PUMaC 2010 · 组合（B 组） · 第 6 题
PUMaC 2010 — Combinatorics (Division B) — Problem 6
题目详情
- A regular pentagon is drawn in the plane, along with all its diagonals. All its sides and diagonals are extended infinitely in both directions, dividing the plane into regions, some of which are unbounded. An ant starts in the center of the pentagon, and every second, the ant randomly chooses one of the edges of the region it’s in, with an equal probability of choosing each edge, and crosses that edge into another region. If the ant enters an unbounded region, it explodes. After first leaving the central region of the pentagon, let x be the expected number of times the ant re-enters the central region before it explodes. Find the closest integer to 100 x .
解析
- A regular pentagon is drawn in the plane, along with all its diagonals. All its sides and diagonals are extended infinitely in both directions, dividing the plane into regions, some of which are unbounded. An ant starts in the center of the pentagon, and every second, the ant randomly chooses one of the edges of the region it’s in, with an equal probability of choosing each edge, and crosses that edge into another region. If the ant enters an unbounded region, it explodes. After first leaving the central region of the pentagon, let x be the expected number of times the ant re-enters the central region before it explodes. Find the closest integer to 100 x . Answer: 200 Solution: Color the regions black and white like a chessboard, where the center region is white, so that no two regions sharing an edge are the same color. The ant moves alternately between black and white regions, so we can consider the ant’s movement two steps at a time, essentially ignoring the black regions. The white regions consist of the central region, five similar “edge” sections, and some un- bounded regions. Let C be the expected number of times the ant re-enters the central region, starting from the central region, and let E be the expected number of times the ant re-enters the central region, starting from one of the edge regions (by symmetry, E is the same for all five edge regions). If the ant starts in the central region, there is a 1/3 probability it returns to the central region in 2 steps, otherwise it moves to an edge region. If the ant starts in an edge region, there is a 2 / 9 probability it moves to the center in 2 steps, a 5 / 9 probability it returns to an edge in 2 steps, and a 2 / 9 chance it explodes within the next 2 steps. Therefore, 3 1 2 C = (1 + C ) + E 3 3 2 5 E = (1 + C ) + E 9 9 Solving yields C = 2, E = 3 / 2, so x = C = 2, and therefore the answer is 200 .