Turn on thread page Beta

    (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.
    Someone got the BMO1 preparation sheet

    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

    as mentioned earlier, u can use the pigeon hole principle to solve that one ALOT faster.....

    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.

    If there are more pidgeons than boxes, there has to be more than one pidgeon in at least one box.
Turn on thread page Beta
Updated: December 16, 2003
Cats or dogs?
Useful resources

Make your revision easier


Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here


How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.