All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Introductions all around (Posted on 2013-06-14) Difficulty: 4 of 5
The town of Friendville has an interesting property. Given any two people in the town, they either know each other or they don't. If they don't know each other, then they can be introduced to each other. One single introduction will work for both people. That is, "Tom this is Phil, Phil this is Tom" counts as one introduction.

The other interesting property that this town has, is that if any group of n people get together, the number of introductions that must be made in order that everyone in the group knows everyone else is at most n-1.

Problem: Prove that the town can be divided into two groups (A and B) such that everyone in group A knows each other, and everyone in group B knows each other.

No Solution Yet Submitted by Danish Ahmed Khan    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re(2): Possible solution | Comment 3 of 8 |
(In reply to re: Possible solution by Steve Herman)

You are right.

In my quest to simplify as much as possible, I have over-simplified.

'B does not know A' says nothing about 'B does not know C', and 'D does not know A, or  D does not know B', says nothing about 'D knows both A and B.'

As you correctly state, the method therefore seems to require the creation of additional residual 'holding' classes, something I was anxious to avoid, even though it is easy to see that they must reduce by the sort of reasoning that you've already outlined.

 

Edited on June 15, 2013, 11:47 am
  Posted by broll on 2013-06-15 11:46:30

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information