Library / /67 of 84

, 2013

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Rahul has ten cards face-down, which consist of five distinct pairs of matching cards. During each move of his game, Rahul chooses one card to turn face-up, looks at it, and then chooses another to turn face-up and looks at it. If the two face-up cards match, the game ends. If not, Rahul flips both cards face-down and keeps repeating this process. Initially, Rahul doesn't know which cards are which. Assuming that he has perfect memory, find the smallest number of moves after which he can guarantee that the game has ended.

Solution

Solution:

Answer: 4 Label the 10 cards $a_{1}, a_{2}, \ldots, a_{5}, b_{1}, b_{2}, \ldots, b_{5}$ such that $a_{i}$ and $b_{i}$ match for $1 \leq i \leq 5$ .

First, we'll show that Rahul cannot always end the game in less than 4 moves, in particular, when he turns up his fifth card (during the third move), it is possible that the card he flips over is not one which he has yet encountered; consequently, he will not guarantee being able to match it, so he cannot guarantee that the game can end in three moves.

However, Rahul can always end the game in 4 moves. To do this, he can turn over 6 distinct cards in his first 3 moves. If we consider the 5 sets of cards $\{a_{1}, b_{1}\},\{a_{2}, b_{2}\},\{a_{3}, b_{3}\},\{a_{4}, b_{4}\},\{a_{5}, b_{5}\}$ , then by the pigeonhole principle, at least 2 of the 6 revealed cards must be from the same set. Rahul can then turn over those 2 cards on the fourth move, ending the game.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.