Cutting a 4 by 4 by 4 cube when you may restack
A wooden cube measures 4 inches on each side. A carpenter wants to cut it into 64 one-inch cubes using a saw that makes straight, planar cuts all the way through whatever is in front of it. Between cuts the carpenter may rearrange and stack the pieces however she likes, so that one cut can pass through several pieces.
Without restacking, 3 + 3 + 3 = 9 cuts are needed. What is the smallest number of cuts with restacking allowed, and why can it not be beaten?
Show a hint
Think about a single direction. The cube is 4 inches long that way and must end up in 1-inch slices. Each cut can at most double the number of slices in that direction.
Your answer
Solving needs a free account
Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.
Discussion
💡 Discussion rules
- No full solutions here. Hints and approaches only.
- Complexity, edge cases and intuition are the point.
- Interview experiences are welcome. Respect your NDAs.
Loading discussion…
Learn the concepts
The theory behind this question.