wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> A gathering problem
        
(Message started by: Grimbal on Aug 27^th, 2008, 8:16am)

Title: A gathering problem
Post by Grimbal on Aug 27^th, 2008, 8:16am

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.

Title: Re: A gathering problem
Post by Hippo on Aug 27^th, 2008, 3:35pm

[hide]We have to prove there is a complete subgraph K_n+1 (on n+1 vertices). Than the vertex selected for the remaining n vertices is connected to the each vertex.

So K_n+1:
Set i=0, start with set of arbitrary n vertices they select a vertex v_i++ 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. v₀,...,v_n is the complete subgraph.
[/hide]

Title: Re: A gathering problem
Post by Grimbal on Aug 28^th, 2008, 4:36am

That looks perfectly correct!

Title: Re: A gathering problem
Post by cool_joh on Aug 28^th, 2008, 5:28am

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

Title: Re: A gathering problem
Post by Hippo on Aug 28^th, 2008, 6:22am

on 08/28/08 at 05:28:33, 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 :) ... 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 v₀,...,v_n know pairwise each other.

Title: Re: A gathering problem
Post by Grimbal on Aug 28^th, 2008, 6:52am

Here is the exact same explanation, but in english. ;) (It was my solution to the problem).

[hide]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.
[/hide]