Problem of the Month (February 2011)

This month we consider some games.

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?


ANSWERS

1. FINGERS

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.

Finger Game Length
m \ n234567
11243106
2367
3510
4714
59
611
713


2. STOCHASTIC WAR

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.

nProbabilitiesAuthor
11Erich Friedman
21/2, 1/2Erich Friedman
31/9, 3/9, 5/9Erich Friedman
41/56, 5/56, 19/56, 31/56Evert Stenlund
51/457, 7/457, 41/457, 155/457, 253/457 Dan Dima
61/4626, 9/4626, 71/4626, 415/4626, 1569/44626, 2561/44626 Dan Dima
71/55969, 11/55969, 109/55969, 859/55969, 5021/55969, 18983/55969, 30985/55969 Dan Dima
81/788192, 13/788192, 155/788192, 1535/788192, 12097/788192,
70709/788192, 267331/788192, 436351/788192
Dan Dima
91/12667041, 5/4222347, 209/12667041, 2491/12667041, 2741/1407449,
194411/12667041, 1136365/12667041, 1432093/4222347, 7012601/12667041
Dan Dima
101/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!


3. UNEVEN POKER

Some minimal collections of turns and the smallest number of cards necessary are shown below:

TurnsCards
1A
23AAK
12 / 245AAKKQ
23AAAKK
345AAKKK
236 / 3456AAAKKK
16 / 23456AKQJT9
126 / 234 / 2467AAKKQQJ
237 / 34567AAAKKQQ
234 / 3467AAAAKKK
235 / 3457AAKKKQQ
3567AAKKQQQ
167 / 34567A♠♠♠♠♠♠

Are there other turn collections possible with 7 cards or fewer?


4. SQUARE PACKING

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, 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.