Pizza and Problems/Pizza and Problems 6 (12/5/08)
From MSEnuxWiki
Contents |
Student Solutions to the Problems in Pizza and Problems Set #6
Problem 1: Solution by: Bruce Wagner
When playing this game, the only way to control the action is to make the proper choice when faced with a pile of 3: do you take the whole pile, or leave 2? (You could also take one from another pile, but that would give control back to the other person.)
Note also that if you present the other person with one pile of 4 or 6, or a configuration of 4-4, 4-6, 4-4-4, or 4-4-6, then you can always win. Likewise, 5-5 is a winning position because it can be reduced to 4-4.
The other observation is that there are 10 total moves if both players take the maximum each move (i.e., the entire pile of 3 when it appears). In that case, the second player will win. In order to prevent that, the first player can change the situation by first taking 1 from the 3 pile, leaving 2.
In fact, that first move is a winning strategy for the first player. Let's call the first player "A", and the second one "B". Than A starts by taking 1 from the 3 pile to leave 2-4-5-6.
B has several choices for the second move:
1. B takes the 2 pile, leaving 4-5-6. Then A can take 1 from the 5 pile to leave a winning position of 4-4-6.
2. B takes 1 from the 4 pile, leaving 2-3-5-6. A can then take the entire 3 pile, leaving a winning position of 2-5-6 (this reduces to either 4-6 or 5-5 after two more moves).
3. B takes 1 from the 5 pile, leaving 2-4-4-6. A can then take the entire 2 pile, leaving a winning position of 4-4-6.
4. B takes 1 from the 6 pile, leaving 2-4-5-5. A can then take the entire 2 pile, leaving a winning position of 4-5-5 (this reduces to either 4-4-4 or 5-5 after two more moves).
Problem 2: Solution by:
Problem 3: Solution by:
Problem 4: Solution by:
Problem 5: Solution by: Bruce Wagner
