What tactics could help with this probability questions I'm not too sure if this question is solvable (I sort of just thought of it yesterday) but when I brute force numerical answers on my computer they seem to show a pattern, so I believe it to be solvable. 
The question: I have $N$ people in a stadium, and there are $5$ different coloured shirts. Each person has an equal chance of wearing any of the coloured shirts. (i.e. it's equally likely that you'll find a guy with a black shirt, than a blue or pink or grey or brown shirt). The love god suddenly starts playing music across the stadium, and every single person suddenly has an unresistable desire to pair up with a person who is wearing a same coloured shirt. Find the probability that nobody is left alone. (equivalent to asking find the probability that the number of people wearing each colour is an even number).
Trivial Observations: If $N$ is odd, then the chance is $0$, only if $N$ is even is the chance finite. In fact (for the case where there are $5$ different coloured shirts), if $N$ is odd, the colours can end with only $3$ combinations (all odd, $3$ odd $2$ even, $4$ odd $1$ even) and for $N$ is even - (all even, $4$ odd $1$ even, $2$ odd $3$ even).
A (seemingly crucial) observation: It seems that if I increase $N$ to an arbitrarily large amount, that the probability that all the colours are even at the end should asymptote for some value, because the bulk majority of people just pair off. I started my solution by attempting to prove this point. To do this, I assumed that at the beginning all $100$ people were shirtless, and we would add the shirts on to the people one by one. We will keep a 'lonely counter' that keeps count of all lonely people, and the moment someone gets paired they immediately are forgotten from memory for all we care. For the first person, the color shirt he chooses is arbitrary, because he will definitely be lonely, so our lonely counter is at $1$. The next person has a $0.2$ chance of picking the same shirt as the first person (in this case the lonely counter drops to $0$), and a $0.8$ chance of picking a different colour (in this case the lonely counter goes up to $2$). The maximum lonely counter value is $5$, and for the case where we want $0$ lonely people, by the time we are done assigning shirt values to everybody the lonely counter must again be at $0$. To test my asymptotic theory, I pretty much put this 'lonely counter' into excel to see what happens

At $N = 0$, the lonely counter is $0$ with a $100\%$ probability (no people around). At $N = 1$, the lonely counter is $1$ with a $100\%$ probability (1 person by himself definitely lonely). At $N = 2$, the lonely counter is $0$ with $0.2$ chance, and $2$ with $0.8$ chance (as explained above). With math and excel magic I ran the data along, and wondrously, the chance the lonely counter was $0$ asymptoted toward a value of $6.25\%$. Then I tried for different numbers of shirts, and found a trend, so unless I messed up my math then I believe
$$ P = \dfrac{1}{2^{p-1}} $$
For large $N$, and where $p$ is the number of shirts. I tried to use my lonely counter to actually prove the result though, and I'm sort of stuck now, and not really sure where to go from here. Any help is appreciated. 
 A: Here's two generally useful tools for this sort of problem:
The Multinomial Distribution, viewed as a Generating Function:
$$(x_1+x_2+x_3+x_4+x_5)^n = \sum_{a_1+\dots+a_5 = n} \frac{n!}{a_1! a_2! a_3! a_4! a_5!} x_1^{a_1} x_2^{a_2} x_3^{a_3} x_4^{a_4} x_5^{a_5}$$
Here the coefficient on the right side represents the number of ways of choosing exactly $a_j$ people to have shirt color $j$ for each $j$.  
Dividing by $5^n$, we can view this probabilistically:
$$5^{-n}(x_1+x_2+x_3+x_4+x_5)^n = \sum_{a_1+\dots+a_5=n} P(a_1, a_2, a_3, a_4, a_5) x_1^{a_1} x_2^{a_2} x_3^{a_3} x_4^{a_4} x_5^{a_5},$$
where $P(a_1, \dots, a_5)$
is the probability the population has exactly distribution $(a_1, \dots, a_5)$ of shirt colors.  
In other words, we can encode the entire probability distribution of shirt colors as the expansion of a single polynomial.  
Coefficient Extraction for Polynomials
What we did above essentially reduced our question to the following: Given a polynomial, how do we extract the sum of only the even coefficients? If we only had one variable, the trick would be to use the observation that 
$$\frac{1^k + (-1)^k}{2} = \left\{ 1 \textrm{ if } k \textrm{ is even} \atop 0 \textrm{ if } k \textrm{ is odd } \right.$$
So if $f$ is a $1$ variable polynomial, and I take $\frac{f(1)+f(-1)}{2}$, the odd coefficients all vanish and I'll get the sum of the even coefficients of $f$.  
The multivariate analogue of this:  If $f(x_1, \dots, x_k)$ is a $k$ variable polynomial, and I take 
$$\frac{1}{2^k} \sum_{c_i \in \pm 1} f(c_1, c_2, \dots, c_k),  $$
then I get the sum of the even coefficients of $f$  For example, for two variables, I'd take 
$$\frac{1}{4} \left(f(1,1)+f(1,-1)+f(-1,1)+f(-1,-1)\right).$$
The point is that if I look at any term with at least one odd power, the sum causes that term to cancel (You should check this!).
Now let's take the tools and combine them.  In this case the $f$ we'll be applying things to is $\frac{1}{5^n} (x_1+\dots+x_5)^n$.  Plugging in the different values of $x$ and combining equal terms, we get a probability of 
$$\frac{1}{5^n} \left(\frac{1}{32} ( 5^n + 5 \times 3^n + 10 \times 1^n + 10 \times (-1)^n + 5 \times (-3)^n + (-5)^n)\right)$$
As expected, if $n$ is odd this comes out to exactly $0$.  If $n$ is even, the positive and negative bases combine further, and we can write this as 
$$\frac{1}{16} + \frac{5}{16} \left(\frac{3}{5}\right)^n + \frac{10}{16} \left(\frac{1}{5}\right)^n$$
In particular, it's converging very rapidly to $\frac{1}{16}$ as $n$ increases, which matches your simulations and joriki's intuitive argument.  
