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.
What if applet does not run? |
|Contact| |Front page| |Contents| |Eye opener| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny
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 ofN > 1 squares. Split it into two with m1 and m2 squares, respectively. Of course,m1 + m2 = N. By the induction hypothesis, it will take (m1-1) breaks to split the first bar and (m2-1) to split the second one. The total will be1 + (m1-1) + (m2-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
- On the Difference of Areas
- Area of the Union of Two Squares
- Circle through the Incenter
- Circle through the Incenter And Antiparallels
- Circle through the Circumcenter
- Inequality with Logarithms
- Breaking Chocolate Bars
- Circles through the Orthocenter
- 100 Grasshoppers on a Triangular Board
- Simultaneous Diameters in Concurrent Circles
- An Inequality from the 2015 Romanian TST
- Schur's Inequality
- Further Properties of Peculiar Circles
- Inequality with Csc And Sin
- Area Inequality in Trapezoid
- Triangles on HO
- From Angle Bisector to 120 degrees Angle
- A Case of Divergence
- An Inequality for the Cevians through Spieker Point via Brocard Angle
- An Inequality In Triangle and Without
- Problem 3 from the EGMO2017
- Mickey Might Be a Red Herring in the Mickey Mouse Theorem
- A Cyclic Inequality from the 6th IMO, 1964
- Three Complex Numbers Satisfy Fermat's Identity For Prime Powers
- Probability of Random Lines Crossing
- Planting Trees in a Row
- Two Colors - Three Points
|Contact| |Front page| |Contents| |Eye opener| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny
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
|Contact| |Front page| |Contents| |Eye opener| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny
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
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.
|Contact| |Front page| |Contents| |Eye opener| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny
72022662