Combinatorics problem involving sets

For any two sets in $S$ to be non-empty, each set has to have at least one element, say $x$ , in common. So, keeping $x$ fixed, we can create all sets containing $x$ in $2^{99}$ ways. This will give us the maximum number of elements in $S$ .

All that is left to do is to find last two digits of $2^{99}$ :

$x \equiv 2^{99} \pmod{100}$ We break it down into $x \equiv 2^{99} \pmod{25}$ and $x \equiv 2^{99} \equiv 0 \pmod{4}$ _ _ _ 1

Since $2^{10} \equiv -1 \pmod{25}$ , we have $2^{90} \equiv -1\pmod{25}$ . Now $2^{9} \equiv 12 \pmod{25}$ . Combining both, we have $x \equiv 2^{99} \equiv 13 \pmod{25}$ . _ _ _ _ _ 2

Now we use CRT to combine 1 and 2 together. We write $x = 25j + 13$ . So, $25j +13 \equiv 0 \pmod{4}$ or $25j \equiv 3 \pmod{4}$ . Solving for j, we have $j \equiv 3\pmod{4}$ . Therefore, $j=4k + 3$ . Therefore, $x=25(4k+3) + 13$ or $x=100k + 88$ . Therefore, $x \equiv 2^{99} \equiv 88 \pmod{100}$ .