PrepRung

JEE Advanced 2023 Paper 1 · Mathematics · Binomial Theorem · hard

Let N be the number of integers k with 0≤ k≤100 for which binom100k is odd and also divisible by 3. Find N.

Numerical answer

Let NN be the number of integers kk with 0≤k≤1000\le k\le100 for which (100k)\binom{100}{k} is odd and also divisible by 33. Find NN.
Show answer and solution

Answer: 6

Odd: by Lucas' theorem (base 2), (100k)\binom{100}{k} is odd iff the binary digits of kk are dominated by those of 100=11001002100=1100100_2. This has three 1-bits, so 23=82^3=8 values of kk: 0,4,32,36,64,68,96,1000,4,32,36,64,68,96,100.
Not divisible by 3: by Lucas (base 3), 100=102013100=10201_3, and (100k)≢0(mod3)\binom{100}{k}\not\equiv0\pmod3 iff each base-3 digit of kk is at most the matching digit of 100100. Among the eight values above, only k=0k=0 and k=100k=100 satisfy this (for example k=4=113k=4=11_3 has digit 11 in the 313^1 place where 100100 has 00).
So 22 of the 88 odd values are not multiples of 33, and N=8−2=6N=8-2=6.
Report a mistake

Original question written in the JEE Advanced 2023 Paper 1 pattern and checked twice for the correct answer. Not an official question paper. How we write and check questions · Corrections policy · Report a mistake