Some Maths problems

Year 12s: what will be the first way you research your future options? >>

Scroll to see replies

theone

Here's an interesting one:

In a group of 6 people, show that there must be 3 people who know each other or don't know each other.

Someone got the BMO1 preparation sheet :tongue:

WLOG, in a group of 6 people there is a person X, and a remaining group of 5. X must EITHER know at least 3 people from the group of 5 or not know at least three people, ie. if he knows 2 people, there are 3 he doesn't know, if he knows 1 person there are 4 people he doesn't know, etc. Assume X knows 3 or more people from the group. If in this group of 3 or more there are three or more people who all know each other then the condition above is satisfied. If there are a pair of people who know each other in that group, WLOG A and B, then there are three people who know each other because X, A and B all know each other, so the condition is satisfied. If none of the people in that group of 3 or more people know each other then there are at least 3 people who do not know each other, and the condition is satisfied.

Now, assume that X doesn't know 3 or more people in that remaining group of 5 and follow the same method above, to prove that in a group of 6 people, there are either at least 3 people who all know each other, or at least 3 people who do not know each other.

That proof is quite complicated because it's just a load of words, and it's hard to understand, but I did my best :tongue:

Reply 21