An odd party!

Nice puzzle that Neeldhara posed to me, and walked me through the solution of! Let me record it, for your enjoyment!

You are at a party where any two people have an odd number of mutual friends at the party. You see an even number of people other than you. But still …

pratyakṣam parikalitamapyartham anumānena bubhutsante tarkarasikāḥ

The lovers of logic wish to establish through inference the same objects revealed by direct perception!

So you wish to deduce that there are an odd number of attendees—the number of odd attendees, on the other hand, while definitely at least one, cannot be ruled out from being even!

The rest of the post shows one way you might deduce this. One piece of bureaucracy first: for an arbitrary party and an arbitrary attendee, by friend we mean a friend who is also an attendee.

The basic tool is the handshake lemma, which says that in any party, the number of attendees with an odd number of friends (among the attendees) is even. An immediate consequence is that if in a party, every attendee has an odd number of friends, then the number of attendees is even.

Now Devadatta is one of the attendees, and his friends want to gift him something (today being his birthday). But they haven’t decided on any yet. So they all repair to a corner to discuss this (out of his eyesight and earshot). If you consider this sub-party, how many friends does each person have? Why, an odd number, of course! (Since each friend (and non-friend!) of Devadatta shares an odd number of friends with him.) But now in this sub-party, every one has an odd number of friends, and so its strength is even (by the handshake lemma).

But the same argument holds good for Viṣṇumitra and Yajñadatta too, and hence everyone has an even number of friends. Now let us say that Devadatta’s friends have decided that there can be no better birthday gift for him than masala poli at Sri Krishna Sweets, and so drag him off (mid-party) to SKS. So an odd number of people have left the place (Devadatta and his even number of friends).

What about the rest? They each had an even number of friends in the party, and an odd number (the mutual friends they share with Devadatta) have now left. So we have a (reduced) party where everybody has an odd number of friends, and thus the strength is even (handshake lemma again!). So there, you see, the number of people originally in the party is odd!

Advertisements

6 comments

  1. I thought I had asked you this before — are Devadatta, Yajñadatta and Viṣṇumitra traditional placeholder names, like John Doe or Alice and Bob? :-)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s