Author |
Topic: New Problem; Introductions all around (Read 2658 times) |
|
Mr._Martingale
Newbie
Posts: 3
|
 |
New Problem; Introductions all around
« on: Aug 10th, 2002, 11:44am » |
 Quote  Modify
|
The town of Friendville has an interesting property.
Given any two people in the town, they either know
eachother or they don't. If they don't know eachother,
then they can be introduced to eachother. 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 eachother.
This problem was introduced to me in a combinatorics class
The professor remembered reading it somewhere, but didn't
remember the answer. He tried to prove it in class, but
eventually gave up. Over the summer I thought about it
for about 3 days straight, until I came up with the
really elegant solution.
Hint: the proof holds, even if you weaken the
condition to just odd n.
|
|
 IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: New Problem; Introductions all around
« Reply #1 on: Aug 10th, 2002, 1:07pm » |
Quote Modify
|
Gather the N townspeople together, call this the pool. Pick up some person who doesn't know someone else. Put him in group 1 (g1) and the person he doesn't know in group 2 (g2). Now repeat the following: If any person x in either g1 or g2 doesn't know some person y from the pool, then take y from the pool and put him in the opposite group from x. If everyone in g1 and g2 know everyone in the pool, then pick up some person x from the pool and assign him to either g1 or g2 -- call this starting a new phase of the process.
Proof of correctness by contradiction. Assume that some 2 people x,y in g1 don't know each other. Note that x and y must have been added in the same phase because we would not have entered a new phase while someone in one of the groups didn't know someone in the pool. Consider the set of m people added in the same phase as x and y. By the method which we used to add people, we know that there are m-1 introductions necessary between g1 and g2 among the people from this phase. Therefore there can't be an introduction necessary between x and y because that would mean there is a set of m people who need m introductions.
Edited to add: if we want to use the weaker condition (only odd groups) we can look at the set of people who are added between x and y in our algorithm (including x and y). This set is always odd in size.
|
| « Last Edit: Aug 10th, 2002, 1:14pm by AlexH » |
IP Logged |
|
|
|
Mr._Martingale
Newbie
Posts: 3
|
|
Re: New Problem; Introductions all around
« Reply #2 on: Aug 10th, 2002, 6:17pm » |
Quote Modify
|
Nice proof Alex. I think the proof I had in mind,
is largely equivalent to yours, although I
approached it from a different standpoint.
Later in the week I'll give out my proof.
I'm not sure I agree with your last statement though,
Suppose (ABCDE) all know eachother but none know G.
I first create the groups g1=A and g2=G
Then I add B,C,D,E to g1 in that order.
to test wheter B and E know eachother,
Do you recommend I look at the group
(BCDE)? This is not of odd size, and
doesn't seem to tell me anything.
Perhaps I'm misunderstanding what you were
suggesting.
On the other hand, perhaps we should change
my hint into "problem 2"
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
7Re: New Problem; Introductions all around
« Reply #3 on: Aug 10th, 2002, 7:18pm » |
Quote Modify
|
I should have been much more clear on what I mean by between. You can think of the set of people you add in a single phase as a set of people connected by the "don't know" edges which you caused you to add them. The set of people "between" x and y is the set of people you need to traverse using these selected edges. Since each of these selected edges crosses the divide between g1 and g2, any path using these edges that goes from g1 to g1 (likewise g2 to g2) must have an even number of edges, and thus an odd number of verticies.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender: 
Posts: 318
|
|
Re: New Problem; Introductions all around
« Reply #4 on: Aug 11th, 2002, 9:04pm » |
Quote Modify
|
[ARGH! I wrote up most of this post this morning, but got distracted by some other things; coming back to it tonight I managed to lose the rest of my write-up for technical reasons. Sorry, this will be a VERY abbreviated version instead.]
First, excellent problem Mr. Martingale, I very much enjoyed it. Also, nice name; are you in finance?
Ok, I didn't go through Alex's proof carefully, but decided mine seemed sufficiently different that I would post it. I think it's quite an intuitive pf:
Start with any one person in a "group". Repeatedly create new groups by splitting off those people who don't know at least one person in the previous group; this sequence eventually terminates with a group (possibly empty) that knows everyone in the previous group; but then they know everyone in all previous groups, or else they would have been included in an earlier group. Call this sequence X0 = {x0}, X1, ..., Xn, Y.
I had two lemmas before that made it easy to see the next step, but instead I'll gloss over it and leave the detail to the reader (it's pretty easy anyway). For i, j not different by exactly 1, everyone in Xi knows everyone in Xj. This is because for every xi, xj you can create a chain of people each not knowing the last that goes from Xi "up to" X0 and from there back "down to" Xj -- possibly shorter if there is a common link on the way "up" from i and j. The not exactly 1 condition ensures that the length of this chain is at least 3, so by the "n-people n-1 intros" condition xi knows xj. All I really care about is actually that for i, j of the same parity, everyone knows each other -- note that for those cases this requires only the "n ppl" condition for odd n.
(I actually only need the hypothesis for i=j; the rest follows by construction, but it is easy to prove using the hypothesis, too.)
Now, merge all the Xi of equal parity, leaving two groups all of whom know each other (the even i groups and the odd i groups). The people in Y know everyone in all the Xi, so split it into two complete groups (say, by using a strong induction, since by construction Y is strictly smaller than the original set); merge either with the two sets of Xi and you get the two complete groups you want. QED
Say, I guess I ended up pretty much writing most of it out again anyway. 
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Mr._Martingale
Newbie
Posts: 3
|
|
Re: New Problem; Introductions all around
« Reply #5 on: Aug 16th, 2002, 8:06pm » |
Quote Modify
|
Hello Eric,
Glad you liked the problem. For the record, I'm not in finance, I'm actually a statistician working at the National Cancer Institute. I use this name when I play games of chance
online, and it seemed appropriate here as well.
It is interesting that there are two very nice solutions up,
which in combination are very similar to my solution, yet
I arrived at mine from a completely different direction, in
that I imagined it visually.
Since Its been a week, (long enough for everyone who
wanted to to think of the problem) I'll present my solution.
Generate a graph with points represented by people, and
then draw lines between those people who do not know
eachother. This will produce one or more sets of
connected points. For each connected set, pick a point,
and color it red. Then color all those points connected
to it green. Color the points connected to these red, and
so on. Repeat until all of the points in the connected set are
colored, then move on to the next set.
Put all the red points in one group and all the green
points in another group.
The only problem we will get into is if a point is colored
more then once. In order for this to happen there would
need to be a closed loop in the graph. But any closed
loop would have to have as many lines as it did vertices,
hense as many introductions as people. So according to
the first version of the problem this couldn't happen.
Also, even if we had a closed loop with an even number
of vertices this would still be ok, since by parity, the
point would just be colored the same color twice.
Cheers,
Mr. M.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: New Problem; Introductions all around
« Reply #6 on: Aug 16th, 2002, 8:37pm » |
Quote Modify
|
Yes, nice proof, it is precisely the graph theoretic translation of what I wrote up, perhaps a little easier to see. Certainly more colorful! 
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print