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

PUMaC 2017 — Combinatorics (Division B) — Problem 6

The four faces of a tetrahedral die are labelled 0, 1, 2, and 3, and the die has the property that, when it is rolled, the die promptly vanishes, and a number of copies of itself appear equal to the number on the face the die landed on. For example, if it lands on the face labelled 0, it disappears. If it lands on the face labelled 1, nothing happens. If it lands on the face labelled 2 or 3, there will then be 2 or 3 copies of the die, respectively (including the original). Suppose the die and all its copies are continually rolled, and let p be the probability that they will all ⌊ ⌋ 10 eventually disappear. Find . p

解析

Let the desired probability be p , so that p satisfies 1 2 3 p = (1 + p + p + p ) . 4 This equation simplifies to 2 ( p + 2 p − 1)( p − 1) = 0 , √ √ so either p = − 1 ± 2 or p = 1. Since − 1 − 2 < 0, it can be rejected. Imagine that the dice-rolling process takes place in discrete units of time. Each minute, for example, every die is rolled, and the new copies are placed to the side to be rolled during the next minute. Let p be the probability any given die and all its copies vanish after k minutes. k √ We will show by induction on k that p < 2 − 1, so that p = 1 can also be rejected, and k √ √ we can conclude p = − 1 + 2. For the base case, p = 0 < 2 − 1. For the inductive step, 0 √ suppose p < 2 − 1. Then, k √ √ √ √ 1 1 2 3 2 3 p = (1 + p + p + p ) < (1 + ( − 1 + 2) + ( − 1 + 2) + ( − 1 + 2) ) = 2 − 1 . k +1 k k k 4 4 √ √ Thus, p = 2 − 1, and the answer is b 10( 2 + 1) c = 24 . Problem written by Matt Tyler