HMMT 十一月 2024 · 团队赛 · 第 6 题

HMMT November 2024 — Team Round — Problem 6

[45] There are 5 people who start with 1 , 2 , 3 , 4 , and 5 cookies, respectively. Every minute, two different people are chosen uniformly at random. If they have a and b cookies and a ̸ = b , the person with more cookies eats | a − b | of their own cookies. If a = b , the minute still passes with nothing happening. Compute the expected number of minutes until all 5 people have an equal number of cookies.

解析

[45] There are 5 people who start with 1, 2, 3, 4, and 5 cookies, respectively. Every minute, two different people are chosen uniformly at random. If they have a and b cookies and a ̸ = b , the person with more cookies eats | a − b | of their own cookies. If a = b , the minute still passes with nothing happening. Compute the expected number of minutes until all 5 people have an equal number of cookies. Proposed by: Jacob Paltrowitz Answer: 25 / 3 Solution: Each person’s cookie count can never increase or go below 1, so in order for everyone to have the same number of cookies, everyone must have exactly 1 cookie. The only time the number of people with exactly 1 cookie increases is when one person with exactly 1 cookie and one person with more than 1 cookie are selected. Suppose there are currently k people with exactly 1 cookie. Then there are k (5 − k ) ways for the above to happen. There are 10 possible pairs of people that could be selected, so the expected number of 10 minutes before the number of people with exactly 1 cookie increases to k + 1 is . Initially, there k (5 − k ) is one person with exactly one cookie, and the process ends when all five people do; by linearity of expectation, the total expected time is the sum of the expected times to get from k to k + 1 for k = 1, 2, 3, and 4: 10 10 10 10 25