PUMaC 2021 · 组合（B 组） · 第 6 题

PUMaC 2021 — Combinatorics (Division B) — Problem 6

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? 2 Proposed by: Austen Mazenko Answer: 12