返回题库

HMMT 十一月 2019 · 冲刺赛 · 第 9 题

HMMT November 2019 — Guts Round — Problem 9

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. [7] Let p be a real number between 0 and 1. Jocelin has a coin that lands heads with probability p and tails with probability 1 − p ; she also has a number written on a blackboard. Each minute, she flips the coin, and if it lands heads, she replaces the number x on the blackboard with 3 x + 1; if it lands tails she replaces it with x/ 2. Given that there are constants a, b such that the expected value of the value written on the blackboard after t minutes can be written as at + b for all positive integers t , compute p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2019, November 9, 2019 — GUTS ROUND Organization Team Team ID#
解析
  1. [7] Let p be a real number between 0 and 1. Jocelin has a coin that lands heads with probability p and tails with probability 1 − p ; she also has a number written on a blackboard. Each minute, she flips the coin, and if it lands heads, she replaces the number x on the blackboard with 3 x + 1; if it lands tails she replaces it with x/ 2. Given that there are constants a, b such that the expected value of the value written on the blackboard after t minutes can be written as at + b for all positive integers t , compute p . Proposed by: Carl Schildkraut 1 Answer: 5 If the blackboard has the value x written on it, then the expected value of the value after one flip is f ( x ) = p (3 x − 1) + (1 − p ) x/ 2 . Because this expression is linear, we can say the same even if we only know the blackboard’s initial expected value is x . Therefore, if the blackboard value is x at time 0, then after t minutes, the 0 t 2 expected blackboard value is f ( x ). We are given that x , f ( x ) , f ( x ) , . . . is an arithmetic sequence, 0 0 0 0 so for there to be a constant difference, we must have f ( x ) = x + c for some c . This only occurs when 3 p + (1 − p ) / 2 = 1, so p = 1 / 5.