| Manifesto | Bookstore | Contents | Amazon store | Term index | What changed? | Contact | Recommend |
Breaking Chocolate BarsAssume 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.
Copyright © 1996-2009 Alexander Bogomolny
AnswerAs many as there are small squares minus 1. Proof (by induction)
Proof #2Let 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 upThe 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 #1A fellow sawed 25 tree trunks into 75 logs. How many cuts did he perform? (Answer) Problem #275 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) Game #1Two players take turns breaking a bar. The last to break a piece wins the game. An AsideIt'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 #2Marbles, 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 #3Write 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. RemarkReturning 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
References
Copyright © 1996-2009 Alexander Bogomolny
Problem #1A fellow sawed 25 tree trunks into 75 logs. How many cuts did he perform? AnswerEvery cut increased the number of logs by 1. Thinking of a tree trunk as a big log, it took
Copyright © 1996-2009 Alexander Bogomolny
Problem #275 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? AnswerWith every meet, the number of teams in the competition is decreased by 1. It takes 74 meets to seed 1 team out of 75.
Copyright © 1996-2009 Alexander Bogomolny |
| 34219971 |  |
