must know

AIEEE Preparation › Algebra questions › must know

There are n people at a party. Prove that there are two of them such that of the
remaining n âˆ’ 2 people, there are at least \left[\frac{n}{2} \right]-1 of them each of whom knows
both or else knows neither of the two.

[ .] denotes greatest integer function

#Mathematics #Algebra

UP 0 DOWN 0 0 2
Post on FacebookPost anonymously?

2 Answers

Devil ·2009-10-20 10:27:13

This should have been posted in the Olympiad section!
Suppose I denote the n people of the party by a n-gon, each vertex representing a people. I color the edges i.e the lines joing the vertices blue or black depending on whether the line joining the vertices and hence the people know each other or not! There are thus ⁿC₂ edges!
If i leave out the adjacent vertex for some vertex say A_i, then we have (n-2) lines emanating from it....So on applying the Pigeon-Hole-Principle, we have [n2]-1 lines of the same color!
Now I need a diagram...( and unfortunately my paint-resolution is too bad), so consider menatlly the vertices .......we thus can prove that from A₁ to A₆, there must exist at least 2 vertices that have [n2]-1 lines of the same color and yet joing the same vertices!

Thus proved!