Pigeonhole principle questions

163 Views Asked by At

I want to solve the following problems with Pigeonhole principle.

  1. Show that in every group of people that have atleast 2 people, we can find couple that know the number of the people in the group.( lets suppose that its symetric relation ).
  2. Show that in place of 1200 people we can find 3 of them that have the same birth date.
  3. There is 12 different integers demonstrated that there are two of them in their difference is divisible by 11

what I tried to do is only for the second question.
I said that there $365$ days so its like Pigeonholes, then $\frac{1200}{365}$ we will get $3.28$ so its obvious that there is a hole that have 3 people with the same birth date, right?
for the other questions I would like to get some advice.
Thanks!

1

There are 1 best solutions below

4
On

Concerning the second question, the reasoning could be as follows: if every day is the birthday of at most two people from the group, then the group can consist of at most $2\times 365 < 1200$ people. By contradiction, at least one day must be the birthday of at least three group members. In fact, as your computation shows, there must even be a day that is the birthday of at least four of the $1200$ people.