31-circle-cross-blue-pattern.jpg

Homepage

Math and Life

Counting Pigeons

You’re leaving for a fancy-schmancy dinner party. You get in the car, buckle your seatbelt and realize: you’ve forgotten your socks! Not stopping for a moment to think about how or why this happened, you rush inside, open your sock drawer, but oh no! The lights went out! You can’t see what color the socks are. You know that there are only blue and black socks (10 of each) in the drawer, all unfolded because… who has the time? Both blue and black socks match your outfit.1

What is the smallest number of socks you need to pull out to guarantee a pair?

I’ll get to the answer eventually. But first, let’s talk about boxes.


Here are three boxes and four balls.

ballsandboxes.PNG

I’m going to place all the balls in the boxes. Is it possible to do this so that there isn’t more than one ball in every box?

I think it’s intuitively clear that no, it isn’t possible. You will always have a duplicate somewhere.

The explanation is fairly straightforward:

balls with arrows.PNG

Place ball 1 in box 1, ball 2 in box 2, and ball 3 in box 3. Each box has a single ball in it. Any shuffling of balls from this state will result in more than one ball in a single box. The fourth ball must also be placed in a box, but we can’t do that without violating the “no more than one ball” rule, so it’s impossible.

We can generalize this slightly to say “if you are putting objects into containers, and the number of objects is greater than the number of containers, you will always have at least one container with more than one object in it”

And this, in essence, is the pigeonhole principle.2

TooManyPigeons.jpg

One popular demonstration of this is the fact that there are at least two people in New York City with the exact same number of hairs on their heads.

This isn’t some wishy-washy “they probably have the same number of hairs” or “there is a 99.99% chance that they do.” This is a cold hard fact: I know that there are at least two people in NYC that have the same number of hairs on their heads.

How am I so certain?

Think of the possible number of hairs on your head as boxes that we will place people in. If you have 1 hair on your head, you get placed on one box with all the other single-haired people. If you have 2 hairs on your head, you get placed in a box with all the other 2-haired people, and if you have 87,693 hairs on your head, you get placed in a box with all the other 87,693-haired people

How many boxes do we have? Depending on who you ask, the average number of human head-hairs is somewhere between 100,000 and 150,000. Given this, I think it is reasonable to establish 1,000,000 as a hard upper bound. So we have a million boxes.

And how many people do we have? The population of NYC is roughly 8.5 million.

So We are going to hypothetically place 8,500,000 people into 1,000,000 boxes.

# of people > # of boxes, so there must be at least one box with more than one person in it. Hence, there are at least two3 people in NYC with the exact same number of hairs on their heads.


Back to the sock predicament.

Remember, you’re frantically pulling single black or blue socks out of a drawer in a poorly-lit room, and you want to know the fewest number of socks you need to pull out in order to guarantee a pair.

To use the pigeonhole principle, we need to frame this as a question of objects being placed in boxes. The socks are the objects, but what are the boxes?

Our goal is to find a pair—that is, two socks of the same color. Because the pigeonhole principle guarantees “one container with more than one object in it,” (provided the conditions are met) it might be useful to choose “color” as our boxes—one box for blue socks and one for black socks.

Why do we make that choice? Think about what “one container with more than one object in it,” means in this context. If we have two socks in the same box, those two socks must be of the same color, meaning they’re a pair.

Think of pulling a sock out, then placing it in the box corresponding to its color. Now the question becomes “what is the fewest number of socks you need to pull out in order to guarantee one box has at least two socks in it?”

That looks very similar to the pigeonhole principle: “If you are putting objects into containers, and the number of objects is greater than the number of containers, you will always have at least one container with at least two in it.”

From this, the only condition that needs to be met is “# of objects > # of boxes.”

We know the number of boxes (2), so we can rewrite this as “# of objects > 2.”

We are looking for the fewest number of socks, and the smallest (natural) number that satisfies the above inequality is 3: “3 > 2.”

So 3 is the answer.


You may be thinking that I made the solution far too complicated for the problem. And fair enough. The sock problem can easily be solved by drawing a simple tree (below). That method may make more sense, but it lacks scalability. How would you do it if there were 3 colors? 4? 247? What if you needed 7 socks to match instead of 2?4

tree.PNG

As in The Wounded Rook, this technique isn’t just for playing around. It’s useful in serious5 math.


In 2003, the Manhattan Mathematical Olympiad presented this problem:

“Prove that from any set of one hundred whole numbers, one can choose either one number which is divisible by 100, or several numbers whose sum is divisible by 100.”

The solution is quite nice:

Say you have a set of 100 whole numbers:

1.PNG

Consider the subsets:

2.PNG

The first subset is just the first whole number, the second subset is the first two whole numbers, on and on until the last subset, which is all the numbers.

Now consider the sum of each of the elements in the subsets. I’ll keep the brackets to keep everything organized.

3.PNG

Divide them all by 100.

Case 1: One of these subset sums is evenly divisible by 100. If this is the case, we have fulfilled the requirement.

Case 2. None of the subset sums is divisible by 100. Proceed:

Write down the remainder of each subset after dividing by 100. It might look something like this: 2, 57, 63, 42...11. These numbers must be less than 100 (because it’s a remainder after dividing by 100), and they can’t be 0, because we are looking at the case where none of the subsets are divisible by 100 (a remainder of 0 would imply that the number is divisible by 100). The numbers must be between 1 and 99, inclusive.

Notice that we have 99 remainder possibilities (1 through 99), and 100 subsets. By the pigeonhole principle, there must be at least two subsets with the same remainder after dividing by 100 (Imagine placing 100 sets into 99 boxes).

So there are two different subsets with the same remainder after dividing by 100:

4.PNG

Both subsets have the same remainder, meaning if we write out the decimal expansion, they will have the same last two digits. Think about what happens if you subtract two numbers with the same last two digits:

subtract.PNG

No matter what the final two digits are, if they are the same, the difference between the two numbers will be a number that ends in two zeros.

If a (whole) number ends in two zeros, it is divisible by 100, which fulfills the requirement set forward by the problem.

But what does that mean in terms of sets? These two sums (below) end in the same two digits (they have the same remainder), so if we subtract them, the resultant number will be divisible by 100.

So,

5.PNG

...is divisible by 100.

And that’s how you go from sock drawers to pigeons to abstract math.


1Lets be honest, you have no idea.

2Note the two pigeons in the top left corner.

3The pigeonhole principle also guarantees at least 9 homohaired people, but I won't get into that.

4This and footnote #3 can be solved with a stronger form of the pigonhole principle that involves celing functions.

5Also as in the Wounded rook, real mathematicians are laughing at me for calling this "serious"

6This is a perfectly acceptable answer, but we can still do some simplification. Because the first few terms up to and including xb are repeated in both sums, and we are subtracting, they cancel (a > b). A simplified answer would be {xb+1,xb+2...xa}

Image sources can be found here.