HMMT 二月 2024 · 冲刺赛 · 第 27 题
HMMT February 2024 — Guts Round — Problem 27
题目详情
- [14] A deck of 100 cards is labeled 1 , 2 , . . . , 100 from top to bottom. The top two cards are drawn; one of them is discarded at random, and the other is inserted back at the bottom of the deck. This process is repeated until only one card remains in the deck. Compute the expected value of the label of the remaining card.
解析
- [14] A deck of 100 cards is labeled 1 , 2 , . . . , 100 from top to bottom. The top two cards are drawn; one of them is discarded at random, and the other is inserted back at the bottom of the deck. This process is repeated until only one card remains in the deck. Compute the expected value of the label of the remaining card. Proposed by: Albert Wang 467 Answer: 8 Solution 1: Note that we can just take averages: every time you draw one of two cards, the EV of the resulting card is the average of the EVs of the two cards. This average must be of the form • • • • 2 · 1 + 2 · 2 + 2 · 3 + · · · + 2 · 100 • where the 2 s add up to 1 . Clearly, the cards further down in the deck get involved in one less layer of − 7 − 6 averaging, and therefore 1 through 72 are weighted 2 while the rest are weighted 2 . To compute 467 the average now, we just add it up to get . 8 n n − 1 Solution 2: We see that in a deck with 2 cards, that after repeating the process 2 times, that 1 each card has a chance of of remaining in the deck. This means that the average of the cards in the 2 n n − 1 deck doesn’t change between 2 by 2 cards. Thus, by repeating this process, we determine that n the expected value of the last card is the average of all cards whenever we start with 2 cards. 7 Suppose we instead start with 2 = 128 cards in the following order: 73 , 73 , 74 , 74 , . . . , 100 , 100 , 1 , 2 , 3 , . . . , 72 . Thus, after 28 steps, we will be left with the original configuration. Since a power of 2 cards are in the 467 deck, we expect that the final card will be the average of these numbers. This is . 8