Could you please answer for this

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

Printable View

- April 13th 2014, 09:46 PMsuhailNew question
Could you please answer for this

show that in any group of 36 people, we can always find 6 people who were born on the same day of week. - April 17th 2014, 03:25 PMDynamicProgrammingRe: 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. - April 17th 2014, 06:55 PMSorobanRe: 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 aof 6 people.*minimum*

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 youhave 6 people with the same day of birth.*will*

Therefore, you could ask aof 36 people.*maximum*