Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In a group of $k$ people, some are acquainted with each other and some are not. Every evening, one person invites all his acquaintances to a party and introduces them to each other (if they are not acquainted). Suppose that after each person has arranged at least one party, some $2$ people don’t know each other. Prove that they don’t meet each other in the next meeting.

Can this be solved using PHP?

I began by assuming that some arbitrary person out of the $k$ available has thrown a party, then everybody who comes there will know everybody else, so if they are not acquainted after this party, it means they won't meet at the next party.

Is my working right?

share|cite|improve this question
It doesn’t involve the pigeonhole principle, if that’s what you mean by php. HINT: Show that if there are two people who are unacquainted after everyone has thrown a party, then the acquaintanceship graph is not connected. – Brian M. Scott Sep 11 '11 at 21:55
yep got it, who allget aquainted forma clique.. who dont should be of diff components altogether which then ensures that they wont meet ina ny pparty, not jst the next one. right? – Bhargav Sep 12 '11 at 2:40
Yep, you’ve got it. – Brian M. Scott Sep 12 '11 at 2:43
up vote 3 down vote accepted

This question has been satisfactorily answered in the comments to the question.

share|cite|improve this answer
The other way to handle this is to invite OP to write (and accept) an answer to his/her/its own question. – Gerry Myerson Oct 31 '11 at 2:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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