# Combinatorial question: drawers and shirts

If I have 50 drawers, each with a blue shirt, a red shirt, a green shirt and a yellow shirt, how many ways can I pick an even number of green shirts? The order of non-green shirts matters too.

Thanks!

-
The problem isn’t fully specified. Are you choosing one shirt from each drawer? – Brian M. Scott Feb 19 '12 at 1:37
Yes, that's right.. sorry I didn't specify! – John Forster Feb 19 '12 at 2:09

I (mis?)interpreted the question as asking what happens when we choose a shirt from every drawer and colour matters for non-green shirts too. (So my answer for 1 drawer would be $3$, yours would be $2^0=1$). Here's my solution anyways.

Assume we choose with uniform probability. The probability of picking exactly $k$ green shirts is $$p_k={50 \choose k} 4^{-k} \left( \frac{3}{4} \right) ^{50-k}=\left( \frac{3}{4} \right) ^{50} {50 \choose k} 3^{-k}$$

Now the probability in question is

$$\sum_{2|k} p_k= \left( \frac{3}{4} \right) ^{50} \sum_{2|k} {50 \choose k} 3^{-k}$$

Here $$\sum_{2|k} {50 \choose k} 3^{-k}=\frac{\left( 1+\frac13 \right)^{50} + \left( 1-\frac13 \right)^{50}}{2}=\frac{(4/3)^{50}+(2/3)^{50}}{2}$$ by the binomial theorem.

Therefore the probability is $$\frac{1+2^{-50}}{2}\;.$$ The total number of cases is $4^{50}$ so we get $$2^{99}+2^{49}$$ as the answer.

-
Looks like my answer from a different approach – Henry Feb 19 '12 at 2:06

Let's suppose that you have to choose one of four shirts from each drawer and the $e(n)$ is the number of ways of choosing an even number of green shirts from $n$ drawers, and $o(n)$ for odd. You have

$$e(n)=e(n-1)+3o(n-1)$$ $$o(n)=o(n-1)+3e(n-1)$$ $$e(0)=1 , o(0)=0.$$.

Since $e(n)+o(n)=4e(n-1) + 4o(e-1)$ and so $2^{2n}$,

and $e(n)-o(n)=2e(n-1) - 2o(e-1)$ and so $2^n$, we get $$e(n)=2^{2n-1}+2^{n-1}$$ $$o(n)=2^{2n-1}-2^{n-1}.$$

For $n=50$, $e(n) = 633825300114115263698305024000.$

-
Sorry I didn't specify earlier, but the order of the non-green shirts matters too... – John Forster Feb 19 '12 at 2:27
@John: Henry’s answer takes that into account. – Brian M. Scott Feb 19 '12 at 2:41

If you’re choosing one shirt from each drawer, there are $2^{49}$ different ways to choose an even number of green shirts. Here’s one way to see this.

First, note that you’re really just counting the number of ways of choosing an even number of drawers, namely, the drawers from which you’ll take a green shirt. Imagine going through the drawers one at a time, from Nr. 1 to Nr. 50. For each of the first $49$ drawers you can take a green shirt or not, as you please; those $49$ two-way choices can be made in $2^{49}$ different ways. That is, there are $2^{49}$ possible subsets of $49$ drawers, and you can pick any of those subsets to be the one from which you take the green shirts. But when you reach Drawer 50, you no longer have a choice: if you’ve already chosen an even number of green shirts, you must take a non-green shirt, and if you’ve already chosen an odd number of green shirts, you must take a green shirt. Thus, the final answer is still $2^{49}$.

Added: However, this treats the non-green shirts as if they were indistinguishable, which is probably not what was intended. Tib’s solution answers the question that was probably intended.

-
Don't you have to consider the sum of all the cases: 1) Take 0 green shirts and 49 non-green, 2) Take 2 green and 48 non-green, etc. etc.? – John Forster Feb 19 '12 at 2:13
My argument does consider all of those cases, but on the assumption (that I later realized was almost certainly erroneous, as you’ve now confirmed with your comment to Henry) that the non-green shirts could be treated as indistinguishable. – Brian M. Scott Feb 19 '12 at 2:40

Here's another approach that gets you Tib's answer. There's $4^{50}$ ways of picking the shirts. I'll divide them into two classes.

1: Every shirt is either red or blue. There's $2^{50}$ selections in this class, and they all have an even number ($0$) of green shirts.

2: There is at least one shirt that's neither red nor blue. I claim exactly half the selections in this class have an even number of green shirts. To see this, let drawer $k$ be the first drawer with a green/yellow shirt. Switching the color of the shirt in drawer $k$ changes the parity of the number of green shirts. This operation pairs off the selections in this class with an even number and the selections with an odd number.

So the total is $2^{50} + \frac{1}{2} \left(4^{50}-2^{50}\right)=2^{99}+2^{49}$

-