Math Is Fun Forum

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Pigeonhole principle help

Hi guys, it's me again.

I'm a little confused about this question and the pigeonhole technique.

Here an example:
There are 15 students in a classroom. Show that at least two of them have the same birthday in the same month of the year.

They way I worked it out is basically A = 15 students and B = 12 months because f:A-->B and |A| > |B|.
So, if i allocate one student to 12 pigeonholes, I am left with 3 students who will have the same birthday with either of the 12 students.

The ACTUAL answer is two students, but I don't understand how you can get that.

Last edited by BlitzBall (2012-01-09 07:51:03)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Pigeonhole principle help

Hi;

The ACTUAL answer is two students, but I don't understand how you can get that.

I agree, at least 3 students will have the same month.

3 students:

4 students:

4 students:

But there is a generalized version (Djikstra?)

http://mathworld.wolfram.com/Dirichlets … ciple.html

which goes like this:

That is the average amount of students per month so you round up to 2, so there must be a birthday that at least 2 people share. Notice the different wording.

Are you sure the question is about students and not birthdays?

Here is a little puzzle:

http://www.mathsisfun.com/puzzles/match … ution.html

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Re: Pigeonhole principle help

Oh I see. I absolutely understood the example you shown me. But in the exam, I am not allowed to use a calculator and I would find it hard to divide and reach the answer 2 if I was at this question. I have been trying hard to understand this pigeonhole principle and when I look at the questions, it's understandable, but when I look at the answers, I don't know why it's +1 to my answer. Like in the example I showed, I said it should be 3, but ends up as 2, so close Not sure if you have heard 'extended pigeonhole principle' where you use |A|-->K|B|.

By the way, I got the answer right from that link you gave me!
Yea, I'm sure the question is about birthdays.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Pigeonhole principle help

Hi BlitzBall;

Yea, I'm sure the question is about birthdays.

I figured that. So you would use the formula at the bottom.

You do not need a calculator. You just need to know what the fraction is between for these problems.

Since 15 is greater than 12, the fraction is bigger than 1. Since 15 is less than 24, the fraction is less than 2. So you know it is some decimal value between 1 and 2. When you you round up to the nearest integer you will get 2.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.