wu :: forums
« wu :: forums - A gathering problem »

Welcome, Guest. Please Login or Register.
Nov 25th, 2024, 12:27am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Icarus, ThudnBlunder, towr, SMQ, william wu, Eigenray, Grimbal)
   A gathering problem
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: A gathering problem  (Read 898 times)
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
A gathering problem  
« on: Aug 27th, 2008, 8:16am »
Quote Quote Modify Modify

A small problem I found somewhere else, that I paraphrased a bit to make it more google-safe.
 
There is a gathering of 2n+1 people.  For any set of n people at the gathering, there exists one person outside of the set who knows everybody in the set.
 
Prove that there is a person who knows everybody.
 
Acquaintance is symmetric.  A knows B iff B knows A.
IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 919
Re: A gathering problem  
« Reply #1 on: Aug 27th, 2008, 3:35pm »
Quote Quote Modify Modify

We have to prove there is a complete subgraph Kn+1 (on n+1 vertices). Than the vertex selected for the remaining n vertices is connected to the each vertex.  
 
So Kn+1:
Set i=0, start with set of arbitrary n vertices they select a vertex vi++ connected to each of them. Discard a vertex different from v* and repeat. Once all vertices in the set are named, we know each is connected to all vertices in the set. v0,...,vn is the complete subgraph.
« Last Edit: Aug 27th, 2008, 3:36pm by Hippo » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: A gathering problem  
« Reply #2 on: Aug 28th, 2008, 4:36am »
Quote Quote Modify Modify

That looks perfectly correct!
IP Logged
cool_joh
Newbie
*





   
WWW

Gender: male
Posts: 50
Re: A gathering problem  
« Reply #3 on: Aug 28th, 2008, 5:28am »
Quote Quote Modify Modify

I don't understand. I haven't learned anything about graph theory. Is there another explanation without graph theory?
IP Logged

MATH PRO
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 919
Re: A gathering problem  
« Reply #4 on: Aug 28th, 2008, 6:22am »
Quote Quote Modify Modify

on Aug 28th, 2008, 5:28am, cool_joh wrote:
I don't understand. I haven't learned anything about graph theory. Is there another explanation without graph theory?

 
I am poor in English Smiley ... replace "complete subgraph on k" vertices with 'k persons pairwise knowing each other'.
"vertex connected to each of them" with 'person knowing each of them'. And name 'persons' instead of "vertices".
Persons v0,...,vn know pairwise each other.
« Last Edit: Aug 28th, 2008, 6:23am by Hippo » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: A gathering problem  
« Reply #5 on: Aug 28th, 2008, 6:52am »
Quote Quote Modify Modify

Here is the exact same explanation, but in english. Wink (It was my solution to the problem).
 
Let's take someone, a1, and (n-1) other people.
Someone, a2, knows them all, especially a1.
Let's take a1, a2 and (n-2) other people.
Someone, a3, knows them all, especially a1 and a2.  a1, a2 and a3 all know each other.
 
Continue like this you end up with a1..an who all know each other.  Do one more step:
Let's take a1..an.  Someone, a[n+1] knows them all.
You now have a group of n+1 people who all know each other.  Let's call that group A.
 
Let's call B the group of the n remaining people.
 
B is a group of size n.  One person not in B knows all people in B.  That person in in A, so it also knows all people in A.  So, that person knows everybody.  
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board