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

英文解析

5. [ 5 ] Rahul has ten cards face-down, which consist of five distinct pairs of matching cards. During eachmove of his game, Rahul chooses one card to turn face-up, looks at it, and then chooses another toturn face-up and looks at it. If the two face-up cards match, the game ends. If not, Rahul flips bothcards 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 guaranteethat 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, whenhe turns up his fifth card (during the third move), it is possible that the card he flips over is not onewhich he has yet encountered; consequently, he will not guarantee being able to match it, so he cannotguarantee 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 inhis 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 thenturn over those 2 cards on the fourth move, ending the game.