# New question

• Apr 13th 2014, 10:46 PM
suhail
New question

show that in any group of 36 people, we can always find 6 people who were born on the same day of week.
• Apr 17th 2014, 04:25 PM
DynamicProgramming
Re: Pigeon Hole Principle
@suhail
Try to prove that statement wrong: try to show that you can have 36 people, 6 of whom don't have to be born the same day of the week.

How would this work? Well, we need LESS THAN 6 people to be born every day of the week.

So: Monday: at most 5 people
Tuesday: at most 5
...
Sunday: at most 5.

But notice, there are 7 days in a week and at most 5 people per day, which is 35.

35 < 36 and we know if we increased any one of those days by 1, we'd be at 6 which we don't want!

It follows that there are always 6 people born the same day of the week in a group of 36.
• Apr 17th 2014, 07:55 PM
Soroban
Re: New question
Hello, suhail!

Quote:

Show that in any group of 36 people, we can always find
6 people who were born on the same day of week.

Suppose you randomly ask people on the street their day of birth.
. . And you want to find 6 people who have the same day.
How many people must you ask?

You could be very lucky.
. . The first 6 people could be born on, say, Tuesday.
So you could ask a minimum of 6 people.

What is the very worst that can happen?

You ask a large group of people and:
. . 5 were born on Sunday,
. . 5 were born on Monday,
. . 5 were born on Tuesday,
. . 5 were born on Wednesday,
. . 5 were born on Thursday,
. . 5 were born on Friday,
. . 5 were born on Saturday.

You have asked 35 people, and you still
. . won't have 6 people on the same day.

But the next person will have one of those days.
Then you will have 6 people with the same day of birth.

Therefore, you could ask a maximum of 36 people.