Math behind Maximum-Product in Rod-Cutting Problem

algebra-precalculuscontest-mathoptimizationproductsprogramming

I am self-learning Data Structures and Algorithms and I came across a problem recently.

Given a rod of length n, find the optimal way to cut the rod into smaller rods in order to maximize product of profit of each of the smaller rod. Assume each rod of length i has profit i.

For example, consider a rod of length $4$. The maximum product will be $4$ ( $=2\times2$ or not cutting it ).

For another example, a rod of length $6$ has maximum product $9$ ( $=3\times3$ ).

I have designed my program and successfully solved this problem. When I looked into the problem more, I found a pattern:

The maximum product can be obtained be repeatedly cutting parts of length $3$ while length is greater than $4$, keeping the last part as length of $2$, $3$ or $4$.

For example,

  1. Length $14$: maximum product $= 3\times3\times3\times3\times\color{blue}{2}=162$.
  2. Length $15$: maximum product $= 3\times3\times3\times3\times\color{blue}{3}=243$.
  3. Length $16$: maximum product $= 3\times3\times3\times3\times\color{blue}{4}=324$.

This fact is interesting, but I'm not able to prove it mathematically. Any suggestions, hints or answers will be appreciated. Thanks for reading this post.

Source: https://www.techiedelight.com/maximum-product-rod-cutting/

Best Answer

This problem is essentially IMO $1976/P4$.

The idea is that using maximum number of $3$'s is most efficient. Since larger numbers can be broken down into smaller ones, keeping the sum same but increasing the product.

For example, if any part is $5$ it can be broken down into a $3$ and $2$ increasing the product contribution from $5$ to $6$. A $6$ into two $3$'s - product contribution : $6$ to $9$. A $7$ into $3,4$ or $3,2,2$ - product contribution : $7$ to $12$.

The reason is simple inequality : $$xy \ge (x+y)\cdot 1 \iff (x-1)(y-1)\ge 1$$

That is, it is beneficial to convert a single part $(x+y)$ into two parts $x$ and $y$ as long as $x,y \ge 2$. Now for size $6=2+2+2=3+3$. But $$3\times 3 > 2 \times 2 \times 2$$

So we observe use of maximum $3$'s is optimal.

For $n \equiv 0 \pmod 3$, all parts should be $3$'s. For $n \equiv 1 \pmod 3$, $n \equiv 2 \pmod 3$ all $3$'s except for one $4$ and one $2$ can be used respectively.

Related Question