1. FINGERS
Two players each start pointing 1 finger on each hand. The players take turns moving by using one of their hands to touch one of their opponent's hands. The opponent then changes the number of pointed fingers to the sum of the two hands, modulo n. Once a hand has no fingers, it plays no further part in the game. A player wins by making their opponent have no fingers on either hand.
This game is usually played with n=5 for obvious reasons. If it is played with n=2, the first player can win in 3 turns. Who can win with n=3? Who can win larger values of n? If space aliens with m hands of n fingers play this game, who wins?
2. STOCHASTIC WAR
Two players have cards containing the numbers 1 through n. Each move, the players choose one of their cards randomly and compare them. If the numbers are not consecutive, the player with the higher number gets both cards. If the numbers are consecutive, a coin is flipped to see who gets both cards. A player wins by collecting all n cards.
We are interested in the probability of winning holding certain cards. What are the probabilities for collections of cards for n=4? How about larger n?
3. UNEVEN POKER
We start with a subset of playing cards that belong to no one. Two players will claim these cards, one by one, and at the end, whoever has cards that make the best poker hand wins. If the players alternate in taking cards, the first player can not lose if he plays well. Can you show this?
Given a subset of cards, we are interested in the minimal collections of turns that would allow a player to win. For example, if the cards are AAKKQQJ, a player can win if he chooses first, second and sixth, or second, third, and fourth, or second, fourth, sixth, and seventh, in each case by taking the highest cards available. Getting to choose more cards or choose them earlier turns obviously also wins. Thus the minimal collection of winning turns for AAKKQQJ is 126/234/2467.
What minimal collections of turns exist, and what are the smallest number of cards that allow them?
4. SQUARE PACKING
A lists some positive integers, with the restriction that squares having these sides must tile a square of side n. B packs squares of these sizes in a square of side n, if he is able, as he hears them. Once a square is placed it can not be moved later. A gets to watch how B is packing, and may choose to change his sequence based on this. B is trying to pack the largest area possible, A is working against him, and both are using their best strategies. What is the largest area that might be failed to be packed?
If A must list the squares in decreasing order, then what is the answer?
When m=1, Bryce Herdt figured out that the game is related to Fibonacci entry points, and that the game lasts 2 less than http://oeis.org/A001177 turns.
When n=2, Bryce Herdt notes that the first player has an easy victory in 2m-1 turns.
When m=2 and n=3, the second player can win in 6 turns, using the strategy below:
When m=2 and n=4, Berend van der Zwaag showed the first player can win in 7 turns, using this strategy:
When m=2 and n=5, Berend van der Zwaag showed the game is a tie. The strategy is rather complicated!
When m=3 and n=3, Evert Stenlund and Bryce Herdt mapped out the winning strategy for the second player in 10 turns.
When m=4 and n=3, Evert Stenlund mapped out the winning strategy for the second player in 14 turns. The length that the game will last from any position is given below.
Here is the chart of how long the game will last for various values of m and n. The yellow games are won by the first player, and the pink games are won by the second player.
| m \ n | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 4 | 3 | 10 | 6 |
| 2 | 3 | 6 | 7 | ∞ | ||
| 3 | 5 | 10 | ||||
| 4 | 7 | 14 | ||||
| 5 | 9 | |||||
| 6 | 11 | |||||
| 7 | 13 |
Dan Dima made the startling discovery that each card contributes a certain probability of winning, regardless of the other cards in your hand. In other words, if S1 and S2 are disjoint sets of cards, then P(S1 ∪ S2) = P(S1) + P(S2). Thus it suffices to give the probabilities associated with each card.
| n | Probabilities | Author |
|---|---|---|
| 1 | 1 | Erich Friedman |
| 2 | 1/2, 1/2 | Erich Friedman |
| 3 | 1/9, 3/9, 5/9 | Erich Friedman |
| 4 | 1/56, 5/56, 19/56, 31/56 | Evert Stenlund |
| 5 | 1/457, 7/457, 41/457, 155/457, 253/457 | Dan Dima |
| 6 | 1/44626, 9/44626, 71/44626, 415/44626, 1569/44626, 2561/44626 | Dan Dima |
| 7 | 1/55969, 11/55969, 109/55969, 859/55969, 5021/55969, 18983/55969, 30985/55969 | Dan Dima |
| 8 | 1/788192, 13/788192, 155/788192, 1535/788192, 12097/788192, 70709/788192, 267331/788192, 436351/788192 | Dan Dima |
| 9 | 1/12667041, 5/4222347, 209/12667041, 2491/12667041, 2741/1407449, 194411/12667041, 1136365/12667041, 1432093/4222347, 7012601/12667041 | Dan Dima |
| 10 | 1/228794930, 17/228794930, 271/228794930, 755/45758986, 3461/17599610, 445577/228794930, 54023/3519922, 20525279/228794930, 77600353/228794930, 126663169/228794930 | Dan Dima |
Furthermore, Dan Dima found that the denominators for n cards are the continued fraction [0, 2, 4, 6, . . . 2n–2], and that the numerator of the largest card is [1, 4, 6, . . . 2n–2]. The worth of the largest card decreases quickly to .55361+.
Evert Stenlund invented and then analyzed a game similar to this. In his game, both players start with cards 1 through n, and each turn choose a card of theirs. If both cards are the same, they are both discarded. If they are not the same, the lower is discarded, unless it is 1 less than the other card, in which case the higher card is discarded.
For n=1, the game is trivial. For n=2, both players can insure a draw by choosing "1". For n=3, this is game is equivalent to "rock-scissors-paper", since the outcome of the game is decided by the first turn. For n>3, the game is more interesting, including some surprises!
Some minimal collections of turns and the smallest number of cards necessary are shown below:
| Turns | Cards |
|---|---|
| 1 | A |
| 23 | AAK |
| 12 / 245 | AAKKQ |
| 23 | AAAKK |
| 345 | AAKKK |
| 236 / 3456 | AAAKKK |
| 16 / 23456 | AKQJT9 |
| 126 / 234 / 2467 | AAKKQQJ |
| 237 / 34567 | AAAKKQQ |
| 234 / 3467 | AAAAKKK |
| 235 / 3457 | AAKKKQQ |
| 3567 | AAKKQQQ |
| 167 / 34567 | A♠♠♠♠♠♠ |
Are there other turn collections possible with 7 cards or fewer?
When n≤3, B can always pack all the squares.
When n=4, A should start 1, 1, 1, 1, 1, 1, 1. If B didn't leave room for a square of side 3, A should name 3. Otherwise, A should continue 1, 2, 2, resulting in an area of 4 unpacked.
Bryce Herdt handled the case when n=5. A should start 1, 1, 1, 1, 1, 1, 1, 1. If B didn't leave room for a square of side 4, A should name 4. Otherwise A should continue 2, 2, 3, resulting in an area of 9 unpacked.
If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 2/24/11.