HMMT 二月 2014 · COMB 赛 · 第 9 题
HMMT February 2014 — COMB Round — Problem 9
题目详情
- There is a heads up coin on every integer of the number line. Lucky is initially standing on the zero point of the number line facing in the positive direction. Lucky performs the following procedure: he looks at the coin (or lack thereof) underneath him, and then, • If the coin is heads up, Lucky flips it to tails up, turns around, and steps forward a distance of one unit. • If the coin is tails up, Lucky picks up the coin and steps forward a distance of one unit facing the same direction. • If there is no coin, Lucky places a coin heads up underneath him and steps forward a distance of one unit facing the same direction. He repeats this procedure until there are 20 coins anywhere that are tails up. How many times has Lucky performed the procedure when the process stops? 2 2
解析
- There is a heads up coin on every integer of the number line. Lucky is initially standing on the zero point of the number line facing in the positive direction. Lucky performs the following procedure: he looks at the coin (or lack thereof) underneath him, and then, • If the coin is heads up, Lucky flips it to tails up, turns around, and steps forward a distance of one unit. • If the coin is tails up, Lucky picks up the coin and steps forward a distance of one unit facing the same direction. • If there is no coin, Lucky places a coin heads up underneath him and steps forward a distance of one unit facing the same direction. He repeats this procedure until there are 20 coins anywhere that are tails up. How many times has Lucky performed the procedure when the process stops? k Answer: 6098 We keep track of the following quantities: Let N be the sum of 2 , where k ranges over all nonnegative integers such that position − 1 − k on the number line contains a tails-up coin. k Let M be the sum of 2 , where k ranges over all nonnegative integers such that position k contains a tails-up coin. We also make the following definitions: A ”right event” is the event that Lucky crosses from the negative integers on the number line to the non-negative integers. A ”left event” is the event that Lucky crosses from the non-negative integers on the number line to the negative integers. We now make the following claims: (a) Every time a right event or left event occurs, every point on the number line contains a coin. (b) Suppose that n is a positive integer. When the n th left event occurs, the value of M is equal to n . When the n th right event occurs, the value of N is equal to n . k (c) For a nonzero integer n , denote by ν ( n ) the largest integer k such that 2 divides n . The number 2 of steps that elapse between the ( n − 1)st right event and the n th left event is equal to 2 ν ( n ) + 1. 2 The number of steps that elapse between the n th left event and the n th right event is also equal to 2 ν ( n ) + 1. (If n − 1 = 0, then the “( n − 1)st right event” refers to the beginning of the 2 simulation.) 10 (d) The man stops as soon as the 1023rd right event occurs. (Note that 1023 = 2 − 1.) In other words, Lucky is keeping track of two numbers M and N , which are obtained by interpreting the coins on the number line as binary strings, and alternately incrementing each of them by one. We will prove claim 2; the other claims follow from very similar reasoning and their proofs will be omitted. Clearly, left and right events alternate. That is, a left event occurs, then a right event, then a left event, and so on. So it’s enough to prove that, between each right event and the following left event, the value of M is incremented by 1, and that between each left event and the following right event, the value of N is incremented by 1. We will show the first statement; the second follows from symmetry. Suppose that a right event has just occurred. Then, by claim 1, every space on the number line cotnains a coin. So, there is some nonnegative integer ℓ for which positions 0 , . . . , ℓ − 1 on the number line contain a tails up coin, and position ℓ contains a heads up coin. Since Lucky is standing at position 0 facing rightward, the following sequence of steps will occur: (a) Lucky will take ℓ steps to the right, eventually reaching position ℓ . During this process, he will pick up the coins at positions 0 , . . . , ℓ − 1. (b) Then, Lucky turn the coin at position ℓ to a tails up coin and turn around. (c) Finally, Lucky will take ℓ + 1 steps to the left, eventually reaching position − 1 (at which point a left event occurs). During this process, he will place a heads up coin at positions 0 , . . . , ℓ − 1. During this sequence, the tails up coins at positions 0 , . . . , ℓ − 1 have been changed to heads up coins, and the heads up coin at position ℓ has been changed to a tails up coin. So the value of M has been incremented by ℓ − 1 ∑ ℓ i 2 − 2 = 1 i =0 as desired. Now, it remains to compute the answer to the question. By claims 3 and 4, the total number of steps taken by the simulation is 1023 ∑ 2 (2 ν ( n ) + 1) . 2 n =1 This can be rewritten as 1023 ∑ 4 ν ( n ) + 2 · 1023 = 4 ν (1023!) + 2046 . 2 2 n =1 We can compute ν (1023!) = 1013 using Legendre’s formula for the highest power of 2 dividing a 2 factorial. This results in the final answer 6098. 2 2