truth tables: prove at least 4 of 40 born in same month

[krisoshiro]

given any 40 people, prove that at least 4 of them were born in the same month of the year.

I'm new to logic and all we learned were truth tables. this is one of the questions i need to answer. Can't figure out how to start it.

 

[JellyFish]

Re: truth tables?

This is how I would do it....

Make 12 (for each month) underscore type dashes on your page or the beginning letter of each month so J F M etc.

Start placing an x or check or something under each dash/letter until you use all 40 "people"/checks.

You will find that you can can go through 3 times (you have used 36 people) and after this you have 4 people left..whether you spread them out or put 2 somewhere and 2 somewhere else etc. at least one month/underscore/letter will have to have at least 4 people.

 

[PAULK]

Re: truth tables?

This is how I would do it....

Make 12 (for each month) underscore type dashes on your page or the beginning letter of each month so J F M etc.

Start placing an x or check or something under each dash/letter until you use all 40 "people"/checks.

You will find that you can can go through 3 times (you have used 36 people) and after this you have 4 people left..whether you spread them out or put 2 somewhere and 2 somewhere else etc. at least one month/underscore/letter will have to have at least 4 people.

yes, but these 'teacher' types want something more formal, such as:

Assume no month has more than 3 birthdays (people with .. in). Let
B[k] be the number of birthdays in month[k]. Then:

for all k, B[k] <= 3.

and then:

SUM[k=1,12] B[k] <=

SUM[k=1,12](3) <=

12 * 3 = 36.

But the sum is 40. That is your contradiction and proof.