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

 Introductions all around (Posted on 2013-06-14)
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: Solution | Comment 6 of 8 |
(In reply to Solution by Dan Rosen)

Sorry, on second thought, my solution does prove that within any group n, the number of acquaintances is larger than the sum of the full acquaintances present in any breakdown of n into 2 fully acquainted groups . This shows that if such breakdown is possible, it does not contradict the terms of the problem.  The question whether every group n, can indeed be broken down into 2 fully acquainted groups has not yet been proven !!!

 Posted by Dan Rosen on 2013-06-22 09:10:40

 Search: Search body:
Forums (0)