wu :: forums - Print Page


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

        riddles >> medium >> 6 PERSON ACQUAINTANCE
        
(Message started by: Aaron on Aug 30^th, 2002, 2:26pm)

Title: 6 PERSON ACQUAINTANCE
Post by Aaron on Aug 30^th, 2002, 2:26pm

Hmm, let's see.

How about because you can't group 6 people into less than 3 groups, each containing no more than 2 people?

With the given restriction, you can only have a maximum of 2 groups x 2 people per group = 4 people.

No matter how you cut it, there are going to be either more than 3 groups (> 3 mutually unacquainted), or the largest group is going to have more than 3 people (> 3 mutually acquainted).

IMO, this really should have been in the easy section.
:P

Title: Re: 6 PERSON ACQUAINTANCE
Post by AlexH on Aug 31^st, 2002, 9:38am

I think you misread the problem. Mutually unacquainted is not the negation of mutually acquainted, if (A knows B) and (D knows E), then groups {a,b,c} and {d,e,f} are neither mutually acquainted nor mutually unacquainted. You're right the problem is easy, but its not THAT easy :D

Title: Re: 6 PERSON ACQUAINTANCE
Post by rugga on Sep 1^st, 2002, 3:34am

Quote:

Prove that in any group of 6 people, at least 3 must be either mutually acquainted with each other, or mutually unacquainted with each other.

I'll take a stab at this using proof by contradiction. Since it's
somewhat wordy I've bolded the milestones.

Assume there is no group of 3 mutually acquainted people and no
group of 3 mutually unacquainted people. Then pick 2 unacquainted
people (there must be 2 such people since otherwise everyone would
be mutually acquainted). Call these 2 people A & B, and the others
C-F.

A and B are not acquainted.

If C is acquainted with neither A nor B, then A,B&C are mutually
unacquainted. Therefore C must be acquainted with one or both of
A and B. The same reasoning of course applies to D-F as well.

Each of C, D, E & F is acquainted with either A or B or both.

But now note that at most 2 of the C-F people can be acquainted
with A. For if 3 of them (say C,D&E) were acquainted with A, then
2 of them (say C&D) must be acquainted with each other. Otherwise
C,D&E would be mutually unacquainted. But then we have C&D both
acquainted with A and with each other, so they form a group of 3
mutually acquainted people. So at most 2 of the C-F people can
be acquainted with A. The same reasoning applies to B as well.

At most 2 of C, D, E & F are acquainted with A, and
at most 2 of C, D, E & F are acquainted with B.

Since all of C-F are acquainted with one of A or B, and at most
2 of them are acquainted with either of A or B, it must be the
case that exactly 2 of C-F are acquainted with A (and are not
acquainted with B), and the other 2 are acquainted with B (and
not with A). Let C&D be the ones acquainted with A, and E&F
the ones acquainted with B.

C & D are acquainted with A but not with B.
E & F are acquainted with B but not with A.
C E / / A B \ \ D F

Finally, since C&D are both acquainted with A, they cannot be
acquainted with each other. But then B,C&D are mutually
unacquainted, which is a contradiction.

Title: Re: 6 PERSON ACQUAINTANCE
Post by Chronos on Sep 2^nd, 2002, 11:43pm

Another way to look at it is as a graph, with 6 vertices (people) and 15 edges between them. Each edge can be in one of two states, depending on whether the people connected by it are friends or strangers. For short, let's call those states A and B.

Now, consider a person W. That person has five edges connecting to him, so at least three edges must be the same. We can say without loss of generality that there are at least three edges in state A, and that they connect to people X, Y, and Z. Now, edge XY can't be in state A, since then WXY would all have the same relationship to each other: if state A is "mutually known", then they are three mutual acquaintances; if A is "mutually unknown", then they are three strangers. Similarly, neither edge XZ nor YZ can be in state A. So that means that XY, XZ, and YZ are all B, and so are either mutual acquaintances or mutual strangers.

Title: Re: 6 PERSON ACQUAINTANCE
Post by Aaron on Sep 3^rd, 2002, 12:21pm

Ooops... I did not concider the cases properly. I guess this is what happens when I do riddles right after an extanded session of coding. :P