# Cutting one 2021-inch-long piece of wood into 2021 1-inch-long pieces using the fewest cuts

A 1x2021 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: 1x1024, 1x512, 1x256, 1x128, 1x64, 1x32, 1x4, 1x1. 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!!

## 1 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.

• This is a very smart specific solution. If I may rearrange your solution a bit: you reach a multiple of $32$ and then just keep halving the big number: $2016 + 5 > 1008 + 5 > 504 + 5 > 252 +5 > 126 + 5 > 63 + 5$ but then you found the smart breakdown of $63 + 5 >> 21 + 5 > 16 + 5$ where the first step involves dividing by three... Any idea as to a general algorithm to find minimum no. of cuts? Commented May 11 at 19:24
• I've been thinking of and on about this. $2023=((2\color{red}+1)(2^4\color{orange}+ (\color{blue}{2^2\color{green}+1}))\cdot 2^5 \color{purple}+ (\color{blue}{2^2\color{green}+1})$ So the highest power of $2$ is $2^{1+4+5}=2^{10}$ so there are $10$ "binary" cuts. (Obviously as $2^{10}<2023<10^{11}$) and then there are four distinct plus signs (Although $(\color{blue}{2^2\color{green}+1})$ are separated they are the same thing and will be cut together so the two green plus signs count as one) so there are $4$ additional "odd" cut. What I can't figure is how to minimize the number of plus signs. Commented May 11 at 20:24
• $2021=111100101$. We can do this as $((((((2+1)2+1)2+1)2+1)2+1)2^3 + 1)2^2 + 1$ so the most odd cut's needed are $7$ but this is clearly inefficient. $2021=$ a multiple of $4 + 1$ is less impressive than $2021=$ a multiple of $32$ plus $5$ but I'm not sure how I'd quantify that observation. $2021=((((2+1)2+1)2+1)2+1)2+1)2^5 +5=((((2+1)2+1)2+1)2+1)2+1)2^5 +(2^2+1)$ still has seven odd cuts. But if we have $5$ we might as well use it more so we look for $K=2^a+5$ and get that $63=3\times(2^4+5)$ so that's more efficient. But not know how to algomorize that. Commented May 11 at 20:38
• \$\color{red}{x^2 + \color{green}{2+5}=7} + \color{blue}e^7\$ will render as $\color{red}{x^2 + \color{green}{2+5}=7} + \color{orange}e^7$. In other words \color{name of color}{text you want to color}. You can nest them and if you don't put text in brackets it we color the next single character. But you must provide a name of a color as an argument. Commented May 12 at 1:03
• More generally, the mathjax guide math.meta.stackexchange.com/questions/5020/… contains a ton of stuff, and while this main guide does not discuss Colors, it links to an answer that does: math.meta.stackexchange.com/a/10116/546005 Commented May 12 at 15:29