For each positive integer $k$, denote by $P (k)$ the number of all positive integers $4k$-digit numbers which can be composed of the digits $2, 0$ and which are divisible by the number $2 020$. Prove the inequality $$P (k) \ge \binom{2k - 1}{k}^2$$and determine all $k$ for which equality occurs. (Note: A positive integer cannot begin with a digit of $0$.) (Jaromir Simsa)
Problem
Source: 2020 Czech and Slovak Olympiad III A p6
Tags: inequalities, Binomial, number theory, divisible
08.12.2020 13:14
2020 Czech and Slovak III P6 wrote: For each positive integer $k$, denote by $P (k)$ the number of all positive integers $4k$-digit numbers which can be composed of the digits $2, 0$ and which are divisible by the number $2 020$. Prove the inequality $$P (k) \ge \binom{2k - 1}{k}^2$$and determine all $k$ for which equality occurs. Let $m=a_1a_2 \ldots a_{4k}$ be a positive integer with $4k$ digits, with $a_i \in \{0, 2 \}$ for all $i$ and $2^2 \cdot 5 \cdot 101 \mid m$. Note that since $a_1 \neq 0$, we must have $a_1=2$. Since $5 \mid m$, $a_{4k}$ must be zero, hence it easily follows that $4 \mid m$ as well. It remains to settle down $101 \mid m$. Denote $$\displaystyle \sum_{i \, \equiv \, 1 \bmod 4} a_i =A, \, \sum_{i \, \equiv \, 2 \bmod 4} a_i = B, \, \sum_{i \, \equiv \, 3 \bmod 4} a_i = C, \, \sum_{i \, \equiv \, 0 \bmod 4} a_i = D$$ The decimal expansion of $m$ consists of $4k$ summands of the form $10^{4k-i}a_i$. Since $10^{4} \equiv 1 \pmod {101}$, we infer that $$10^{4k-i} \equiv 10^3 \equiv -10 \pmod {101}$$for all $i \equiv 1 \pmod 4$, and similarly $$10^{4k-i} \equiv 100 \equiv -1 \pmod {101}$$for all $i \equiv 2 \pmod 4$, $$10^{4k-i} \equiv 10 \pmod {101}$$for all $i \equiv 3 \pmod 4$ and finally $$10^{4k-i} \equiv 1 \pmod {101}$$for all $i \equiv 0 \pmod 4$. From the above, $$m \equiv -10A-B+10C+D \equiv 10(C-A)+D-B\pmod {101}$$ Let $Q(k)$ be the number of ways to choose $a_i$ such that $C=A$ and $D=B$. Obviously $P(k) \geq Q(k)$. We prove the following Claim, which proves the desired inequality. Claim: $Q(k)=\binom{2k-1}{k}^2$ Proof: In order for $A=C$ to hold, we must have an equal number of $a_i$ being $2$ at each of the sums $A$ and $C$. Since $a_1=2$ we may discard it from sum $A$ and just ask for $C$ to have one $2$ more than $A'$, with $A'$ being $A$ minus $a_1$. This can be done in $$\sum_{r=0}^{k-1} \binom{k}{r+1}\binom{k-1}{r}$$ways since we can have $r$ $a_i$ from $A'$ equal to 2 and $r+1$ from $C$. Using Vandermonde's identity, the previous sum is equal to $\binom{2k-1}{k}$. Similarly, the number of ways to pick $a_i$ such that $B=D$ is $\binom{2k-1}{k}$ (here, $a_{4k}=0$ hence discard it from $D$ to create $D'$ and proceed as before). Hence, in total there are $\binom{2k-1}{k}^2$ ways, as desired $\blacksquare$. To the problem, we are left to examine when equality holds. That is, we have to examine for which values of $k$, $10(C-A)+D-B \equiv 0 \pmod {101}$ forces $C-A=D-B=0$. To start, if $k=10$, then let $a_i=0$ for all $i \equiv 2 \pmod 4$ and $i \equiv 3 \pmod 4$, $a_i=2$ for all $i \equiv 0 \pmod 4$ and $a_i=0$ for all $i \equiv 1 \pmod 4$ and $i>1$ (if $i=1$ then $a_1=2$). We can easily check that $C-A=-2$ and $D-B=20$ hence $10(C-A)+D-B=0$, as desired. If $k >10$, then just let all the extra $a_i$ be equal to zero to finish. Now, we claim that if $k \leq 9$ then we must have $C-A=D-B=0$. Note that $-2k \leq C-A \leq 2k$ and $-2k \leq D-B \leq 2k$ hence $$-198 \leq -22k \leq 10(C-A)+D-B \leq 22k \leq 198$$hence $10(C-A)+D-B \in \{-101,0,101 \}$. If it is equal to $\pm 101$ then $D-B$ must be odd, which is a contradiction since $a_i \in \{0,2 \}$. Hence, $10(C-A)+D-B=0$, and since $2 \mid (C-A)$, we must have $20 \mid D-B$. Since $$-18 \leq -2k \leq D-B \leq 2k \leq 18$$the only choice is $D-B=0$ which in turn implies $C-A=0$, as desired. To conclude, equality holds if and only if $k \leq 9$.