Cut The Knot!

An interactive column using Java applets
by Alex Bogomolny

Breaking Chocolate Bars

November 1997

The chocolate bar puzzle has three parameters: two side lengths (m and n) and actual selection of lines along which to break the bar and its parts. Changing all three at once would produce wealth of experimental data which would be hard to organize. On the other hand, keeping m and n fixed for a few trials leaves a lot of room to experiment with the third parameter even for small values of m and n. Following this venue it is hard to miss the fact that the number of breaks actually does not depend on the sequence of moves. Once you noticed this for one pair of m and n, it is natural to verify the guess for a few other pairs. After several attempts this will become clear: the number of breaks it takes to split a chocolate bar into its constituent squares depends on neither its shape nor the selected sequence of breaks but only on the total number of squares m*n. Furthermore, denoting this number as f(m*n) we summarize the results of the experiments in a simple formula f(m*n) = m*n - 1. Which is to say, the number of breaks it takes to completely split a chocolate bar into small squares equals the number of squares minus 1.

This is our working hypothesis which will become even more credible after a few additional trials. Still, in mathematics, the only way to establish the veracity of a hypothesis is to prove it, i.e., derive it from simpler facts following rules formulated and accepted for this purpose. Thus I want to prove that the number of breaks f(m*n) is indeed a function of m*n equal to m*n - 1. Let's denote m*n as N. Then, what I plan to prove appears as f(N) = N - 1.

Is it a more general formulation? Superficially, it is. Because having a generic N instead of a more specific m*n suggests that the bar may not be rectangular. On the other hand, any number N can be split into a product of two factors. If N is composite, this can be done in many ways. If N is prime than still N = N*1. In the latter case, we envisage a single row chocolate bar, quite long for large N. This case is trivial: imagine N squares arranged horizontally in a single row. There are N - 1 vertical edges along which adjacent squares abut each other. To separate the squares all it takes is to break along each such edge. This is of course true for any N, not necesarily prime.

The simple N*1 case lends additional support for the hypothesis and now it may be the right time to tackle the more general case. However, the skeptical among us may want to verify it one more time. Not to lose time breaking a real bar or switching to another page to play with above mentioned applet, let's simply make a thought experiment. We have already broken an imaginary N*1 bar into small squares. Imagine putting them back in a row again. Or, choosing an even easier (especially for large N) route, just sweep them into a pile. Surely it is all the same:

Finding integer K and M such that N = K + M,
Breaking an N*1 bar after the Kth square (counting either left or right), or
Splitting a pile into two, of sizes K and M, respectively.

To every break of a row of squares there corresponds a split of a pile of square counters. In a pile though, it is not at all important whether the counters are square or not. However, a pile of counters presents a more general situation. Indeed, with a pile there is no restriction to separate only abutting squares. We can split the pile into two any way we choose. On the other hand, since the counters are (implicitly assumed to be) indistinguishable, we may as well re-arrange them in a row, before or after splitting the pile up. So the problem of pile splitting is equivalent to the problem of breaking a narrow (N*1) chocolate bar. Then again, breaking arbitrary shaped bars is too a special case of pile splitting because the latter offers more freedom to select moves. Therefore, whatever is true of a special N*1 case is also true of the (apparently but not really more general) m*n case. This concludes the proof.

The proof? From what simpler facts and with what rules have we derived our result? The simple fact we used was the assertion that for an N*1 bar the statement of the hypothesis is indeed correct. Such a bar has N - 1 edges that must be broken. I, for one, feel this claim is simple enough to be generally acceptable as true. On the other hand, it can also be derived from another, apparently simpler, fact. Now, what rules did the proof use? We first established an isomorphism between our problem and another one. Next, we applied the rule of isomorphism

Isomorphic problems have the same set of solutions.

To apply this rule we have established the following correspondence: bar - pile, break - split, square - counter. With this correspondence, we discovered that the problem of breaking an N*1 bar is outright equivalent to the problem of splitting a pile of N counters. Next, we noticed that the problem of breaking an m*n bar is equivalent to the problem of splitting a pile with a limited number of legitimate moves. However, from the first isomorphism, pile splitting takes the same number of moves regardless of what moves have been actually performed. Therefore, we concluded with regard to the bar breaking, that the only thing that matters is the total number of squares and not their arrangement.

It's amazing how much can be said about this simple problem. For one, no one will be surprised to learn that the problem admits several essentially different proofs. It might be expected that traditional induction would apply to a problem whose essence is counting objects. Another proof depends on the fact that there is a quantity that does not change when pieces is broken. Such quantities are called problem invariants and finding such properties is often helpful in problem solving. Several simple games include bar breaking or pile splitting activities.

The problem also admits a couple of generalization.

What if we are allowed to break a bar along zigzagging lines? How long will it take to ultimately break an m*n bar into small squares?
Going into higher dimensions, imagine having a chocolate brick consisting of k*m*n small cubes. A move consists in breaking a brick along the sides of small cubes, etcetera.

Arguably, the problems of bar breaking and pile splitting are kindred. Surprisingly, both are isomorphic to another one that comes from an unexpected corner: planning an olympic competition:

A tennis tournament is arranged by rounds. On every round, all eligible players draw lots to determine who plays whom. Only the winners advance to the next round. If necessary, one preferred lot is thrown in whose lucky owner sits the round out. How many meets must be played before an olympic champion emerges victorious?

The problem has a geometric analogue: Find the maximum number of non-intesecting diagonals in a convex N-gon that could be drawn simultaneously. To see the analogy, call an N-gon, say, a (N-2)-plex. Then a single diagonal splits an N-plex into an K-plex and M-plex such that N = K + M, etc.

The reverse problem is also of some interest. N counters are strewn on the table. The task is to collect them into a single pile. On a single move, one is allowed to combine two existent piles (a single counter is regarded as a pile for this purpose.) Does selecting a counter and adding to it counters one at a time seems too slow to you? Is it possible to speed the task up by combining bigger piles?

Finally, the next applet further exploits the idea of invariants in mathematics.

References

D. Fomin, S. Genkin, I. Itenberg, Mathematical Circles (Russian Experience), AMS, 1996
D. Wells, You are a Mathematician, John Wiley & Sons, 1995

33062484

Amazon.com Widgets