TIFR CSE 2021 | Part A | Question: 12

Question

How many numbers in the range ${0, 1, \dots , 1365}$ have exactly four $1$’s in their binary representation? (Hint: $1365_{10}$ is $10101010101_{2}$, that is, $$1365=2^{10} + 2^{8}+2^{6}+2^{4}+2^{2}+2^{0}.)$$

In the following, the binomial coefficient $\binom{n}{k}$ counts the number of $k$-element subsets of an $n$-element set.

• A. $\binom{6}{4}$

• A. $\binom{10}{4}$

100. $\binom{10}{4}+\binom{8}{3}+\binom{6}{2}+\binom{5}{1}$

500. $\binom{11}{4}+\binom{9}{3}+\binom{7}{2}+\binom{5}{1}$

• A. $1024$

Answer 1

$1365 = (10101010101)_2$

$(\text{total number of bits =} 11)$

Now if I keep $MSB = 0$, then from the remaining $10$ bits, I can select any $4$ bits ans set them as $1$. So total cases become $\binom{10}{4}$.

Now keep the $MSB = 1$, now we cannot replace $0$ on the second last bit from LHS with 1 as it will increase the number. This will apply to every $0$ as we move forward. So, now we have $10$ on the LHS and the third bit from LHS, we set to $0$, now we have $8$ bits remaning from which we have to select $3$ bits (Why $3$? as we are keeping MSB as $1$ and in total we only need $4$ bits to be set to $1$). Total cases will become $\binom{8}{3}$.

Similarly, we will move forward and will get $\binom{6}{2}$ and $\binom{4}{1}$.

So, the answer should be $\binom{10}{4} + \binom{8}{3} + \binom{6}{2} + \binom{4}{1}$

I think there is a typo in the $(C)$ option. They have the last term as $\binom{5}{1}$ instead of $\binom{4}{1}$.