HMMT 二月 2012 · 冲刺赛 · 第 36 题
HMMT February 2012 — Guts Round — Problem 36
题目详情
- [ 23 ] Maria is hopping up a flight of stairs with 100 steps. At every hop, she advances some integer number of steps. Each hop she makes has fewer steps. However, the positive difference between the length of consecutive hops decreases. Let P be the number of distinct ways she can hop up the stairs. ⌊ ⌋ 23 √ Find lower and upper bounds L and U for P . If 0 < L ≤ P ≤ U , your score will be . U/L Otherwise, your score will be 0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TH 15 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 11 FEBRUARY 2012— GUTS ROUND School Team Team ID#
解析
- [ 23 ] Maria is hopping up a flight of stairs with 100 steps. At every hop, she advances some integer number of steps. Each hop she makes has fewer steps. However, the positive difference between the length of consecutive hops decreases. Let P be the number of distinct ways she can hop up the stairs. ⌊ ⌋ 23 √ Find lower and upper bounds L and U for P . If 0 < L ≤ P ≤ U , your score will be . U/L Otherwise, your score will be 0. Answer: 6922 Consider the sequence of hops backwards. It is an increasing sequence where the first finite differences are increasing, so all the second finite differences are all positive integers. Furthermore, given positive integers a, e (representing the initial value and initial first finite difference), 0 and a sequence of positive integers e , e , . . . , e , representing the second finite differences, we obtain a 1 2 k ∑ i − 2 sequence of k +2 integers satisfying our constraints where the i -th term is equal to a + ( i − j − 1) e . j j =0 ∑ k ( j +1)( j +2) The sum of these values is equal to ( k + 2) a + e . The number of sequences of length k − j j =0 2 ∑ k ( j +1)( j +2) k + 2 with sum 100 is then the number of positive integer solutions to ( k + 2) a + e = k − j j =0 2 100 in a, e , . . . , e . 0 k We can now approximate a count of the total number of solutions by caseworking over the possible values of k . First, we must consider all sequences of length 1 or 2; it easy to see that there are 1 and 49 of these, respectively. Otherwise, we want to consider the following equations: x + 3 x + 3 x = 100 , 1 2 3 x + 4 x + 3 x + 6 x = 100 , 1 2 3 4 x + 5 x + 3 x + 6 x + 10 x = 100 , 1 2 3 4 5 x + 6 x + 3 x + 6 x + 10 x + 15 x = 100 , 1 2 3 4 5 6 x + 7 x + 3 x + 6 x + 10 x + 15 x + 21 x = 100 , 1 2 3 4 5 6 7 x + 8 x + 3 x + 6 x + 10 x + 15 x + 21 x + 28 x = 100 . 1 2 3 4 5 6 7 8 (Any larger values of k will yield equations with no solutions, as the sum of the coefficients will be greater than 100 in all of these.) We can compute the number of solutions to the last equation easily: there are 8. For the remaining 5 equations, we can use the following observation to estimate the number of solutions. Suppose we wanted to count the number of positive integer solutions to Guts ∑ k c x = n , where c = 1. This is equivalent to finding the number of nonnegative integer solutions i i i i =1 ∑ ∑ k k to c x = n − c , which is also equivalent to finding the number of nonnegative integer i i i i =1 i =1 ∑ ∑ ∑ ′ k k k n ′ solutions to c x ≤ n − c . Let n = n − c . Each x can take values from 0 to , i i i i i i =2 i =1 i =1 c i ′ k − 1 ( n ) Q giving about choices. Of course, not all of these choices work; we try to estimate the probability k c i i =2 that one does. We can think of a random selection of x as approximated by choosing X uniformly i i ∑ ′ k n from [0 , 1], then setting x = X · . The condition would then be X ≤ 1. The probability i i k c i =2 i ′ k − 1 ( n ) 1 Q of this occuring is , so an approximate number of solutions would be . We can use k ( k − 1)! ( k − 1)! c i i =2 ′ these values to get a lower bound of around 4000, and we can also use n instead of n for a reasonable upper bound of 16000. Guts