Guessing Birthday Binary-Implementation Set Size

Question

Guessing a persons birthday day-of-month, i.e. a number ranging from 1 to 31 by dividing the numbers 1 to 31 up in 5 sets.

A binary number for decimal integers between 1 and 31 has at most five digits. Thus, $b_5b_4b_3b_2b_1 = b_50000 + b_4000 + b_300 + b_20 + b_1 $

If a day’s binary number has a digit 1 in $b_k$, the number should appear in Setk.

For example, number 19 is binary 10011, so it appears in Set1, Set2, and Set5.

Example of Set1:

              1 3 5 7

              9 11 13 15

              17 19 21 23

              25 27 29 31

Now what I noticed is that all 5 sets are the same size, they all contain 16 numbers.

My question is how can you show/prove that the sets are the same size?

Answer 1

Consider the binary number $b_5b_4b_3b_2b_1$, where each $b_i$ can assume values of $0$ or $1$. If you set one of the $b_i$ equal to 1, there remain four numbers that can assume values of $0$ or $1$, so $2^4=16$ possibilities.

As a result, if we define the sets $Set_i$ ($i=1$ to $5$) as those containing all binary numbers obtainable by keeping the corresponding $b_i$ fixed to 1, each of them necessarily must contain $16$ numbers.

Answer 2

If you included $0$, you would have $32=2^5$ numbers and the complement of each set would also have $16$ members. Then the symmetry makes it clear that each set is the same size as its complement, so it has $16=2^4$ members. The complement is the set of numbers with a zero in the binary expansion at that position.