Communications of the ACM
Last byte
Puzzled: Solutions and Sources
The first puzzle was adapted from Martin Gardner's Colossal Book of Short Puzzles & Problems (W. W. Norton & Co., New York, 2006), Problem 2.10. In his solution, Gardner observed since you need to win two in a row of three games, you must win the middle game; moreover, you must win a game with the black pieces, so having two chances to do it seemed like a good idea. There are two arguments for playing black first, even though it means you get to play white only once. In fact, neither argument is conclusive by itself, nor do they constitute a proof even together. Gardner offered an algebraic proof that starting with black is best, but extending it to the second and third puzzles would be too horrible to contemplate. Is there a watertight argument that circumvents algebra? Yes. Probabilists sometimes use a technique called "coupling" in which random events are tied to the same experiment, and it can be used to good effect here.
1. White or black?
Imagine you play four games against Ioana, alternating white-black-white-black, or WBWB. You must still win two in a row and decide ahead of time whether to discount the first game or the last. This question is clearly equivalent to the earlier one, but now you are in a position to limit the discussion to outcomes in which the decision makes a difference: namely, WWLX and XLWW. In words, what you decided matters only if you win the first two games and lose the third (in which case you should have discounted the fourth) or if you win the last two games and lose the second (in which case you should have discounted the first). The first two and last two games are both WB, so it comes down to comparing the probability of losing the third game with the probability of losing the second game. Since you are black in the second game, the second scenario is more likely, so discount the first game; that is, play BWB.
2. Still need two in a row.
Here you play 17 games, still needing two wins in a row. Note if you start with black you are black, not white, in the middle (ninth) game. Does that change the answer? No. Assume you actually play 18 games, WBWB...WB, and must decide in advance whether to discount the first or last game. Your decision matters only when you win the first two games, lose the third, and win no other two in a row (in which case, you should have discounted the last game) or you win the last two, lose the 15th, and win no other two in a row (in which case you should have discounted the first game). It is easy (but not as easy as before) to see the second scenario as more likely, so again start with black.
3. 10 in a row.
Here you must win 10 in a row out of 49 games, but the argument hardly changes. Begin with black. In general, if the total number of games played is even, time-symmetry implies it does not matter whether you began with white or black. If the total games played and the number of consecutive wins needed are both odd, then, if you made it this far, you should have no trouble showing one should always start with white.
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
©2013 ACM 0001-0782/13/09
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2013 ACM, Inc.
No entries found