Contest Math – How to Cut a 2021-Inch Wood into 2021 1-Inch Pieces with Fewest Cuts

contest-mathproblem solvingpuzzle

A 1×2021 plank is to be cut into 2021 unit squares. In each move, we can either cut through a single plank, dividing it into two (not necessarily equal), or through a stack of planks of equal length, dividing each of them into two in the same way.
Your task is to achieve this goal using as few cuts as you can. How many cuts do
you need?

I tried the following strategy:
Use 7 cuts to cut the plank into 7 planks: 1×1024, 1×512, 1×256, 1×128, 1×64, 1×32, 1×4, 1×1.
Then I need 10 cuts to cut all of them to 2021 unit squares.
So, this strategy needs 17 cuts.

However, the answer is 14

Thank you so much, and good luck!!

Source of the problem:

Source of answer:

Best Answer

Here is a $14$-cut solution, where the greater than sign is my hatchet:

$2021 >\ 2016\ 5 >> 672\ 5\ > 336\ 5\ > 168\ 5\ > 84\ 5\ > 42\ 5\ > 21\ 5\ > 16\ 5\ > 8\ 5\ > 4\ 5\ > 4\ 1\ > 2\ 1\ > 1$

Some explanation: It's costly to do cuts that aren't $2$-fold cuts (like the $7$-fold cut in the OP), but a $3$-fold cut isn't so bad and is always possible by trimming $1$ or $2$ off, which will always be cuts anyways in a situation like this where you need to get to lengths of $1$, so powers of $2$ are the natural framework to think of. You can get a $15$-cut solution that way from $2021$. But combinations of powers of $2$ are also good trims to make, since a single extra cut later on reduces such numbers to cuts that would have to be made anyways. E.g., $5=4+1$, $9=8+1$, or $20=16+4$. If our trim is a number like $5$, then we also consider numbers like $5+8=13$ or $5+16=21$ auspicious, since we will already have to split that into its squares at some point.

In this particular case, $2021=2016+5$, and $2016=3(672)=3(21)(32)=3(16+5)(32)$. So if we trim $5$ to start, we need just one extra cut for the $3$-fold part, and one extra cut to split the $5$s into $4$s and $1$s.

Related Question