Maths Olympiad Prep

Library / /508 of 520

Number theory Difficulty 8.0 National olympiad, round 2 Prove it

Given a positive integer kk, call nn good if among (n0),(n1),(n2),...,(nn)\binom{n}{0},\binom{n}{1},\binom{n}{2},...,\binom{n}{n} at least 0.99n0.99n of them are divisible by kk. Show that exists some positive integer NN such that among 1,2,...,N1,2,...,N, there are at least 0.99N0.99N good numbers.

Solution

1. Restate the problem and introduce the necessary notation:
Given a positive integer k k , we call n n good if among the binomial coefficients
(n0),(n1),(n2),,(nn) \binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n}
at least 0.99n 0.99n of them are divisible by k k . We need to show that there exists some positive integer N N such that among 1,2,,N 1, 2, \ldots, N , there are at least 0.99N 0.99N good numbers.

2. **Generalize the problem for arbitrary constants 0C,D<1 0 \le C, D < 1 :**
We will prove that for any constants 0C,D<1 0 \le C, D < 1 , there exists an integer z z such that for all N>z N > z , at least DN DN of the numbers 1,2,,N 1, 2, \ldots, N are good, where a number n n is good if at least Cn Cn of its binomial coefficients are divisible by k k .

3. **Prove the statement for k=pm k = p^m where p p is a prime:**
For a fixed integer n n and an integer k k , the p p -adic valuation of the binomial coefficient (nk) \binom{n}{k} is given by:
vp((nk))=sp(k)+sp(nk)sp(n)p1 v_p\left(\binom{n}{k}\right) = \frac{s_p(k) + s_p(n - k) - s_p(n)}{p - 1}
where sp(x) s_p(x) denotes the sum of the digits of x x in base p p . This valuation represents the number of carries when adding k k and nk n - k in base p p .

4. Lemma:
Let z2 z \ge 2 be a positive integer. We can choose N N large enough so that when we consider the numbers 1,2,,N 1, 2, \ldots, N as base-z z numbers, at least DN DN of them have at least K K digits among some nonempty subset of digits S S , where K K is any fixed integer.

5. Proof of the Lemma:
For N N large enough, we only need to consider the numbers which have at least x x digits in base r r when written without leading zeroes. We can choose N N such that the fraction of numbers with fewer than x x digits in base r r is as close to 0 0 as needed.

Let q=Sz q = \frac{|S|}{z} and r=1q r = 1 - q . The probability of a random x x -digit base-z z integer having fewer than K K digits among the elements of S S is bounded above by:
qx+(x1)qx1r++(xK1)qxK+1rK1max(q,r)x[(x0)+(x1)++(xK1)] q^x + \binom{x}{1} q^{x-1} r + \cdots + \binom{x}{K-1} q^{x-K+1} r^{K-1} \le \max(q, r)^x \left[ \binom{x}{0} + \binom{x}{1} + \cdots + \binom{x}{K-1} \right]
For large x x , the sum (x0)+(x1)++(xK1) \binom{x}{0} + \binom{x}{1} + \cdots + \binom{x}{K-1} is a polynomial of degree K1 K-1 in x x , denoted by P(x) P(x) . We need to show that for any ϵ>0 \epsilon > 0 , we can find x x such that:
max(q,r)xP(x)<ϵ \max(q, r)^x P(x) < \epsilon
This is equivalent to:
P(x)ϵ<(1max(q,r))x \frac{P(x)}{\epsilon} < \left( \frac{1}{\max(q, r)} \right)^x
The left-hand side (LHS) is a polynomial in x x , while the right-hand side (RHS) is exponential in x x . For large enough x x , the RHS will dominate the LHS since 1max(q,r)>1 \frac{1}{\max(q, r)} > 1 .

6. Application of the Lemma:
As a corollary, we can find N N such that among the numbers 1,2,,N 1, 2, \ldots, N , at least DN DN of them contain at least K K zeroes when written in base p p without leading zeroes, for some fixed integer K K .

7. Claim:
For large enough K K and N N , all such numbers are good. Consider a number n n which has at least K K zeroes and at least d d digits in base p p . The fraction of numbers 0xn 0 \le x \le n such that x x and nx n - x have at most A A carries during their addition can be made arbitrarily small for large K K and d d . If there are no carries at a digit 0 0 in n n , then the corresponding positions in x x and nx n - x must both be 0 0 . This means that among the K K positions, at least KA K - A of them must be 0 0 in x x . The fraction of such numbers x x can be made arbitrarily small when K K is large.

8. **Conclusion for k=pm k = p^m :**
For large enough d d and K K , all these numbers are good. This completes the proof for k=pm k = p^m .

9. **Generalization to arbitrary k k :**
Suppose we have proved the statement for k=a k = a and k=b k = b , where a a and b b are coprime. We can find N N such that among 1,2,,N 1, 2, \ldots, N , at least DN DN numbers are good for each k k . Let S1 S_1 and S2 S_2 be the sets of good numbers for k=a k = a and k=b k = b , respectively, with SiDN |S_i| \ge DN . The size of their intersection is at least DN(1D)N=(2D1)N DN - (1 - D)N = (2D - 1)N .

For each number x x in the intersection, at least Cx Cx of the binomial coefficients are divisible by a a and at least Cx Cx are divisible by b b . The intersection of these sets of binomial coefficients is at least (2C1)x (2C - 1)x , and since a a and b b are coprime, these coefficients are divisible by ab ab . Thus, to prove the statement for k=ab k = ab , we can choose larger C C and D D for the statements k=a k = a and k=b k = b to achieve the desired result. This generalizes the proof for all kN k \in \mathbb{N} .

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.