There are 2n cards labeled 1, 2, ..., 2n respectively, and the cards are distributed randomly between two players so that each has n cards. Each player takes turns to place one card, and you win if you put down a card so that the current sum of all the played cards is divisible by 2n+1.
For example, if n=10, and the previously placed cards are 5, 8, 9, 19, then if player A now places 1, he wins since 5+8+9+19+1 = 42 is divisible by 2*10+1=21.
Assuming both players want to win, what strategy should one adopt in order to win? Following the strategy, is there a consistent winner of this game?
(In reply to
More thorough solution by David Shin)
So in less-math speak:
Since the numbers on the cards are all less than the multiplier
there is only ever one possible card that when played will cause an
immediate win (for example if you only have cards up to ten, if the
current sum is 10, it may be possible to make ten, but there's no way
to make 22: the most you can get is 20. You would have to play a
one to make 11). Now on your turn either you have that card and
you play it and do a little victory dance, or you don't. If you
don't have it, then you try to play a card such that your opponent
can't win on the next term.
Now consider the progress of a game. On player one's turn
looks through his cards, sees what he has and what he's missing (these
are the cards p2 has) and plays a card that he has the
equals-2n+1-match card to. Since there is not a 2n+1 card p2
cannot win on the first round: the most he can make is 2n. Player
1 now has n - 1 cards left in his hand and it is Player 2's turn.
Player 2 now has n cards still in his hand. Since each of his
cards contains a different number, each possible play requires a
specific card from player 1 on his next turn if p1 is to win.
However, since player 2 has one more card than player 1, p1 cannot have
the unique matches to every card in player 2's hand, so player 2 has at
least one card he can play so player 1 cannot win next
round. Note that he might have more than one possible play, but
it doesn't matter which one he takes. During his turn, player 2
will always have one more card than player 1, and thus will always have
a move which player 1 cannot match. Thus, in the worst case,
player 2 will have to play all his cards and win on the last hand.
The best case for player 2 is when player 1 draws all even or
all the odd cards. In this case p1 has no moves to stymie p2 on
his first move, so player 2 wins in round 1.
...which leads us to an intersting follow up question - there are two
possible deals which can lead to a perfect player 2 beating a perfect
player 1 after one round. What is the expected length of a game
with 2n card?
I'm new to this site, so let me know if posting interesting follow up question is against the rules, or gauche, or both.
re: More thorough solution
