I am trying to design an algorithm that solves the following with the minimum number of bar breaks.
A chocolate bar with $n * m$ pieces must be broken into $nm$ $1*1$ pieces to share with $n * m$ people. The bar must be broken only in a straight line, and once broken, only one piece at a time can be further broken. What is the minimum number?
I understand that using properties of a binary tree would best justify my solution and that a divide-and-conquer approach should be used.
Unfortunately, no matter how you do it, you will always use exactly $nm-1$ breaks.
The reason? Every break increases the number of pieces by one!