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.

  • $\begingroup$ 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. $\endgroup$ – Eric Stucky Sep 7 '13 at 10:32
  • 3
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Sep 7 '13 at 10:47

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.

  • $\begingroup$ Say again, please? $\endgroup$ – Rasmus Sep 7 '13 at 10:38
  • $\begingroup$ I really can't parse that sentence either, sorry. I don't know how to clarify without repeating what I wrote in the answer. $\endgroup$ – Rasmus Sep 7 '13 at 10:43
  • $\begingroup$ if the question is for 3 people. but its the same way to solve no? $\endgroup$ – Ofir Attia Sep 7 '13 at 10:48
  • $\begingroup$ Well, yes. The statement with "four" in place of "three" is clearly stronger. $\endgroup$ – Rasmus Sep 7 '13 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.