Given a positive integer $k$, call $n$ good if among $$\binom{n}{0},\binom{n}{1},\binom{n}{2},...,\binom{n}{n}$$at least $0.99n$ of them are divisible by $k$. Show that exists some positive integer $N$ such that among $1,2,...,N$, there are at least $0.99N$ good numbers.
Problem
Source: 2018 China TST Day 2 Q2
Tags: number theory, binomial coefficients, Divisibility
02.01.2018 11:05
Legendre says that for all prime $p$ and nonnegative integer $n$, $$\nu_p(n!) = \frac{n-s_p(n)}{p-1},$$where $s_p(n)$ is the sum of digits of $n$ in base $p$. Therefore, for all prime $p$ and nonnegative integers $m,n$, $$\nu_p \binom{m+n}{n} = \frac{s_p(m)+s_p(n)-s_p(m+n)}{p-1}$$which is equal to the number of carries when adding $m$ and $n$ in mod $p$. Hence for $k=\prod p_i^{\alpha_i}$ to not divide $\binom{m+n}{n}$, there must be a prime $p_i$ such that the summation of $m$ and $n$ in base $p_i$ must have at most $\alpha_i-1$ carries. Now the (non-rigorous) idea is just that it's actually very likely that there are carries: the density of $(m,n)$ for which $m+n$ has at most $\alpha_i-1$ carries in base $p_i$ is $0$, so summing over $p$, the density of $(m,n)$ for which $k=\prod p_i^{\alpha_i}$ does not divide $\binom{m+n}{n}$ is also $0$, so we can find a big enough $N$.
05.01.2018 16:52
More formally, note that there is a carry whenever the corresponding digit in $m+n$ is less than in $n$. Let's count the number of pairs $(n,k)$ with $p^N>n\ge k$ such that $n$ has at most $a$ digits that are less than their corresponding digits in $k$. To ensure that $n$ is greater than $k$, we do casework based on the first digit of $n$ that is different from $k$. Suppose that $n$ and $k$ have the same $s$ leading digits. Then, there are $\binom p2$ choices for the first different digits of $n$ and $k$. Beyond that, we may have up to $a$ instances of $k$ having a larger digit with $\binom p2$ ways, and the rest must have the digit of $n$ at least the digit of $k$ in one of $\binom{p+1}2$ ways. Hence, the number of $(n,k)$ such that $p^a\nmid\binom nk$ is at most \[p^N+\sum_{s=0}^{N-1}p^s\binom p2\sum_{b=0}^a\binom{N-s-1}{b}\binom p2^b\binom{p+1}2^{N-s-1-b}\]We will show that this is $o(p^{2N})$. Clearly, we can disregard the $p^N$ in front. Now, the term after the second summation is bounded above by $N^b\cdot(p^2)^b\cdot(p^2)^{N-s-1-b}\cdot\left(\frac{p+1}{2p}\right)^{N-s-1}=N^b\cdot p^{2N-2s-2}\cdot\left(\frac{p+1}{2p}\right)^{N-s-1}$. Summing from $b=0$ to $a$ gives that the second sum is bounded above by $N^{a+1}\cdot p^{2N-2s-2}\cdot\left(\frac{p+1}{2p}\right)^{N-s-1}$, so the term in the first sum is bounded above by $p^{2N-s}\cdot N^{a+1}\cdot\left(\frac{p+1}{2p}\right)^{N-s-1}$. Pulling out the factor of $p^{2N}\cdot N^{a+1}\cdot\frac{2p}{p+1}$, we are left to evaluate $\sum_{s=0}^{N-1}p^{-s}\cdot\left(\frac{p+1}{2p}\right)^{N-s}<\sum_{s=0}^N\left(\frac1p\right)^s\cdot\left(\frac{p+1}{2p}\right)^{N-s}=\frac{\left(\frac{p+1}{2p}\right)^{N+1}-\left(\frac1p\right)^{N+1}}{\frac{p-1}{2p}}<\frac{2p}{p-1}\left(\frac{p+1}{2p}\right)^{N+1}$. The sum thus evaluates to $p^{2N}\cdot N^{a+1}\cdot \frac{4p^2}{p^2-1}\left(\frac{p+1}{2p}\right)^{N+1}$ which is $o(p^{2N})$, as desired. Thus, for any $\epsilon$ and all sufficiently large $N$, $1-\epsilon$ of the entries of the first $p^N-1$ rows of Pascal's triangle are divisible by $p^a$, so for all sufficiently large $n$, $1-\epsilon$ of the entries of the first $n$ rows of Pascal's triangle are divisible by $p^a$, implying that for sufficiently large $n$, $1-\epsilon$ of the rows of the first $n$ rows of Pascal's triangle have at least $1-\epsilon$ of the entries divisible by $p^a$. Combining the result for all prime power divisors of $k$ in the original problem, we easily get $0.99$, as desired.
15.01.2018 10:28
We prove the statement for arbitary constants $0 \le C, D < 1$ (at least $Cn$ of the binomial coefficients are divisible by $k$, at least $DN$ good numbers among $1, 2, ..., N$) and we prove that there is an integer $z$ such that all $N > z$ works. First, we'll prove the statement for $k = p^{m}$. For a fixed integer $n$ and an integer $k$, $v_{p}\binom{n}{k} = \frac{s_{p}(k) + s_{p}(n - k) - s_{p}(n)}{p - 1}$ is the number of carries when adding $k$ and $n - k$ in base $p$. Lemma : Let $z \ge 2$ be a positive integer. We can choose $N$ large enough so that when we consider the numbers $1, 2, ..., N$ as a base-$z$ number, where $x$ is some large positive integer, at least $DN$ of them have at least $K$ digits among some nonempty subset of digits $S$, where $K$ is any fixed integer. Proof :For $N$ large enough, we only have to consider the numbers which have at least $x$ digits in base $r$ when written without leading zeroes, as we can choose $N$ such that the fraction of numbers with less than $x$ digits in base $r$ to be as close to $0$ as we need. Let $q = \frac{|S|}{z}, r = 1 - q$. Indeed, the probability of a random $x$-digit base-$z$ integer having less than $K$ digits among the elements of $S$ is bounded above by $q^{x} + \binom{x}{1}q^{x - 1}r + ... + \binom{x}{K - 1}q^{x - K + 1}r^{K - 1} \le \max(q, r)^{x}\left[\binom{x}{0} + \binom{x}{1} + ... + \binom{x}{K - 1}\right]$. Note that for $x$ large, $\binom{x}{0} + \binom{x}{1} + ... + \binom{x}{K - 1}$ is just a polynomial of degree $K - 1$ in $x$. Denote it by $P(x)$. We prove that for any $\epsilon > 0$, we can find $x$ such that $\max(q, r)^{x}P(x) < \epsilon$. This is equivalent to $\frac{P(x)}{\epsilon} < \left(\frac{1}{\max(q, r)}\right)^{x}$. LHS is a polynomial in $x$ while RHS is exponential in $x$. Thus, for large enough $x$, $RHS > LHS$ since $\frac{1}{\max(q, r)} > 1$. Back to the problem, as a corollary of this lemma, we can find $N$ such that among the numbers $1, 2, ..., N$, at least $DN$ of them contains at least $K$ zeroes when written in base $p$ without leading zeroes, for some fixed integer $K$. We claim that for large enough $K$ and $N$, all such numbers are good. Consider a number $n$ which has at least $K$ zeroes and at least $d$ digits in base $p$, for some $K$ and $d$. What fraction of numbers $0 \le x \le n$ are there so that $x$ and $n - x$ has at most $A$ carries during their addition. We claim that for large enough $K, d$, the fraction can be arbitarily small. If there are no carries at a digit $0$ in $n$, then the relative positions in $x$ and $n - x$ must both be $0$. This means that among the $K$ positions, at least $K - A$ of them must be $0$ in $x$. However, the fraction of numbers $x$ with $0$ in at least $K - A$ out of $K$ fixed positions can be arbitarily small when $K$ is large (using a similar argument as the lemma). Thus, for $d$ and $K$ large enough, all these numbers are good. This completes the proof for $k = p^{m}$. Suppose we proved the statement $k = a$ and $k = b$, where $a$ and $b$ are coprime. Then, if we can find $N$ such that among $1, 2, ..., N$, at least $DN$ numbers are good, where good numbers are defined as such that at least $Cn$ of the binomial coefficients are divisible by $k$, this means that now we have two sets of good numbers $S_{1}, S_{2}$ for different $k$, with $|S_{i}| \ge DN$. The size of their intersection is at least $DN - (1 - D)N = (2D - 1)N$. Consider this intersection. For each number $x$ in the intersection, we know that among $\binom{x}{0}, ..., \binom{x}{x}$, at least $Cx$ are divisible by $a$ and at least $Cx$ are divisible by $b$. The intersection of these two sets of binomial coefficients is again at least $(2C - 1)x$, and since $a, b$ are coprime, these coefficients are divisible by $ab$. Thus, to prove the statement for $k = ab$ and some fixed $C, D$, we can just choose a larger $C, D$ for the statements $k = a$ and $k = b$ so that when we combine them we get the desired result. Thus, this generalizes the proof for all $k \in \mathbb{N}$.
24.10.2020 11:29
Solved with nukelauncher. Say a number is \(\delta\)-good if at least \((1-\delta)n+1\) of the binomials are divisible by \(k\). We first solve the problem for prime powers \(k\): Claim: For each \(\varepsilon,\delta>0\), the density of \(\delta\)-good numbers is at least \(1-\varepsilon\). Proof. Let \(n=\overline{a_ja_{j-1}\cdots a_0}_p\), and let \(S_t\) be the \(t\)th symmetric sum of \(a_\bullet+1\). First we upper bound the number of \(i\) with \(\nu_p\left(\binom ni\right)\le e\). By Kummer's theorem, we can overcount the number of \(i\) by counting the number of \(i\) such that when written in base \(p\), at most \(e\) digits are greater than the corresponding digit in \(n\). This overcount describes at most \(p^eS_{j+1-e}\) such \(i\). But if \(\mu\) denotes the number of zeros in the base-\(p\) representation of \(n\), then from \(a_\bullet+1\le p\), \[S_{j+1-e}\le\binom{j+1}{j+1-e}\cdot p^{j+1-e-\mu}=\binom{j+1}e\cdot p^{j+1-\mu}.\]To consider the density of \(n\), we wonder how often \(p^eS_{j+1-e}\ge\delta n\). Substituting the upper bound for \(s_{j+1-e}\), we find it is necessary for \[p^\mu\le100p^{e+2}\binom{j+1}e<100p^{e+2}(j+1)^e.\]Hence \(\mu<\log_p100+e+2+e\log_p(j+1)=O(\log\log n)\). Then let \(c=O(\log\log N)=O(\log m)\) be the upper bound for \(\mu\) over all \(n=1,\ldots,N=p^m\); then each \(\delta\)-bad \(n\) contains at most \(c\) zeros, so the number of \(\delta\)-bad \(n\) is at most \[\binom mcp^c(p-1)^{m-c}<m^cp^c(p-1)^{m-c}<\varepsilon p^m\]for large enough \(m\). Digression: We can verify that \(m^cp^c(p-1)^{m-c}\) is tiny compared to \(p^m\) as follows: rewrite the inequality as \[\left(m\cdot\frac{p-1}p\right)^c\stackrel?\ll\left(\frac p{p-1}\right)^m,\]then observe that asymptotically \(x^{\log x}\ll c^x\). Anyway, this shows at most \(\varepsilon\) of \(n\le N\) are \(\delta\)-bad, as claimed. \(\blacksquare\) Finally, let \(k=p_1^{e_1}\cdots p_\ell^{e_\ell}\). We will show the density of \(k\)-good numbers is also 1. By the claim, for all \(\varepsilon,\delta>0\), the \(\delta\)-good numbers with \(k\to p_i^{e_i}\) have density at least \(1-\varepsilon\). It follows tha the density of \(\ell\delta\)-good numbers for \(k\to p_1^{e_1}\cdots p_\ell^{e_\ell}\) is at least \(1-\ell\varepsilon\), so the conclusion follows.
25.08.2023 07:41
Proof by making the number really, really, really, really big. We can instead show this holds for prime powers $k = p^e$ with bounds $1 - \varepsilon$ instead and arbitrary $\varepsilon$. We fix a very large $N$. Let $n = n_0 + n_1p + \dots + n_Np^N$ and let $a = a_0 + a_1p + \dots + a_Np^N < n$. Note that by Legendre's $\nu_p\left(\binom{n}{a}\right)$ is at least the number of times $a_i > n_i$. We now create a really big $N$. Define $T_N = \{p^{N-1}, \dots, p^{N+1} - 1\}$. Note that for sufficiently large $N$, $T_N$ is almost all of $[p^{N+1}-1]$. which consists of $N$-digit base $p$ numbers without leading zeros. Claim: For sufficiently large $x$, almost all of $T_x$ has at least one base digit of $k$ for an arbitrary $0 \le k \le p-1$. Proof. The complementary probability is $1 - \left(\frac{p-1}{p}\right)^{x-1}$. $\blacksquare$ Claim: For arbitrary $P$ and $Q$, we can construct a sufficiently large $x$ such that almost all $T_x$ has $P$ occurences of $p-1$ followed by $Q$ occurences of $0$. Proof. Chain together occurences of the previous lemma. $\blacksquare$ We now construct $a$. By making sure that one of the $P$ digits is less than $p - 1$, we ensure $a < N$. This occurs at least $1 - \frac{1}{p^P}$ of the time which can be made arbitrary close to one. Then, for the $Q$ digits, we ensure that the number of times $a_i > n_i$ for the $Q$ occurences of $i$ is at least $e$. The number of ways to do this is \[ \sum_{i=e}^Q \binom{Q}{e} (p-1)^i = p^Q - O(Q^e) \]and taking sufficiently large $Q$ lets $\frac{p^Q - O(Q^e)}{p^Q}$ approach $1$. As such, for almost all of $t \in T_N$, almost all $\binom{t}{a}$ is divisible by $p^k$.
12.02.2024 22:48
Sketch: By Legendre $v_p \left(\binom{m+n}{n}\right) = \frac{s_p(m)+s_p(n)-s_p(m+n)}{p-1}$ so now it suffices to show that the density of "carrying" is $0$. This can be done easily by counting the no. of pairs of $(n,k)$ suvh that $n+k$ does a carry.
04.09.2024 06:28
Let $N$ be a positive integer and let $S_N$ be the multiset $\left\{\binom nk \mid 0 \le k \le n \le N\right\}$. We will show the limit inferior of the proportion of elements in $S_N$ not divisible by any prime power $p^m$ is zero. Take $\nu_p$s of all items in $S_N$, which gives the multiset \[T_N = \{\text{the number of carries when $x$ is added to $y$ in base $p$, $x + y \le N$}\}.\] Consider $T_N$ and $T_{Np}$. Each element in $T_N$ generates at least $\frac 14p^2$ elements in $T_{Np}$ that are one more than itself, since each base-$p$ string $s$ can be identified with the $p$ strings $s0,s1,\dots,s(p - 1)$, where the operation is concatenation. Repeatedly multiplying by $p$ makes the proportion of elements at most $m$ arbitrarily small.