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. Therefore, 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 also 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 a 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 matches 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
Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and
Puzzles to which he brought more than 10 years of college instruction
and, at least as much, programming experience. He holds M.S. degree in
Mathematics from the Moscow State University and Ph.D. in Applied
Mathematics from the Hebrew University of Jerusalem. He can be reached at
alexb@cut-the-knot.com
Copyright © 1997 Alexander Bogomolny
