HMMT 二月 2010 · TEAM2 赛 · 第 10 题
HMMT February 2010 — TEAM2 Round — Problem 10
题目详情
- Call an 2 n -digit number special if we can split its digits into two sets of size n such that the sum of the numbers in the two sets is the same. Let p be the probability that a randomly-chosen 2 n -digit n number is special (we will allow leading zeros in the number). (a) [ 25 ] The sequence p converges to a constant c . Find c . n q n (b) [ 30 ] Let q = p − c . There exists a unique positive constant r such that converges to a n n n r constant d . Find r and d . Page 1 of 1
解析
- Call an 2 n -digit number special if we can split its digits into two sets of size n such that the sum of the numbers in the two sets is the same. Let p be the probability that a randomly-chosen 2 n -digit n number is special (we will allow leading zeros in the number). (a) [ 25 ] The sequence p converges to a constant c . Find c . n 1 Answer: We first claim that if a 2 n -digit number x has at least eight 0’s and at least eight 2 1’s and the sum of its digits is even, then x is special. Let A be a set of eight 0’s and eight 1’s and let B be the set of all the other digits. We split ∑ ∑ b arbitrily into two sets Y and Z of equal size. If | y − z | > 8, then we swap the y ∈ Y z ∈ Z biggest element of the set with the bigger sum with the smallest element of the other set. This transposition always decreases the absolute value of the sum: in the worst case, a 9 from the bigger set is swapped for a 0 from the smaller set, which changes the difference by at most 18. ∑ ∑ Therefore, after a finite number of steps, we will have | y − z | ≤ 8. y ∈ Y z ∈ Z Note that this absolute value is even, since the sum of all the digits is even. Without loss of ∑ ∑ generality, suppose that y − z is 2 k , where 0 ≤ k ≤ 4. If we add k 0’s and 8 − k 1’s y ∈ Y z ∈ Z to Y , and we add the other elements of A to Z , then the two sets will balance, so x is special. 3 See http://www.artofproblemsolving.com/Forum/weblog_entry.php?p=1263378 . 4 See http://en.wikipedia.org/wiki/Lagrange_polynomial . Team Round B q n (b) [ 30 ] Let q = p − c . There exists a unique positive constant r such that converges to a n n n r constant d . Find r and d . 1 1 Answer: ( , − 1) To get the next asymptotic term after the constant term of , we need to 4 2 consider what happens when the digit sum is even; we want to find the probability that such a number isn’t balanced. We claim that the configuration that contributes the vast majority of unbalanced numbers is when all numbers are even and the sum is 2 mod 4, or such a configuration ( ) ( ) 2 n n 1 1 1 with all numbers increased by 1. Clearly this gives q being asymptotic to − · 2 · = − , n 2 2 4 1 so r = and d = − 1. 4 To prove the claim, first note that the asymptotic probability that there are at most 4 digits that ( ) n 1 occur more than 10 times is asymptotically much smaller than , so we can assume that there 2 exist 5 digits that each occur at least 10 times. If any of those digits are consecutive, then the digit sum being even implies that the number is balanced (by an argument similar to part (a)). So, we can assume that none of the numbers are consecutive. We would like to say that this implies that the numbers are either 0 , 2 , 4 , 6 , 8 or 1 , 3 , 5 , 7 , 9. However, we can’t quite say this yet, as we need to rule out possibilities like 0 , 2 , 4 , 7 , 9. In this case, though, we can just pair 0 and 7 up with 2 and 4; by using the same argument as in part (a), except using 0 and 7 both (to get a sum of 7) and 2 and 4 both (to get a sum of 6) to balance out the two sets at the end. In general, if there is ever a gap of size 3, consider the number right after it and the 3 numbers before it (so we have k − 4 , k − 2 , k, k + 3 for some k ), and pair them up such that one pair has a sum that’s exactly one more than the other (i.e. pair k − 4 with k + 3 and k − 2 with k ). Since we again have pairs of numbers whose sums differ by 1, we can use the technique from part (a) of balancing out the sets at the end. So, we can assume there is no gap of size 3, which together with the condition that no two numbers are adjacent implies that the 5 digits are either 0 , 2 , 4 , 6 , 8 or 1 , 3 , 5 , 7 , 9. For the remainder of the solution, we will deal with the 0 , 2 , 4 , 6 , 8 case, since it is symmetric with the other case under the transformation x 7 → 9 − x . If we can distribute the odd digits into two sets S and S such that (i) the differense in sums of 1 2 S and S is small; and (ii) the difference in sums of S and S , plus the sum of the even digits, 1 2 1 2 is divisible by 4, then the same argument as in part (a) implies that the number is good. In fact, if there are any odd digits, then we can use them at the beginning to fix the parity mod 4 (by adding them all in such that the sums of the two sets remain close, and then potentially switching one with an even digit). Therefore, if there are any odd digits then the number is good. Also, even if there are no odd digits, if the sum of the digits is divisible by 4 then the number is good. So, we have shown that almost all non-good numbers come from having all numbers being even with a digit sum that is 2 mod 4, or the analogous case under the mapping x 7 → 9 − x . This 1 formalizes the claim we made in the first paragraph, so r = and d = − 1, as claimed. 4 Team Round B