The problem goes like this:
We color each of the 99 numbers 1, 2, …, 99 either red or green. We
say that a coloring is good if there are strictly more red numbers from 1 to 50 than red numbers
from 51 to 99.
A. How many different colorings of these 99 numbers are there?
B. How many different good colorings of these 99 numbers are there? (
Part A is straight forward, we have 2^99 possible colorings, since every number can either be red or green.
Part B I am having troubles with. It seems that the answer should be trivial, but I'm not sure how to count the possibilities. I have tried to approach the problem by taking 1 number away from the first 50 and then considering the 3 cases: when number of red in first 49 > number of red in the second 49; it's equivalent; less red in the first 49. But this approach doesn't seem to be the right one.
I have also tried counting a sum and using multiplicative principle principle to count the cases, but I believe that the way I wrote down the formula it generates cases of double counting and I can't really get around it.
I have been thinking about this problem for a while and can't figure it out. Any help would be much appreciated! Thank you!
Best Answer
Let us define the "complement" of a coloring to be another coloring, in which every number is assigned the opposite color of the original coloring, i.e. we change all red numbers to green and all green numbers to red.
I claim that:
A coloring is good if and only if its complement is not good.
Proof:
Let $a$ (resp. $b$) denote the number of red numbers from $1$ to $50$ (resp. from $51$ to $99$) in the original coloring, and let $c$ (resp. $d$) denote the number of red numbers from $1$ to $50$ (resp. from $51$ to $99$) in the complement coloring.
The original coloring is good if and only if $a > b$.
The complement coloring is good if and only if $c > d$, hence is not good if and only if $d \geq c$.
By definition of complement, we have $c = 50 - a$ and $d = 49 - b$.
Therefore: $$ d \geq c \iff 49 - b \geq 50 - a \iff a \geq b + 1 \iff a > b.$$
Since all colorings come in pairs which are complement to each other, it follows that the number of good colorings is just half of the number of all colorings. Thus the answer is $2^{98}$.