Breaking Chocolate Bars

Assume you have a chocolate bar consisting, as usual, of a number of squares arranged in a rectangular pattern. Your task is to split the bar into small squares (always breaking along the lines between the squares) with a minimum number of breaks. How many will it take?

The purpose of the simulation below is to help you come up with the right answer. Please try it before you proceed to the solution. Click where you want to break them.

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Breaking Chocolate Bars

What if applet does not run?

Answer

As many as there are small squares minus 1.

Proof #1 (by induction)

If there are just one square we clearly need no breaks.
Assume that for numbers 1 ≤ m < N we have already shown that it takes exactly m - 1 breaks to split a bar consisting of m squares. Let there be a bar of N > 1 squares. Split it into two with m₁ and m₂ squares, respectively. Of course, m₁ + m₂ = N. By the induction hypothesis, it will take (m₁-1) breaks to split the first bar and (m₂-1) to split the second one. The total will be 1 + (m₁-1) + (m₂-1) = N-1.

Proof #2

Let start counting how many pieces we have after a number of breaks. The important observation is that every time we break a piece the total number of pieces is increased by one. (For one bigger piece have been replaced with two smaller ones.) When there is no pieces to break, each piece is a small square. At the beginning (after 0 breaks) we had 1 piece. After 1 break we got 2 pieces. As I said earlier, increasing the number of breaks by one increases the number of pieces by 1. Therefore, the latter is always greater by one than the former.

Follow up

It should be now clear that the rectangular formation of a chocolate bar is a red herring. The basic fact explained above may appear in many different guises. For example, there are quite edifying games based on the principle explained above (with every move a number related to the game is increased by 1.) These games are not very challenging as such. However, they furnish an edifying experience besides giving a chance for a knowledgeable person to show off if he/she is the only one who knows the secret. Here are a few examples.

Problem #1

A fellow sawed 25 tree trunks into 75 logs. How many cuts did he perform? (Answer)

Problem #2

75 teams took part in a competition organized according to the olympic rules: teams met 1-on-1 with the defeated team getting dropped out of the competition. How many meets are needed to before one team is declared a winner? (Answer)

Problem #3

(C. W. Trigg, Mathematical Quickies, Dover, 1985, #29.)

In assembling a jigsaw puzzle, let us call the fitting together of two pieces a "move", independently of whether the pieces consist of single pieces or of blocks of pieces already assembled. What procedure will minimize the number of moves required to solve an N-piece puzzle? What is the minimum number?

Problem #4

(C. W. Trigg, Mathematical Quickies, Dover, 1985, #13.)

There are N players in an elimination-type singles tennis tournament. How many matches must be played (or defaulted) to determine the winner?

Game #1

Two players take turns breaking a bar. The last to break a piece wins the game.

An Aside

It's a great way to learn of odd and even numbers. Any one privy to the secret would know what is preferable: to start the game or to be a second player - depending as whether the total number of squares is even or odd.

Game #2

Marbles, checkers, or stones are arranged in several piles. A move consists in selecting a pile and splitting it into two. The player to split the last pile is the winner. (Explanation: it clearly does not matter how many piles one starts with. Imagine starting with a single pile and then making a few moves "that do not count.")

Other simple games may be thought up to explain and reinforce the notion of parity, i.e., the concepts that odd and even numbers are of different parities. For example,

Game #3

Write a sequence of numbers. For the entertainment sake, let one opponent write the sequence and the other start the game. A move consists in writing a plus or a minus sign between two adjacent terms. The first player wins if, with all signs inserted and computations carried out, the result is odd. If the result is even, the second player wins. (Explanation: The result does not depend on the particular distribution of signs at all. Adding or subtracting an even (odd) number does not change (changes) the parity of the result. So the final result will be odd iff the number of odd numbers in the sequence is odd.) You may want to test your skills against your computer's.

Remark

Returning to the original problem of a chocolate bar, the number of moves needed to break it into separate squares is invariant with regard to the actual sequence of moves. A less trivial invariant may serve as a basis for a trick suitable for a magic show.

Yvan_Roux from Canada was inspired to make the following remark

Congradulations!

We can use the same induction proof to prove that the result is true for a puzzle or a 3D shape made of elementary pieces, as far as we do not break the elementary pieces.

Yvan Roux

References

D. Fomin, S. Genkin, I. Itenberg, Mathematical Circles (Russian Experience), AMS, 1996
P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004

What Is Red Herring

Problem #1

A fellow sawed 25 tree trunks into 75 logs. How many cuts did he perform?

Answer

Every cut increased the number of logs by 1. Thinking of a tree trunk as a big log, it took 75 - 25 = 50 cuts to get 75 logs out of 25.

Problem #2

Answer

With every meet, the number of teams in the competition is decreased by 1. It takes 74 meets to seed 1 team out of 75.

71924321