Breaking a chocolate bar
Task number: 3326
let’s have a chocolate bar with \(m\times n\) squares. Determine how many times you must break some piece of chocolate into two smaller pieces until you obtain \(mn\) individual squares.
Find a way to break the bar with as few breaks as possible.
Solution
Let \( f(m,n) \) be the number of table breaks with dimensions \( m \times n \). The following identities follow from the assignment:
\(f(m,1)=m-1\)
\(f(1,n)=n-1\)
\(f(m+m’,n)=1+f(m,n)+f(m’,n)\)
\(f(m,n+n’)=1+f(m,n)+f(m,n’)\)These have the solution \( f (m, n) = mn-1 \).
Answer
The breaking procedure is irrelevant, it will always be necessary to break \( mn-1 \) times.