Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992); Database Tuning: A Principled Approach (Prentice Hall, 1992); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer-Verlag, 1998). He can be contacted at [email protected].
It was Baskerhound again. "Ecco, you may be nearly as surprised as I am by my new job. The FBI has engaged me to negotiate with a kidnapper."
"A replay of the theme of 'It Takes a Thief'," Ecco said with a smile. (Readers of Codes, Puzzles, and Conspiracy may remember that Benjamin Baskerhound once kidnapped Ecco for his puzzle-solving talents, but things didn't completely work out.)
Baskerhound chuckled. "You wouldn't hold that small escapade against an old friend after all these years, would you? Anyway, I have a personal vendetta against this kidnapper — they call him Sam the Snatcher. He has the conceit of being the world's greatest gamester. What nerve."
"It seems that he wants to play a game he calls "Ultimate Tic-Tac-Toe" against the FBI. If we win, he will charge only 10 million dollars per hostage. Rates have gone up since you were my guest."
Ecco smiled again. I suspected he still missed Baskerhound's hideouts and his companions.
"So, what's the game, Dr. Baskerhound?" 13-year-old Liane asked.
"I'm glad someone is taking me seriously around here," Baskerhound replied and then directed his explanation to Liane.
"Imagine a 4 X 4 grid (not 3 X 3). We will play a tic-tac-toe variant on this. Players alternate play as in tic-tac-toe with X moving first and then O moving second. A threesome for X is a set of three cells that form a line vertically, horizontally, or diagonally that all contain Xs. Similarly for a threesome for O. Since the grid is 44, there are 16 cells, so eight alternating turns of the two players will fill the board.
"Now for the rules: If a player gets a threesome before his last possible turn, then he loses. If he gets a threesome on his last turn, he wins. The game is of the 'sudden death' variety. As soon as there is a loser or a winner, the game stops. So if both players could get a threesome on the last turn, then the first player wins anyway. If either player loses on some turn (by getting a threesome too early), then it doesn't matter if the other player would be forced to lose on his next move. The player who loses first still loses. If neither player gets a threesome by the end of the game, the game is a draw. The big question is: Does either player have a winning strategy (that is, can they force a win)? If not, can either player force a draw?
"Fortunately, we don't have to answer the big question. Sam has given us two game puzzles. Train your intuition on the first one. Can X force a win from this configuration? (In Figure 1(a), it's X's move.)"
Reader: Please give this a try before you read on.
"I think so," Liane replied.
"First move as in Figure 1(b). By case analysis, nothing O can do will prevent the X player from being able to place X in a square that will give him two opportunities to win in the last turn. X has two ways to win on the next turn."
"Nicely done, young mathematician," Baskerhound said. "Now for Sam's second puzzle in Figure 2. The asterices represent moves by X and O. All you know is that neither has a threesome and that there are six Xs and six Os among the perimeter. Can X force a win in this case?"
Reader: What do you think? Can you prove your answer?
Liane was able to answer the question. Baskerhound left to talk to his "handlers."
Still, his original question weighed heavily in the air. Was a winning strategy possible for X in general or could O always force a draw? I never heard the answer.
Reader: Would you like to give this a try? Even if you use the computer to help you search, please express your strategy in a simple way (no table lookup). Try to find a simple proof as well.
Another variant of the game is the Come-Back variant. In that variant, O wins if he obtains a threesome on the eighth turn regardless of whether X has already obtained a threesome on his eighth turn. On the other hand, early threesomes still face a sudden death rule. In that case, does O have a winning strategy?
Reader: Ecco never told me about this one either. Would you like to try? Again, strive for a simple proof.
Last Month's Solution
Placing parks at the points: (3,1), (4,1), (5,1), (7,1), and (8,1) giving an initial configuration of
000000000000
000000000000
000000000000
0P0110000000
0P0000000000
0P0000000000
000000000000
0P0000000000
0P0000000100
000000000100
000000000000
000000000000
retards full development of all nonpark land by 15 years.
Reader Notes
Several readers found solutions to the "Who Rules?" puzzle (DDJ, September 2001) including: Michael Birken, Wyatt Matthews, Chad Harrington, Pieter Gosselink, Geoffrey Probert, Bob Byard, Bernhard Kuehl, Laszlo Vecsey, Jim Woodgate, Andrew Calafato, Jim Love, Scott Romanowski, Tomas G. Rokicki, Grisha Golberg, Richard Ford, Pearl Pauling, Rodney Meyer, Hans Knorr, Andrew Palfreyman, Yves Piguet, Ketil Malde, Wim Nuij, and Robin Golden.
Birken and Vecsey were the first to observe that units 1 and 5 might be interchanged in the solution to the first question, yielding
3
|
+ — 7
| |
| + — 1
| | |
| | + — 2
| | |
| | + — 6
| | |
| | + — 8
| |
| + — 5
|
+ — 12
|
+ — 4
|
+ — 9
|
+ — 10
|
+ — 11
and
3
|
+ — 7
| |
| + — 1
| |
| + — 5
| |
| + — 2
| |
| + — 6
| |
| + — 8
|
+ — 12
|
+ — 4
|
+ — 9
|
+ — 10
|
+ — 11
Several readers — including Birken, Matthews, Kuehl, and Goldberg — found multiple solutions to the second problem, while identifying 6 and 8 as Silky and Slit.
DDJ
