Problem 6
Integers and are given, with . You play the following game against an evil wizard.
The wizard has cards; for each , there are two cards labeled . Initially, the wizard places all cards face down in a row, in unknown order.
You may repeatedly make moves of the following form: you point to any of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the chosen cards and then turns them back face-down. Then, it is your turn again.
We say this game is winnable if there exist some positive integer and some strategy that is guaranteed to win in at most moves, no matter how the wizard responds.
For which values of and is the game winnable?
Solution
The game is winnable if and only if .
First, suppose . Query the cards in positions {}, then {}, and so on, up to {}. Indeed, by taking the difference of the th and st query, we can deduce the value of the th card, for . (This is possible because the cards are flipped face up before they are re-shuffled,so even if two adjacent queries return the same set, one can still determine the th card. It is possible to solve the problem even without the flipped information, though.) If , this is more than cards, so we can find a matching pair.
For we remark the following:at each turn after the first, assuming one has not won,there are cards representing each of the values exactly once,such that the player has no information about the order of those cards.We claim that consequently the player cannot guarantee victory.Indeed, let denote this set of cards, and the other cards.The player will never win by picking only cards in or .Also, if the player selects some cards in and some cards in ,then it is possible that the choice of cards in is exactly the complementof those selected from ; the strategy cannot prevent this sincethe player has no information on . This implies the result.
The problems on this page are the property of the MAA's American Mathematics Competitions