Stacking the Deck
DOI: 10.1145/3040969 Dennis Shasha
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@example.com; solutions to upstarts and
discussion will be posted at http://cs.nyu.edu/cs/ faculty/
Dennis Shasha ( firstname.lastname@example.org) is a professor
of computer science in the Computer Science Department
of the Courant Institute at New York University, New York,
as well as the chronicler of his good friend the omniheurist
Copyright held by the author.
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
8 6 5 7 8 6 3 [ 1] 7 [ 2 5 4 3 2 4 1]
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 consid-
ered 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 re-
vealed 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
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
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?