Answer:
a. The minimum number of 1-inch cuts for a 30-inch stick is 5.
b. The minimum number of 1-inch cuts for a 33-inch stick is 6.
c. 2ˣ ⁻¹ < n < 2ˣ
Where x shows the minimum number of cuts needed.
Where 2ˣ ⁻¹ shows the starting point of cutting for the minimum number of cuts.
Explanation:
a. Solve the problem for a 30-inch stick.
We need to cut a 30-inch wooden stick into 1-inch pieces.
2⁴ < 30 < 2⁵
16 < 30 < 32
Which means that we need to make at least 5 cuts and the starting point of cutting should be 16 in.
1st Cut:
Cutting the wood at 16 in. gives at most 2 pieces
No. of pieces | size (in) | No. of pieces | size (in)
1 | 16 | 1 | 14
2nd Cut:
Cutting the wood at 8 in. gives at most 4 pieces
No. of pieces | size (in) | No. of pieces | size (in)
3 | 8 | 1 | 6
3rd Cut:
Cutting the wood at 4 in. gives at most 8 pieces
No. of pieces | size (in) | No. of pieces | size (in)
7 | 4 | 1 | 2
4th Cut:
Cutting the wood at 2 in. gives at most 16 pieces (actual 15)
No. of pieces | size (in) | No. of pieces | size (in)
14 | 2 | 1 | 2
5th Cut:
Cutting the wood at 1 in. gives at most 32 pieces (actual 30)
No. of pieces | size (in) | No. of pieces | size (in)
28 | 1 | 2 | 1
Hence total pieces are 28 + 2 = 30 and size is 1 inch.
Therefore, the minimum number of 1-inch cuts for a 30-inch stick is 5.
b. Solve the problem for a 33-inch stick.
We need to cut a 33-inch wooden stick into 1-inch pieces.
2⁵ < 30 < 2⁶
32 < 33 < 64
Which means that we need to make at least 6 cuts and the starting point of cutting should be 32 in.
1st Cut:
Cutting the wood at 32 in. gives at most 2 pieces
No. of pieces | size (in) | No. of pieces | size (in)
1 | 32 | 1 | 1
2nd Cut:
Cutting the wood at 16 in. gives at most 4 pieces (actual 3)
No. of pieces | size (in) | No. of pieces | size (in)
2 | 16 | 1 | 1
3rd Cut:
Cutting the wood at 8 in. gives at most 8 pieces (actual 5)
No. of pieces | size (in) | No. of pieces | size (in)
4 | 8 | 1 | 1
4th Cut:
Cutting the wood at 4 in. gives at most 16 pieces (actual 9)
No. of pieces | size (in) | No. of pieces | size (in)
8 | 4 | 1 | 1
5th Cut:
Cutting the wood at 2 in. gives at most 32 pieces (actual 17)
No. of pieces | size (in) | No. of pieces | size (in)
16 | 2 | 1 | 1
6th Cut:
Cutting the wood at 1 in. gives at most 64 pieces (actual 33)
No. of pieces | size (in) | No. of pieces | size (in)
32 | 1 | 1 | 1
Hence total pieces are 32 + 1 = 30 and size is 1 inch.
Therefore, the minimum number of 1-inch cuts for a 33-inch stick is 6.
c. State a general formula for the minimum number of cuts for an n-inch stick.
2ˣ ⁻¹ < n < 2ˣ
Where x shows the minimum number of cuts needed.
Where 2ˣ ⁻¹ shows the starting point of cutting for minimum number of cuts.