It is not Lupus

Probability Level pending

For how many positive integers $n < 1000$ are there an odd number of subsets of $\{1, 2, \ldots, 999 \}$ with size $n$ ?

The answer is 255.

1 solution

Calvin Lin Staff
May 13, 2014

By Lucas's Theorem, ${ 999 \choose n }$ is odd if and only if in the binary representation of $n$ , the positions which are 1, are also 1 in the binary representation of 999.

Since $999 = 1111100111_2$ , we have $2^{8} - 1 = 255$ possibilities (-1 because we have to exclude $n = 0$ ).

It is not Lupus

The answer is 255.

1 solution

0 pending reports