HMMT 二月 2013 · 冲刺赛 · 第 5 题

HMMT February 2013 — Guts Round — Problem 5

[ 5 ] 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.

解析

[ 5 ] 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. Answer: 4 Label the 10 cards a , a , ..., a , b , b , ..., b such that a and b match for 1 ≤ i ≤ 5. 1 2 5 1 2 5 i i 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 , b } , { a , b } , { a , b } , { a , b } , { a , b } , then by 1 1 2 2 3 3 4 4 5 5 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.