HMMT 十一月 2025 · 冲刺赛 · 第 35 题
HMMT November 2025 — Guts Round — Problem 35
题目详情
- [20] Derek has a 45 × 45 grid of cells. Initially, every cell in the grid is uncolored. Every second, he picks one of the remaining uncolored cells uniformly at random and colors it in. He stops once there exist two distinct colored cells that share an edge. Estimate the expected number of seconds before Derek stops. 3 / 4 Submit a real number E . If the correct answer is A , you will receive ⌈ max(0 , 20 − 7 | E − A | ) ⌉ points.
解析
- [20] Derek has a 45 × 45 grid of cells. Initially, every cell in the grid is uncolored. Every second, he picks one of the remaining uncolored cells uniformly at random and colors it in. He stops once there exist two distinct colored cells that share an edge. Estimate the expected number of seconds before Derek stops. 3 / 4 Submit a real number E . If the correct answer is A , you will receive ⌈ max(0 , 20 − 7 | E − A | ) ⌉ points. Proposed by: Derek Liu Answer: ≈ 29 . 267 Solution: Let n = 45. As a heuristic, after m cells are shaded, each pair of adjacent cells has around a 2 2 2 ( m/n ) probability of being colored. There are approximately 2 n such pairs, so the expected number 2 2 2 2 2 of pairs that are colored is 2 n ( m/n ) = 2 m /n . Since we stop after one such pair exists, we might √ expect this value to be 1, so m ≈ m/ 2 ≈ 32, which attains 6 points. 2 n ( n − 1) 4 For a much better estimate, let X be the number of seconds that elapse. Let p = = ≈ 2 n n ( n +1) ( ) 2 0 . 002 be the probability that two random distinct cells are adjacent. Assuming that this probability is independent for each pair (which is reasonable as this probability is very small), the probability that k ( k − 1) / 2 none of the first k colored cells are pairwise adjacent is (1 − p ) . This is the probability that X > k , so ∞ ∞ X X k ( k − 1) / 2 E [ X ] ≈ Pr[ X > k ] = (1 − p ) . k =0 k =0 We can approximate this sum with an integral: Z Z ∞ ∞ 2 x ( x − 1) / 2 − 1 / 8 ( x − 1 / 2) / 2 E [ X ] ≈ (1 − p ) d x = (1 − p ) (1 − p ) d x. − 1 / 2 − 1 / 2 − 1 / 8 Note that (1 − p ) is extremely close to 1, so we ignore that factor. Let c = ln(1 − p ) ≈ − p . By shifting, this integral is Z Z ∞ ∞ 2 2 x / 2 cx / 2 (1 − p ) d x = e d x. − 1 − 1 √ Performing a u -substitution of u = x − c , this integral becomes Z ∞ 2 1 − x / 2 √ e d x. √ − c − c p R √ 2 ∞ − x We know that e d x = π/ 2. Since − c ≈ 0, 0 r Z Z ∞ ∞ √ √ 2 2 2 π − x / 2 − 0 / 2 − x / 2 e d x ≈ − ce + e d x = − c + , √ 2 − c 0 so our estimation becomes r √ √ 1 π 1 π √ − c + = 1 + √ · . 2 2 − c − c Observe that r 1 1 n ( n + 1) n + 0 . 5 91 √ ≈ = ≈ = , √ p 4 2 4 − c p while π/ 2 ≈ 5 / 4 (as π ≈ 25 / 8), so our estimate is 91 5 1 + · ≈ 29 . 44 , 4 4 © 2025 HMMT which gets 19 points (possibly 18, depending on the numerical estimations we use). p It turns out that π/ 2 is actually around 1 . 253, and our estimate should be around 29 . 5 as a result. The reason we have an overestimate is that our independence assumptions work better when we assume cells are being colored with replacement (i.e., the same cell may be selected several times); the effect this has on p is negligible. Thus, it remains to estimate the number of distinct cells that are selected when 29 . 5 cells with replacement are selected on average. We assume the probability of a cell being selected 3 or more times is negligible, so the number of distinct cells is simply 29 . 5 minus the number of pairs of selected cells which are the same. Each pair of selected cells has a 1 / 2025 probability of being the same, and there are (29 . 5 · 28 . 5) / 2 such pairs, so by linearity of expectation, our new estimate is (29 . 5 · 28 . 5) / 2 ≈ 29 . 29 ,