Cutting one $100$-inch-long piece of wood into one-hundred $1$-inch-long pieces using the fewest cuts

Question

Here is a tricky problem that I haven't been able to solve yet:

Finn is cutting a $100$-inch piece of wood into one-hundred $1$-inch pieces of wood.

What is the minimum number of cuts Finn has to make if he is allowed to cut several pieces at the same time?

Note: The wood must stay the same "thickness" at all times. So if the wood was laying flat on the ground, you cannot slice it horizontally to keep the length and width the same but have two flimsy pieces.

The lowest I have gotten is $9$ cuts so far. Thank you all so much, and good luck!!

Answer 1

1. Cut at 64 inches from the left
2. Lay your two pieces on top of each other, aligned at the left, and cut at 32 inches from the left
3. Lay all your pieces on top of each other, aligned at the left, and cut at 16 inches from the left
4. Repeat with 8 inches, then 4 inches, then 2 inches, then 1 inch

This procedure uses seven cuts. To see that six or less cuts cannot solve the problem note that a cut can at most double the number of pieces, so after six cuts, you cannot have more than $64$ pieces.

Answer 2

The minimum number of cuts needed is 7.

First, each cut can at most double the number of pieces you have. Therefore, you will need to make at least 7 cuts (since $2^6 = 64 < 100$ while $2^7 = 128 > 100$).

It remains to show that 7 cuts suffices. The following sequence of cuts works:

1. Cut the stick into a length of 64 inches and a length of 36 inches.
2. Lay the pieces so that the left ends line up, and then cut so that you have 3 pieces of length 32 and 1 piece of length 4. In all future cuts we will also start by laying the pieces so that their left ends line up.
3. Cut the pieces into 6 pieces of length 16 and 1 piece of length 4 (in this step we do not actually cut the piece of length 4).
4. Cut the pieces into 12 pieces of length 8 and 1 piece of length 4.
5. Cut the pieces into 25 pieces of length 4.
6. Cut the pieces into 50 pieces of length 2.
7. Cut the pieces into 100 pieces of length 1.

I believe that this algorithm of always cutting the largest power of two which is smaller than the largest piece will be optimal in general, not just for 100 pieces.

Answer 3

If he stacks every piece and cuts everything in half he will double his pieces each cut. So in $n$ cuts he will have $2^n$ pieces. $2^6 < 100 < 2^7$ so he needs at least $7$ cuts.

But if he cuts exactly in half his pieces will not be exactly $1$ inch.

If first cut is at the $50$ (He now has $50$ inch pieces. $2$ of them.).

Second is at $25$. (He now has $25$ inch peices. $4$ of them.).

Third is at $13$ inches. (he now has some $13$ inch pieces and some $12$ inch pieces. $4$ of each).

Fourth is at $7$ (he now has some $7$ inch pieces ($8$), some $6$ inch pieces ($4$) , and some $5$ inch pieces ($4$).)

Fifth cut at $4$ inches. (he now has some $4$ inch pieces ($16$), so $3$ inch pieces ($8$), some $2$ inch pieces ($4$), and some $1$ inch pieces ($4$).

Sixth cut is at the $2$ inches. (he now has $2$ inch pieces ($44$) and some $1$ inch pieces ($12$).)

Last cut is at $1$ inch. (he now has $100$, $1$ inch pieces.)

This isn't the only way to do it in $7$ but $7$ is required. You could reason he need $7$ cuts so he might as well always cut at the $2^k$ mark.

Cut 1: at $64$, gives him at most $2$ pieces the largest of which are $64$ but one may be shorter. (one is $36$ inches)

Cut 2: at $32$, give him at most $4$ pieces the largest of which are $32$ but one may smaller. (one is shorter at $4$ inches)

Cut 3: at $16$ gives him at most $8$ pieces (actually $6$) the largest of which is $16$ but one may be smaller. ($1$ is shorter at $4$ inches).

Cut 4: at $8$ gives him at most $16$ (actually $12$) pieces the largest of which is $8$ but one may be smaller. ($1$ is shorter at $4$ inches).

Cut 5: at $4$ gives him at most $32$ (actually $25$) pieces the largest of which is $4$ but one may be smaller. (But they aren't.).

Cut 6: at $2$ give him at most $64$ (actually $50$) pieces the largest of which is $2$ but one my be smller. (But there isn't.)

Cut 7: at $1$ final cut he has at most $128$ (actually $100$ pieces at $1$ inch each.