HMMT 十一月 2025 · THM 赛 · 第 2 题

2. The 3 new marbles are not all the same color. There are 20 − 2 = 18 ways for this to happen. Triton’s marble colors will be either 4 green and 5 blue, or 5 green and 4 blue. Without loss of generality, we assume the former. Next turn, Triton will return a green marble to the bag, and he will repeatedly discard the marble he newly draws until he draws the sixth blue marble, at which point the ritual is complete. Only 1 out of the 10 marbles in the bag will be blue when Triton draws, meaning it will take him an expected 10 turns to get the sixth blue marble and complete the ritual. The total expected number of turns the ritual will take is therefore 10 10 10 2 18 91

• • • · 0 + · 10 = . 4 5 6 20 20 6 As an addendum, we now rigorously prove why the described strategy above is optimal. 333 0 . 6 234 0 . 3 0 . 2 144 135 225 0 . 4 0 . 6 0 . 4 0 . 3 0 . 1 0 . 1 045 126 0 . 1 0 . 4 036 The claimed optimal strategy leads to the transition graph shown, where abc denotes a state in which the number of marbles of each color are a , b , and c in some order (it does not matter which). Each state returns to the same state with the remaining probability (for example, state 234 returns to itself with probability 1 − 0 . 3 − 0 . 2 = 0 . 5.) In other words, the claimed expected number of turns required to complete the ritual from a given state are as follows: 036 135 045 144 234 333 126 225 0 10 10 25 / 2 27 / 2 91 / 6 5 / 2 21 / 2 We can prove optimality for this problem as follows: © 2025 HMMT • Suppose it is possible to improve upon any of the numbers in the above table using a certain ′ strategy. Look at the entry which we can decrease the most, say we can replace x with x = x − ∆. i i i We can simplify any mixed strategy at this state to some deterministic strategy without increasing its expected remoteness, since we know x − ∆ is a weighted average of the values obtained by i the possible deterministic strategies. • If this same strategy is applied on the weights given in the above table , then we claim it must P ′ also reduce x . Suppose it leads to x with probability w ; then x − ∆ = 1 + w x ≥ i j ij i ij j P P 1 + w ( x − ∆) = (1 + w x ) − ∆, where equality can only hold if all x for which w ̸ = 0 ij j ij j j ij ′ satisfy x = x − ∆. We can then apply the same argument to every such x , which eventually j j j leads to a contradiction because every node in this graph has a path of nonzero edges leading to

P • Thus, x < 1 + w x , which reduces verifying optimality to a finite case bash. It is straightfor- i ij j ward to consider, for each of the 8 states, the non-optimal choices of marble to remove and then verify that this inequality does not hold. The general solution can be described as linear programming duality.