Someone got the BMO1 preparation sheet(Original post by 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.
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
Turn on thread page Beta
Some Maths problems watch
- 15-12-2003 21:31
- 16-12-2003 00:32
as mentioned earlier, u can use the pigeon hole principle to solve that one ALOT faster.....
- 16-12-2003 17:42
Would you mind explaining the pidgeon-hole principle please? I may have to do BMO2 in a couple of months, and I heard it's useful for that.
- 16-12-2003 17:47
If there are more pidgeons than boxes, there has to be more than one pidgeon in at least one box.