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: Compute optimal revenue for length 7.
We check all possible partitions of 7:
\[ 7,\; 6+1,\; 5+2,\; 4+3,\; 3+2+2,\; \text{etc.} \] Their revenues are:
\[ p[7]=18, p[6]+p[1]=17+1=18, \] \[ p[5]+p[2]=10+5=15, p[4]+p[3]=9+8=17, \] \[ p[3]+p[2]+p[2]=8+5+5=18. \]

Step 2: Identify maximum value.
The maximum obtainable revenue is \(18\). Hence, \(R_7 = 18\), and statement (A) is correct.

Step 3: Count number of optimal solutions.
The value \(18\) is obtained by three different cuts: \[ 7, 6+1, 3+2+2. \] Hence, statement (C) is correct.

Step 4: Eliminate incorrect options.
Statement (B) is incorrect since revenue 19 is not achievable.
Statement (D) is incorrect because \(3+2+2\) uses three pieces and achieves \(R_7\).