Question

Define \(R_n\) to be the maximum amount earned by cutting a rod of length \(n\) meters into one or more pieces of integer length and selling them. For \(i>0\), let \(p[i]\) denote the selling price of a rod whose length is \(i\) meters. Consider the array of prices:
\[ p[1]=1,\; p[2]=5,\; p[3]=8,\; p[4]=9,\; p[5]=10,\; p[6]=17,\; p[7]=18 \] Which of the following statements is/are correct about \(R_7\)?

• A. \(R_7 = 18\)
• B. \(R_7 = 19\)
• C. \(R_7\) is achieved by three different solutions.
• D. \(R_7\) cannot be achieved by a solution consisting of three pieces.

Hint:

In rod cutting, always check all partitions; optimal revenue may be achieved by multiple distinct cuts.

Answer 1

The Correct Option is A, C

Step 1: Evaluate revenue possibilities for rod length 7.
To determine the optimal revenue, consider all meaningful ways of cutting a rod of length 7 and compute the total price using the given price table.

Possible cases:

• No cut: p[7] = 18
• One cut:
  6 + 1 → p[6] + p[1] = 17 + 1 = 18
  5 + 2 → p[5] + p[2] = 10 + 5 = 15
  4 + 3 → p[4] + p[3] = 9 + 8 = 17
• Multiple cuts:
  3 + 2 + 2 → p[3] + p[2] + p[2] = 8 + 5 + 5 = 18

---

Step 2: Determine optimal revenue.
From all evaluated cases, the highest revenue obtainable is 18.

Hence, the optimal revenue for a rod of length 7 is:
R₇ = 18

Therefore, statement (A) is correct.

---

Step 3: Count distinct optimal cutting strategies.
The maximum revenue of 18 is achieved in the following three distinct ways:

• No cut (7)
• 6 + 1
• 3 + 2 + 2

Thus, there are three optimal solutions, making statement (C) correct.

---

Step 4: Reject incorrect statements.
Statement (B): Incorrect, since no combination yields a revenue of 19.
Statement (D): Incorrect, because an optimal solution using three pieces (3 + 2 + 2) does exist.

---

Final Conclusion:
The correct statements are (A) and (C).