Welcome to NRICH.

 
People at a party knowing each other (or not)
By Anonymous on Friday, August 25, 2000 - 04:56 pm:

hello,

I came across this question, which I think has to do with networks/graphs:

The problem is the following:

Prove that among 6 people in a room there are at least three who know one another, or at least three who do not know one another

Thank you very much,

By Tom Hardcastle (P2477) on Friday, August 25, 2000 - 06:06 pm:

The problem is isomorphic to two colouring a network of six points, all joined to each other. The problem indicates that at least one triangle of a colour must be formed. Playing about with such a network should convince you. I think I saw a proof by construction somewhere, so I might dig it out or try and reproduce it. This sort of problem is dealt with by Ramsey theory.

Tom

By Tom Hardcastle (P2477) on Friday, August 25, 2000 - 11:24 pm:

C:
C:ramsey.giframsey.gif

By Tom Hardcastle (P2477) on Friday, August 25, 2000 - 11:25 pm:

Ok, I can prove it. (see above, made a mess of the file upload thing) Taking a set of six points, choose one point. Now there must be at least three points of the same colour coming off this point, so choose one colour and put those three lines in. Now you've got to put in two lines of the other colour straight away, because otherwise you would have a triangle. But then you have two points where you can't put a line of either colour without forming a triangle. So, you have to form a triangle.

So, if you have six people at a party, there is either a group of three people who all know each other, or there is a group of three people none of whom know each other.

Tom