PUMaC 2023 · 组合（B 组） · 第 3 题
PUMaC 2023 — Combinatorics (Division B) — Problem 3
题目详情
- Alien Connor starts at (0 , 0) and walks around on the integer lattice. Specifically, he takes one step of length one in a uniformly random cardinal direction every minute, unless his previous four steps were all in the same direction in which case he randomly picks a new direction to step in. Every time he takes a step, he leaves toxic air on the lattice point he just left, and the toxic cloud remains there for 150 seconds. After taking 5 steps in total, the probability that a he has not encountered his own toxic waste can be written as for relatively prime positive b integers a, b . Find a + b .
解析
- Alien Connor starts at (0 , 0) and walks around on the integer lattice. Specifically, he takes one step of length one in a uniformly random cardinal direction every minute, unless his previous four steps were all in the same direction in which case he randomly picks a new direction to step in. Every time he takes a step, he leaves toxic air on the lattice point he just left, and the toxic cloud remains there for 150 seconds. After taking 5 steps in total, the probability that a he has not encountered his own toxic waste can be written as for relatively prime positive b integers a, b . Find a + b . Proposed by Ben Zenker Answer: 505 Due to parity, we can see that the only way he can encounter his own toxic waste is by walking directly backwards. The toxic waste stays in the air for 2 full step sizes, but disappears after 1 3, and there’s no way to take two more steps and return to where you started. First, suppose his first four steps are all in the same direction, which happens with probability 1 2 . Then, the probability he avoids his own toxic waste with his last step is , contributing a 3 4 3 2 1 probability of · . Otherwise, we see the probability he makes it four steps without hitting 3 3 4 3 3 1 13 is own toxic waste while also not going the same direction every step is − = . 3 4 4 32 Conditioned on this, we see the probability his last step also avoids the toxic air is again 3 2 1 13 3 4 117 121 . Thus, our final answer is · + · = + = , giving a final answer of 3 4 3 4 32 4 3 · 128 3 · 128 384 121 + 384 = 505.