Communications of the ACM
Last byte
Stacking the Deck
Credit: WildNight
Consider 16 cards consisting of the ace through 8 of hearts and the ace through 8 of spades. You are allowed to arrange the cards as you wish. Your opponent chooses a number between 1 and 8. You deal that many cards from the top of the deck and put the last card face up, with a value of, say, k. You next deal k cards (ace is considered 1) and put the last card face up, with a value of, say, k'. You then deal k' cards and so on. You continue until the number revealed is more than the remaining cards, in which case your opponent wins or the last deal ends with the final card of the 16 and is an ace, in which case you win.
Warm-Up. Find an arrangement in which you can win this game.
Solution. There are many. Here is one possibility
3 4 5 6 7 8 7 6 5 4 3 2 1 2 8 1
If your opponent chooses, say, 2, you deal the first two cards, so the last card is a 4. Turning over the four cards after the 4 lands on an 8, then eight cards after that lands on a 2. Turning over two more cards lands on the final ace. This will work no matter which number between 1 and 8 inclusive your opponent chooses.
Now suppose your opponent takes the following eight cards and arranges them like this
5 2 2 3 3 4 4 1
Can you insert the remaining cards among and perhaps before or after these eight and still guarantee to win?
Solution. Here is one solution, with the inserted cards bracketed
5 2 2 3 3 4 4 [1 7 6 5 6 7 8 8 1]
Consider the same problem, but your opponent starts, as in the Figure here, with
8 6 5 7 8 6 3 7
Solution.
8 6 5 7 8 6 3 [1] 7 [2 5 4 3 2 4 1]
Upstart 1. Suppose your opponent gets to arrange all cards ≥d. You are allowed to insert the remaining cards anywhere you like. Now find the minimum d that will still allow you to be sure to win and show how you did it.
Upstart 2. Suppose you win if your opponent ever lands on an ace, whether of hearts or spades, no matter where it is. Now suppose your opponent gets to arrange all cards ≥d. You are allowed to insert the remaining cards anywhere you like. Find the minimum d that will still allow you to be sure to win and show how you did it.
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
Figures
Figure. Consider a sequence of cards in the order 8 6 5 7 8 6 3 7 of, say, hearts and spades and a collection of hearts and spades 1 1 2 2 3 4 4 5. Can you intersperse the second set of cards in some order into the first sequence to force your opponent to land on the final card, which will be the ace of spades, based on the rules outlined here?
The Digital Library is published by the Association for Computing Machinery. Copyright © 2017 ACM, Inc.
No entries found