PUMaC 2021 · 组合（A 组） · 第 4 题

PUMaC 2021 — Combinatorics (Division A) — Problem 4

There are n lilypads in a row labeled 1 , 2 , ..., n from left to right. Fareniss the Frog picks a lilypad at random to start on, and every second she jumps to an adjacent lilypad; if there are two such lilypads, she is twice as likely to jump to the right as to the left. After some finite number of seconds, there exists two lilypads A and B such that Fareniss is more than 1000 times as likely to be on A as she is to be on B . What is the minimal number of lilypads n such that this situation must occur?

解析

There are n lilypads in a row labeled 1 , 2 , ..., n from left to right. Fareniss the Frog picks a lilypad at random to start on, and every second she jumps to an adjacent lilypad; if there are two such lilypads, she is twice as likely to jump to the right as to the left. After some finite number of seconds, there exists two lilypads A and B such that Fareniss is more than 1000 times as likely to be on A as she is to be on B . What is the minimal number of lilypads n such that this situation must occur? Proposed by: Austen Mazenko Answer: 12 This situation is modeled by a Markov chain; calculating the equilibrium distribution for each n − 2 n − 3 n − 3 n − 3 n − 3 n − 2 state gives the probabilities as (1 / 3) , (1 / 3) , 2 ∗ (1 / 3) , ... 2 ∗ (1 / 3) , (2 / 3) . n − 2 n − 3 n − 2 The maximum is (2 / 3) and the minimum is (1 / 3) , and their ratio is 2 × 3. This must exceed 1000, so n must be at least 12.