PUMaC 2023 · 组合（B 组） · 第 2 题

PUMaC 2023 — Combinatorics (Division B) — Problem 2

Amir enters Fine Hall and sees the number 2 written on a blackboard. Amir can perform the following operation: he flips a coin, and if it is heads, he replaces the number x on the blackboard with 3 x + 1; otherwise, he replaces x with ⌊ x/ 3 ⌋ . If Amir performs this operation m four times, let denote the expected number of times that he writes the digit 1 on the n blackboard, where m, n are relatively prime positive integers. Find m + n .

解析

Amir enters Fine Hall and sees the number 2 written on a blackboard. Amir can perform the following operation: he flips a coin, and if it is heads, he replaces the number x on the blackboard with 3 x + 1; otherwise, he replaces x with ⌊ x/ 3 ⌋ . If Amir performs this operation m four times, let denote the expected number of times that he writes the digit 1 on the n blackboard, where m, n are relatively prime positive integers. Find m + n . Proposed by Sunay Joshi Answer: 27 There are only two numbers that can appear in four operations that contain the digit 1, namely 1 and 13. The sequences of flips that contain the digit 1 are: HTTH (one 1), TTTH (one 1), TTHT (one 1), TTHH (one 1), THTT (one 1), THTH (two 1s), THHT (two 1s), and THHH 1 11 (two 1s). The expected value is therefore (1 + 1 + 1 + 1 + 1 + 2 + 2 + 2) = and our answer 16 16 is 11 + 16 = 27.