Author |
Topic: A gathering problem (Read 898 times) |
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
A gathering problem
« on: Aug 27th, 2008, 8:16am » |
Quote 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:
Posts: 919
|
|
Re: A gathering problem
« Reply #1 on: Aug 27th, 2008, 3:35pm » |
Quote 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:
Posts: 7527
|
|
Re: A gathering problem
« Reply #2 on: Aug 28th, 2008, 4:36am » |
Quote Modify
|
That looks perfectly correct!
|
|
IP Logged |
|
|
|
cool_joh
Newbie
Gender:
Posts: 50
|
|
Re: A gathering problem
« Reply #3 on: Aug 28th, 2008, 5:28am » |
Quote 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:
Posts: 919
|
|
Re: A gathering problem
« Reply #4 on: Aug 28th, 2008, 6:22am » |
Quote 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 ... 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:
Posts: 7527
|
|
Re: A gathering problem
« Reply #5 on: Aug 28th, 2008, 6:52am » |
Quote Modify
|
Here is the exact same explanation, but in english. (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 |
|
|
|
|