3
$\begingroup$

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?

  • 1
    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.2011-09-11
  • 0
    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?2011-09-12
  • 0
    Yep, you’ve got it.2011-09-12

1 Answers 1

3

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

  • 1
    The other way to handle this is to invite OP to write (and accept) an answer to his/her/its own question.2011-10-31