HMMT 十一月 2025 · THM 赛 · 第 9 题
HMMT November 2025 — THM Round — Problem 9
题目详情
- Triton performs an ancient Neptunian ritual consisting of drawing red, green, and blue marbles from a bag. Initially, Triton has 3 marbles of each color, and the bag contains an additional 3 marbles of each color. Every turn, Triton picks one marble to put into the bag, then draws one marble uniformly at random from the bag (possibly the one he just discarded). The ritual is completed once Triton has 6 marbles of one color and 3 of another. Compute the expected number of turns the ritual will take, given that Triton plays optimally to minimize this value. © 2025 HMMT
解析
- Triton performs an ancient Neptunian ritual consisting of drawing red, green, and blue marbles from a bag. Initially, Triton has 3 marbles of each color, and the bag contains an additional 3 marbles of each color. Every turn, Triton picks one marble to put into the bag, then draws one marble uniformly at random from the bag (possibly the one he just discarded). The ritual is completed once Triton has 6 marbles of one color and 3 of another. Compute the expected number of turns the ritual will take, given that Triton plays optimally to minimize this value. Proposed by: Derek Liu 91 Answer: 6 Solution: Intuitively, an optimal strategy for Triton is for him put a marble of the least common color among his marbles into the bag every turn (with ties broken arbitrarily). This is because to complete the ritual, he must get rid of all the marbles of some color, then minimize the number of marbles of another color. The fastest way to do this is to remove a marble of the color that he wants to minimize at each turn, which would be the least common color. For completeness, we give a rigorous proof of optimality at the end of the solution. Thus, it is optimal to initially fix a color, then repeatedly put a marble of that color into the bag until Triton doesn’t have any marbles of that color left. Once this happens, he should then repeatedly discard the less common of the two remaining colors he has until the ritual is complete. Without loss of generality, suppose Triton chooses to get rid of his 3 red marbles first. After putting a red marble into the bag on his first turn, 4 of the 10 marbles in the bag will be red. When he draws a 4 marble back from the bag, there is a chance the marble is red (which means his turn did nothing), 10 6 and a chance the marble is not red (which means Triton now has 2 red marbles). The expected 10 10 number of turns before the latter scenario happens is . 6 Similarly, when Triton has 2 red marbles and returns one to the bag, the bag will have 5 red and 5 10 non-red marbles. We therefore expect it to take turns before he has only 1 red marble remaining. 5 10 Likewise, getting rid of the last red marble will take an expected turns. 4 © 2025 HMMT By symmetry, the 3 marbles that replaced Triton’s red marbles are equally likely to be any 3 of the 6 6 non-red marbles that were initially in the bag. There are = 20 possible cases and two scenarios to 3 consider: