This discussion is closed.
Psiko
Badges: 0
#21
Report 16 years ago
#21
(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
0
4Ed
Badges: 15
Rep:
?
#22
Report 16 years ago
#22
as mentioned earlier, u can use the pigeon hole principle to solve that one ALOT faster.....
0
Psiko
Badges: 0
#23
Report 16 years ago
#23
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.
0
theone
Badges: 0
Rep:
?
#24
Report 16 years ago
#24
If there are more pidgeons than boxes, there has to be more than one pidgeon in at least one box.
0
X
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Had lockdown impacted your relationships?

Yes, my partner and I are struggling (30)
7.77%
Yes, my partner and I broke up (33)
8.55%
Yes, it's hard being around my family so much (86)
22.28%
Yes, I'm feeling lonely isolating alone (50)
12.95%
No, nothing has changed (117)
30.31%
No, it's helped improve my relationships (70)
18.13%

Watched Threads

View All
Latest
My Feed