Combinatorics and Probability—I love this kind of math. Here are some interesting problems I’ve gotten most of these from classes I’ve taken. Two of them (the triangle one and the combinatorial proof one) took me a few hours to solve, and each time it was like slamming my head against a wall until a lightbulb went off.

If you want to challenge yourself, I encourage you to give each problem some thought before you read the answers. Here is an idea I’ve learned from having slammed my head against a wall for a long time with problems like this—ask yourself, *“How can I think about this?”*, rather than *“What’s the answer?”*.

*1. If every point in a plane is colored either red or blue, show that an equilateral triangle with vertices of the same color exists.*The way we need to think about this problem is through the Pigeonhole Principle. I’m not going to formerly define it, but when I’m using it, I like to keep this thought in my mind—“How can I show that

*this*not happening is impossible?”. We’re not showing that something is possible; we’re showing it’s inevitable.For a quick intro to the Pigeonhole Principle (it’s really simple!), go here.

So let’s start out with the 3 points on a line given case. This is the case where we know 3 equidistant points of the same color exist on a line. We need to show that the following phrase is true “if there is a line with 3 equidistant points of the same color, then an equilateral triangle with vertices of the same color exists.”

So, if we have , then or exists.

As you can see in the above pictures, if we start with the red line, the points at the peaks of the bottom corner triangles have to be blue (otherwise there would be a red triangle there, and we’d be done). Then if there blue, the top point (the yellow one), must be red. But if it’s red, than such an equilateral triangle exists (shown on the left). So then it must be blue. But if it’s blue, then an equilateral triangle with all blue vertices exists as shown on the right.

Therefore, this statement is true—“*If we have a line with three equidistance vertices of the same color, then we have an equilateral triangle with vertices of the same color.*”

Unfortunately, the assumption that we have such a line isn’t something we can rely on (if anybody knows a proof for that one email me!), so we have to go on until we find a line with 3 equidistant same color points or the actual triangle itself. However, having the line with 3 equidistant, same-colored points as a tool to use to solve this problem is useful.

So now the pigeonhole thinking begins…

(1) We start with three equidistant points on a line. Set the first two to red. Then, the third one must be blue, otherwise we’d have a line of 3 same-colored, equidistant points and the problem would be over.

(2) The peak of the triangle with the two points must be blue, otherwise we’d have our triangle and be done.

(3) The midpoint between the two blue points must be red, otherwise we’d have a blue 3-point line, and thus the triangle.

(4) Then a third equidistant point on a line with two reds sitting on it must be blue, otherwise we’d have a 3-point red line.

(5) The midpoint on the bold line above must be red, otherwise we’d have a 3-point blue line.

(6) There is a third equidistant point to the two red points in the middle layer, and it must be blue, otherwise we’d have a 3-point red line.

(7) Now there exists a final point, highlighted above in yellow. If it’s red, then there is a red equilateral triangle. If it’s blue, then there is a blue equilateral triangle.

Therefore, an equilateral triangle with vertices of the same color must exist.

**2. Find the probability of getting dealt a full house in a poker game.
**

There are some different ways to solve this, but the one that I’ve learned and find fairly easy to replicate in different situations goes like this.If you have a full house, how many different numerical values are you looking at (note jack = 11, queen = 12, king = 13, ace = 1)?

Well, there are 13 numerical values overall, and we’ll have 2 different ones in our hand—the pair and the three-of-a-kind. So,\(\binom{13}{2}\).**How many different ways can the two numerical values make a full house (still not considering suit)?
**We can make one the pair and one the three of a kind, or switch it. So, \(\binom{2}{1}\).

**Now, how many ways can the suits be chosen?
**There are \(\binom{4}{2}\) suits for the pair, and \(\binom{4}{3}\) suits for the three of a kind.

And there are \(\binom{52}{5}\) total possible hands.$$P(\text{full house}) = \frac{\binom{13}{2} \binom{2}{1} \binom{4}{2} \binom{4}{3}}{\binom{52}{5}}$$

I realize I’m not going into great detail on this problem, that’s cuz the other two are so involved. If you struggled with this one, you can look at combinations or more on probability and poker hands.

**3. Assuming n is a positive even number, prove the following identity.**

$$\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + … + \binom{n}{n} = \binom{n}{1} + \binom{n}{3} + \binom{n}{5} + … + \binom{n}{n-1}$$

While you can do this using the binomial theorem \((x=1, y=-1)\), or Pascal’s Identity, I like to use Combinatorial proofs. Combo proofs are ones that seem less mathematical, because we describe an expression in terms of a story, and show how things relate in a more tangible, easier to grasp way.

So when we look at the above expression, we have to think—what is this counting?

Well, if we had a set *A* of length *n* (remember *n* is even), then the left side could be counting all the subsets of an even length, and the right side could be counting all the subsets of an odd length!

Now this becomes another proof—show that, given a set *A* of even length *n*, the number of subsets of even length equal the number of subsets of odd length. That’s a lot easier, because we kind of know where to go.

Recall that when counting subsets, we biject to bit strings. The number of subsets of a set of length m is \(2^m\). Imagine we took every object in the set and put it in a line. Then walked through the line and randomly assigned each object a 1 or a 0. The following subset would be given by the all objects that were assigned a 1. We can form any set this way; and every bit string of length *m* corresponds to a unique subset, so the total number of subsets (and the total number of bit strings) is \(2^m\) (remember the length of the original set is *m*).

So, how do we apply this to counting the subsets of an even or odd length?

Well, all subsets of an even length can be represented by all the bit strings with an even number of 1’s, and all the subsets of an odd length can be represented by the subsets with an odd number of 1’s.

Let’s get back to our set *A* of even length *n*.

To form a bit all the bit strings with an even number of ones, randomly choose the first \(2^{n-1}\) digits. If there is an even number of 1’s, set the \(n^{th}\) digit to be 0; if there is an odd number of 1’s, set the \(n^{th}\) digit to be 1. Since the \(n^{th}\) digit is completely determined by the previous \(n-1\) digits, there is \(2^{n-1}\) such bit strings, and thus \(2^{n-1}\) subsets of even length.

The bit strings with an odd number of ones (and thus the subsets of an odd length), are counted in the same way, except determining the final bit to allow for an odd number of 1’s as the outcome.

Therefore, there are \(2^{n-1}\) subsets of even length, and \(2^{n-1}\) subsets of odd length, and so the left side of the equation in the original problem equals the right side, and they both equal \(2^{n-1}\).

The essence of this problem highlights two important modes of thinking with these kinds of problems—“What could this equation represent?” and “I know this thing is hard to count, but what does it biject to that isn’t so hard?”

Hope you guys liked these three problems! I really enjoyed spending time with 1 and 3, and when I finally got them I was ecstatic. Also, I’ll try to post more in the future. I’ve been busy with school and writing a poker application, which I’ll be sure to post something about soon.