Given a positive integer , call good if among at least of them are divisible by . Show that exists some positive integer such that among , there are at least good numbers.
Solution
1. Restate the problem and introduce the necessary notation:
Given a positive integer , we call good if among the binomial coefficients
at least of them are divisible by . We need to show that there exists some positive integer such that among , there are at least good numbers.
2. **Generalize the problem for arbitrary constants :**
We will prove that for any constants , there exists an integer such that for all , at least of the numbers are good, where a number is good if at least of its binomial coefficients are divisible by .
3. **Prove the statement for where is a prime:**
For a fixed integer and an integer , the -adic valuation of the binomial coefficient is given by:
where denotes the sum of the digits of in base . This valuation represents the number of carries when adding and in base .
4. Lemma:
Let be a positive integer. We can choose large enough so that when we consider the numbers as base- numbers, at least of them have at least digits among some nonempty subset of digits , where is any fixed integer.
5. Proof of the Lemma:
For large enough, we only need to consider the numbers which have at least digits in base when written without leading zeroes. We can choose such that the fraction of numbers with fewer than digits in base is as close to as needed.
Let and . The probability of a random -digit base- integer having fewer than digits among the elements of is bounded above by:
For large , the sum is a polynomial of degree in , denoted by . We need to show that for any , we can find such that:
This is equivalent to:
The left-hand side (LHS) is a polynomial in , while the right-hand side (RHS) is exponential in . For large enough , the RHS will dominate the LHS since .
6. Application of the Lemma:
As a corollary, we can find such that among the numbers , at least of them contain at least zeroes when written in base without leading zeroes, for some fixed integer .
7. Claim:
For large enough and , all such numbers are good. Consider a number which has at least zeroes and at least digits in base . The fraction of numbers such that and have at most carries during their addition can be made arbitrarily small for large and . If there are no carries at a digit in , then the corresponding positions in and must both be . This means that among the positions, at least of them must be in . The fraction of such numbers can be made arbitrarily small when is large.
8. **Conclusion for :**
For large enough and , all these numbers are good. This completes the proof for .
9. **Generalization to arbitrary :**
Suppose we have proved the statement for and , where and are coprime. We can find such that among , at least numbers are good for each . Let and be the sets of good numbers for and , respectively, with . The size of their intersection is at least .
For each number in the intersection, at least of the binomial coefficients are divisible by and at least are divisible by . The intersection of these sets of binomial coefficients is at least , and since and are coprime, these coefficients are divisible by . Thus, to prove the statement for , we can choose larger and for the statements and to achieve the desired result. This generalizes the proof for all .