#116easyBrainteasers
Breaking a Chocolate Bar
Time Limit: 2sMemory: 256MB
Problem
You have a rectangular chocolate bar made up of M x N small square pieces arranged in a grid pattern (M rows and N columns). You want to break this bar into all of its individual small square pieces.
Each "break" consists of picking up a single piece of chocolate (which may be the original bar or any fragment you have already broken off) and snapping it along one of its straight grid lines, splitting it into two pieces. You may not stack pieces or break multiple fragments at once.
What is the minimum number of breaks required to separate the entire bar into all M x N individual squares? Prove that your answer is optimal.
Your Workspace
Think through the problem, use the hints if stuck, and reveal the solution when ready.
Hints
Hint 2 (reveal previous hint first)
Hint 3 (reveal previous hint first)