Maths Olympiad Prep

Library / /71 of 94

Combinatorics Difficulty 6.7 National Olympiad Prove it Hong Kong

Find the number of nonnegative integers kk, 0k21880 \le k \le 2188, such that (2188k)\binom{2188}{k} is divisible by 21882188.
(Note that the binomial coefficient is defined by (nr)=n!r!(nr)!\binom{n}{r} = \frac{n!}{r!(n-r)!}.)

Solution

The answer is 21462146.

Note that 2188=4×5472188 = 4 \times 547, where 547547 is a prime. So 2188=40(547)2188 = 40_{(547)} (base 547547 representation). Let k=ab(547)k = \overline{ab}_{(547)}. If kk is not divisible by 547547, then b>0b > 0. By Lucas' theorem,
(2188k)=(40(547)ab(547))(4a)(0b)=0(mod547). \binom{2188}{k} = \binom{40_{(547)}}{\overline{ab}_{(547)}} \equiv \binom{4}{a}\binom{0}{b} = 0 \pmod{547}.
This shows (2188k)\binom{2188}{k} is divisible by 547547. If 547k547 \mid k, then b=0b=0 and a4a \le 4. By Lucas' theorem,
(2188k)=(40(547)a0(547))(4a)(00)=(4a)≢0(mod547). \binom{2188}{k} = \binom{40_{(547)}}{\overline{a0}_{(547)}} \equiv \binom{4}{a}\binom{0}{0} = \binom{4}{a} \not\equiv 0 \pmod{547}.
This shows (2188k)\binom{2188}{k} is not divisible by 547547.

Next, let NN be the highest power of 22 dividing (2188k)\binom{2188}{k}. Using binary representation, we have 2188=100010001100(2)2188 = 100010001100_{(2)}. By Kummer's theorem, NN is the number of carries when kk is added to 2188k2188-k in base 22.

Firstly, (2188k)\binom{2188}{k} is odd if and only if N=0N = 0. This holds if and only if aja_j is 00 whenever the corresponding digits of 21882188 in binary representation are 00. In other words, k=a000b000cd00(2)k = \overline{a000b000cd00}_{(2)}. There are 24=162^4 = 16 such numbers.

Secondly, (2188k)\binom{2188}{k} is even and is not divisible by 44 if and only if N=1N = 1. This holds if and only if kk has the form 0100a000bc00(2)\overline{0100a000bc00}_{(2)}, a0000100bc00(2)\overline{a0000100bc00}_{(2)}, a000b000c010(2)\overline{a000b000c010}_{(2)}. There are 23×3=242^3 \times 3 = 24 such numbers.

Finally, (21880)=(21882188)=1\binom{2188}{0} = \binom{2188}{2188} = 1 are odd, while 4(2188547),(21881094),(21881641)4 \mid \binom{2188}{547}, \binom{2188}{1094}, \binom{2188}{1641} since 547=001000100011(2)547 = \overline{001000100011}_{(2)}, 1094=010001000110(2)1094 = \overline{010001000110}_{(2)}, 1641=011001101001(2)1641 = \overline{011001101001}_{(2)}. Therefore, the final answer is
218951624+2=2146. 2189 - 5 - 16 - 24 + 2 = 2146.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.