Author |
Topic: Cliques (Read 348 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
A) There are 100 students taking an exam.
Every student knows at least 67 other students (where 'knowing' is a symmetric relation).
Prove that there is a set of four students in the room, such that every two from the four know each other.
(Let us call such a set a 'clique'.)
B) Two students in the room, called Bonnie and Clyde, know each other.
Is there a clique of four students which includes Bonnie and Clyde?
A student wanders in, late for the exam, so that there are now 101 students in the room.
C) Does each student know at least 67 others?
D) Is there now a clique of four students?
|
| « Last Edit: Jan 27th, 2004, 7:50am by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
 |
Re: Cliques
« Reply #1 on: Jan 27th, 2004, 7:22am » |
 Quote  Modify
|
I fail to see how 'knowing' being reflexive ([forall]x: x knows x) is at all relevant - I suspect symmetric ([forall](x,y): (x knows y)[bigto](y knows x)) was intended.
Assuming symmetry:
A)::Take any student, Z, let Y be someone he knows. Then since Z and Y each do not know at most 32 of the other 98 students, there are at least 98-32-32=34 students they both know. Any one of them, X, does not know at most 32 of the other 33 known by both Z and Y, so there is at least one student, W, known by all 3. By symmetry, any two of W,X,Y and Z know each other - in fact, since X can be any of the 34 students known by Z and Y, there are at least 17 cliques which have both Z and Y as members.
::
B)::Let Bonnie and Clyde be Z and Y rexpectively. The rest of the above proof applies, so they are in at least 17 cliques of 4.
::
C)::We have no information about how many people the new student knows - if, say, he's not only late but at the wrong school, he might well not know anyone, so the answer is a resounding "maybe" - it's also possible he does know (at least) 67 people already present.
::
Without symmetry, I get bogged down very quickly.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Cliques
« Reply #2 on: Jan 27th, 2004, 7:45am » |
Quote Modify
|
You are right, that should be symmetric. Now corrected. (Blame my rusty maths.)
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Cliques
« Reply #3 on: Jan 27th, 2004, 6:12pm » |
Quote Modify
|
D)::No - The new girl was so overwhelmingly beautiful that Clyde completely forgot the existance of Bonnie!  (Alright, that only works if every clique has at least one susceptable male.)::
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Cliques
« Reply #4 on: Jan 28th, 2004, 1:42pm » |
Quote Modify
|
What if all 100 were boys and the 1 person that walked in was a gergeous gal? 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Cliques
« Reply #5 on: Jan 29th, 2004, 6:23am » |
Quote Modify
|
As rmsgrey showed, there are quite a few cliques for every pair of students. If so, can the number "67" be relaxed?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Cliques
« Reply #6 on: Jan 29th, 2004, 8:04am » |
Quote Modify
|
Can 67 be relaxed? ::No::
Proof:
::divide the students into three groups, of 33, 33 and 34 members. Let each student know all and only the students not in their own group. The students in the group with 34 members each know 66 others; those in the other groups each know 67 others. Since a clique must take each member from a different group, and there are only 3 groups, there are no cliques of 4 or more. Every student is in at least 1089 (33*33) cliques of 3 though, and introducing the minimum 17 pairs of students (all in the group of 34) to each other to have everyone know 67 others will turn every clique of 3 into a clique of 4 (though each clique of 4 will come from 2 different cliques of 3) creating a very large number of cliques of 4 (1089*17 of them)
::
If, instead of adding an extra student to the 100 with their numerous 4-cliques, you consider what happens if you instead start with 101 students, each of which knows at least 67 others, you get the opposite result (ignoring Icarus' hypothesis) - it's possible to arrange them so that there are no cliques of 4 ::two groups of 34 and one of 33 with everyone knowing precisely those students in other groups - two thirds of the students know 67 others, the remainder 68, and no clique exceeds 3 members::
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Cliques
« Reply #7 on: Jan 29th, 2004, 9:03am » |
Quote Modify
|
Quote:| If, instead of adding an extra student to the 100 with their numerous 4-cliques, you consider what happens if you instead start with 101 students, |
|
Yes, I wanted to rewrite the bit about a student being late, but you had already quoted it.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Cliques
« Reply #8 on: Jan 30th, 2004, 9:14am » |
Quote Modify
|
Of course, the questions lead fairly directly into graph theory - particularly tripartite graphs. If I could remember more of my graph theory, I'd probably be able to quote some relevant results, but I can't so I can't.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print