Communications of the ACM

Last byte

Puzzled: Solutions and Sources

By Peter Winkler
Communications of the ACM, June 2011, Vol. 54 No. 6, Page 126
10.1145/1953122.1953151
Comments

Solution. Recall that in deterministic poker, all 52 cards are spread out face up. Alice chooses five, followed by Bob choosing five. Alice can then discard any number of cards (which then go out of play) and draw a like number, finishing with five cards. It's then Bob's turn to draw, with the same options. All actions are deterministic and seen by both players who compare hands. Bob wins if the hands are equally good. The question is, who wins the game with best play?

Note that Alice is a goner if she doesn't immediately prevent Bob from constructing a royal flush—A, K, Q, J, 10 of the same suit—since this is the best hand in poker. So, to have a chance, she must pick at least one of A, K, Q, J, 10 from each suit.

Since straight flushes are the critical threat, Alice's best choice for these cards is the four 10s, permanently preventing Bob from getting a straight flush 10-high or better. Bob is doomed, as Alice will be able to get either A-K-Q-J-10 or 10-9-8-7-6 in a suit after drawing. To prevent it, Bob, on his first turn, would have to pick both a card higher than the 10 and a card lower than the 10 in each suit, adding up to eight cards, though he can take only five.

Any initial hand with the four 10s wins for Alice. She can also win with only three 10s, provided she takes A–9, K–9, Q–9, J–9, K–8, Q–8, J–8, Q–7, J–7, or J–6 of the fourth suit as well. This adds up to (52–4) + 4x10 = 88 winning initial hands for Alice.

This problem was posed by Martin Gardner in his famous Mathematical Games column in Scientific American and included in The Scientific American Book of Mathematical Puzzles & Diversions, Simon & Schuster, New York, 1959, 23.

Back to Top

2. Random chess.

Solution. Recall that Clarissa, a computer-science major and president of her university's chess club, has programmed her laptop to play random chess. At each position, all possible legal moves are computed, with one chosen uniformly at random. The program is designed to quit if and only if a checkmate or stalemate is achieved or if just the two kings remain. The question was, how can her program get caught in a loop?

Turns out, lots of ways...In some cases the players are reduced to a single forced move at each turn; in others (as in the figure here, a position suggested by Dartmouth student Cole Ott), they have scope but no way to interact.

The chances of a correct program being caught in such a loop are virtually zero. I don't know about Clarissa, but if I wrote the program and it fell into a loop, it would be due to a bug.

Back to Top

3. Winning Hex.

Solution. The unsolved problem was to prove that making one's first move in the center cell leads to a win, with best play, for the first player in Hex. Recall that we already knew (through a "strategy-stealing argument") that the first player has a winning strategy, and it's difficult to believe that playing in the center would undermine it. However, no move by the first player has been identified as part of a winning strategy, even though, amazingly, some moves (near the corners) are known to lose.

Curiously, the game "Random-Turn Hex," in which the players flip coins to determine who moves next, is better understood (and fairer) than the standard alternating game. See the delightful article by Y. Peres et al. "Random-Turn Hex and Other Selection Games" in American Mathematical Monthly 114 (May 2007), 373–387.

Back to Top

Back to Top

Back to Top

Back to top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.

---

No entries found