HMMT 二月 2024 · COMB 赛 · 第 7 题
HMMT February 2024 — COMB Round — Problem 7
题目详情
- There is a grid of height 2 stretching infinitely in one direction. Between any two edge-adjacent cells 1 of the grid, there is a door that is locked with probability independent of all other doors. Philip 2 starts in a corner of the grid (in the starred cell). Compute the expected number of cells that Philip can reach, assuming he can only travel between cells if the door between them is unlocked. · · · · · · · · ·
解析
- There is a grid of height 2 stretching infinitely in one direction. Between any two edge-adjacent cells 1 of the grid, there is a door that is locked with probability independent of all other doors. Philip 2 starts in a corner of the grid (in the starred cell). Compute the expected number of cells that Philip can reach, assuming he can only travel between cells if the door between them is unlocked. · · · · · · · · · Proposed by: Jacob Paltrowitz 32 Answer: 7 Solution: For clarity, we will number our grid, with (0,0) being the corner that Philip starts in, and the grid stretching in the positive x direction, i.e. all elements of the grid are of the form ( x, y ) , with y ∈ { 0 , 1 } and x ∈ N . We will use recursion and casework. Let A be the expected number of reachable cells given that the door between (0 , 0) and (0 , 1) is unlocked, and B be the expected number of cells given that door is 1 A + B closed. Since that door is locked of the time, our answer is . 2 2 We can write recurrence relations by considering the different configurations of the doors in the first 4 cells. For the sake of writing, let W be the (0 , 0) − (0 , 1) door, X be the (0 , 0) − (1 , 0) door, Y be the (0 , 1) − (1 , 1) door, and Z be the (1 , 0) − (1 , 1) door. Let’s start with the case where W is unlocked and compute A : Y Y Y W W W ? ? ? X X X Case 1: W is unlocked. Shaded cells represent inaccessible cells, and the arrows show Philip’s movements between cells. 1 • If X, Y are both locked, then Philip can reach exactly 2 rooms. This occurs with probability . 4 • If both of X, Y are unlocked, then we have exactly the same case of A , except with the ability to 1 reach two extra cells. This occurs with probability . 4 • If exactly one of X, Y are unlocked, we have back to the original case, except with the ability to 1 access two more cells, which occurs with probability . 2 So, we get the equation: ( ) 1 1 1 A + B A = (2) + ( A + 2) + + 2 4 4 2 2 Now, let’s consider when W is locked. Y Y Y W W W ? ? ? X X X Case 2: W is locked. 1 • If X is locked, Philip can only reach one cell. This occurs with probability . 2 • If X is unlocked and Y is locked, we have exactly the original problem, except with the ability to 1 reach one more cell. This occurs with probability . 4 • In the case where X is unlocked and Y is unlocked, this is the same as the original configuration, except with the ability to reach one extra cell (the start) and possibly the cell at (0 , 1) . Now, let’s compute the probability that Philip can reach (0 , 1) in this case. This is the probability that Philip can reach (1 , 1) since Y is unlocked. We can compute that the probability that Philip can reach (1 , 1) from (1 , 0) is equal to ∞ ∑ 1 3 n +1 2 n =0 by looking at the minimum distance Philip has to go to the right before getting back to (1 , 1) . 4 4 This is a geometric series with sum . So, in this case, on average Philip can reach 1 + more 7 7 1 cells than the original case. This case occurs with probability . 4 So, we can write the equation: ( ) ( ) 1 1 A + B 1 A + B 4 B = (1) + + 1 + + 1 + 2 4 2 4 2 7 32 40 24 A + B Solving the system of these two linear equations, we get A = , B = and = . 7 7 2 7