Author |
Topic: 6 PERSON ACQUAINTANCE (Read 10695 times) |
|
Aaron
Newbie
Gender: 
Posts: 14
|
 |
6 PERSON ACQUAINTANCE
« on: Aug 30th, 2002, 2:26pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: 6 PERSON ACQUAINTANCE
« Reply #1 on: Aug 31st, 2002, 9:38am » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
rugga
Newbie
Gender:
Posts: 21
|
|
Re: 6 PERSON ACQUAINTANCE
« Reply #2 on: Sep 1st, 2002, 3:34am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: 6 PERSON ACQUAINTANCE
« Reply #3 on: Sep 2nd, 2002, 11:43pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aaron
Newbie
Gender:
Posts: 14
|
|
Re: 6 PERSON ACQUAINTANCE
« Reply #4 on: Sep 3rd, 2002, 12:21pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print