1

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!

Ofir Attia
  • 3,136
  • Can you please rewrite (3)? I cannot make any sense of it. I do have a guess what it might mean, but it's more from seeing pigeonhole problems before, and less from the sentence itself. – Eric Stucky Sep 07 '13 at 10:32
  • 3
    For (3) there are $11$ pigeonholes labelled $0,1,\dots 10$. Put integer $n$ in pigeonhole $r$ if $r$ is the remainder when $n$ is divided by $11$. – André Nicolas Sep 07 '13 at 10:47

1 Answers1

1

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.

Rasmus
  • 18,404