wu :: forums - Print Page


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

        riddles >> easy >> Cliques
        
(Message started by: THUDandBLUNDER on Jan 26^th, 2004, 6:54pm)

Title: Cliques
Post by THUDandBLUNDER on Jan 26^th, 2004, 6:54pm

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?

Title: Re: Cliques
Post by rmsgrey on Jan 27^th, 2004, 7:22am

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)::[hide]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.
[/hide]::

B)::[hide]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.
[/hide]::

C)::[hide]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.
[/hide]::

Without symmetry, I get bogged down very quickly.

Title: Re: Cliques
Post by THUDandBLUNDER on Jan 27^th, 2004, 7:45am

You are right, that should be symmetric. Now corrected. (Blame my rusty maths.)

Title: Re: Cliques
Post by Icarus on Jan 27^th, 2004, 6:12pm

D)::[hide]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.)[/hide]::

Title: Re: Cliques
Post by Sameer on Jan 28^th, 2004, 1:42pm

What if all 100 were boys and the 1 person that walked in was a gergeous gal? :o

Title: Re: Cliques
Post by Barukh on Jan 29^th, 2004, 6:23am

As rmsgrey showed, there are quite a few cliques for every pair of students. If so, can the number "67" be relaxed?

Title: Re: Cliques
Post by rmsgrey on Jan 29^th, 2004, 8:04am

Can 67 be relaxed? ::[hide]No[/hide]::

Proof:
::[hide]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)
[/hide]::

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 ::[hide]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[/hide]::

Title: Re: Cliques
Post by THUDandBLUNDER on Jan 29^th, 2004, 9:03am

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.

Title: Re: Cliques
Post by rmsgrey on Jan 30^th, 2004, 9:14am

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.