x Turn on thread page Beta
 You are Here: Home >< Maths

# Pigeonhole Principle Application watch

1. Q) Show the following statement:
"At least two students in a class of 200 have birthdays on the same or on consecutive days"

Attempt:

I know the pigeonhole principle states:
"if n items are put into m containers, with n > m, then at least one container must contain more than one item."

So in this case I thought the pigeons would be the 200 students and the holes would be the potential days. However I don't really know how to define the days.

I know that 200>#days to show that at least 2 students have birthdays on the same or consecutive days, a hint would be greatly appreciated!

Thanks
2. (Original post by randlemcmurphy)
Q) Show the following statement:
"At least two students in a class of 200 have birthdays on the same or on consecutive days"

Attempt:

I know the pigeonhole principle states:
"if n items are put into m containers, with n > m, then at least one container must contain more than one item."

So in this case I thought the pigeons would be the 200 students and the holes would be the potential days. However I don't really know how to define the days.

I know that 200>#days to show that at least 2 students have birthdays on the same or consecutive days, a hint would be greatly appreciated!

Thanks
As you surmised, the key is in what are the pigeonholes.

Clearly, a single day won't suffice - hope that's sufficient.
3. (Original post by ghostwalker)
As you surmised, the key is in what are the pigeonholes.

Clearly, a single day won't suffice - hope that's sufficient.
I'm probably over-complicating it but:

If I was to take the odd days in a year (i'll assume it is a leap year).
So 1,3,5,7,9....,365

a=b OR b=a+1

So person a has a birthday on an odd day and b has it on the same day OR person b has a birthday on an even day, 1 day after a who had his/her birthday on an odd day.

In a leap year the number of odd days are 187 since 200>187 it follows that there are at least 2 students who have their birthday on the same day or consecutive days.
4. (Original post by randlemcmurphy)
I'm probably over-complicating it but:

If I was to take the odd days in a year (i'll assume it is a leap year).
So 1,3,5,7,9....,365

a=b OR b=a+1

So person a has a birthday on an odd day and b has it on the same day OR person b has a birthday on an even day, 1 day after a who had his/her birthday on an odd day.

In a leap year the number of odd days are 187 since 200>187 it follows that there are at least 2 students who have their birthday on the same day or consecutive days.
Sorry, I'm struggling to follow what you've done there.

Alternatively, and I suspect this may be what you're aiming at:
Spoiler:
Show

Partition the year into pairs of days, {1,2}, {3,4}, etc. With potentially a singleton at the end {365}. These are our pigeonholes.
There are 183 of them.
etc.
5. (Original post by ghostwalker)
Sorry, I'm struggling to follow what you've done there.

Alternatively, and I suspect this may be what you're aiming at:
Spoiler:
Show

Partition the year into pairs of days, {1,2}, {3,4}, etc. With potentially a singleton at the end {365}. These are our pigeonholes.
There are 187 of them.
etc.
That is what I was aiming for, I should have realized straight away to do what you did. I was thinking along the same lines but my written explanation wasn't too good!

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: November 8, 2015
Today on TSR

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams