HMMT 二月 2010 · TEAM1 赛 · 第 10 题

英文解析

10. Call an 2 n -digit base-10 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 number is special. (We allow leading zeros in 2 n -digit numbers).n
    (a) [ 20 ] The sequence p converges to a constant c . Find c .
    1 n
    Answer: We first claim that if a 2 n -digit number x has at least eight 0’s and at least eight
    1’s and the sum of its digits is even, then x is special.2
    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 they ∈ Y z ∈ Zbiggest element of the set with the bigger sum with the smallest element of the other set. Thistransposition always decreases the absolute value of the sum: in the worst case, a 9 from thebigger 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’sy ∈ Y z ∈ Zto Y , and we add the other elements of A to Z , then the two sets will balance, so x is special.
    (b) [ 45 ] Let q = p − c . There exists a unique positive constant r such that converges to anqn n nconstant d . Find r and d .r
    1 1
    Answer: r = , d = − 1 To get the next asymptotic term after the constant term of , we need
    4 2
    to consider what happens when the digit sum is even; we want to find the probability that sucha number isn’t balanced. We claim that the configuration that contributes the vast majority ofunbalanced 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 · = − ,
    2 2 4 nso r = and d = − 1.1
    To prove the claim, first note that the asymptotic probability that there are at most 4 digits that 4
    ( )
    1 noccur more than 10 times is asymptotically much smaller than , so we can assume that thereexist 5 digits that each occur at least 10 times. If any of those digits are consecutive, then the 2
    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 thisimplies 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 asum 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 numbersbefore it (so we have k − 4 , k − 2 , k, k + 3 for some k ), and pair them up such that one pair has asum that’s exactly one more than the other (i.e. pair k − 4 with k + 3 and k − 2 with k ). Sincewe 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 numbersare 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 thetransformation 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.
    Team Round A
    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 potentiallyswitching 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 isgood.
    So, we have shown that almost all non-good numbers come from having all numbers being evenwith a digit sum that is 2 mod 4, or the analogous case under the mapping x 7 → 9 − x . Thisformalizes the claim we made in the first paragraph, so r = and d = − 1, as claimed.1
    Team Round A4