Grade 11Algebra

If each person in a group of n people is a friend of at least half the people in the group,then prove that it is possible to seat them in a circle so that everyone sits next to a friend of his/hers.

suhail

8 Years agoGrade 11

3 Answers

Arun

8 Years ago

the statement is true for 2 people (and less than two doesn't count as a group). Because each must be friends with the other.

if true for n > 2people and a new one arrives, consider separately n even or odd.

If n = 2k, then the new arrival makes a group of 2k + 1, and by the premiss of the problem, everyone in this new group must be friends with at least k + 1 of the group. So the new arrival has k + 1 friends already seated and at most k - 1 people separating them so he must have two adjacent friends he can be placed between.

If n = 2k + 1 his arrival makes 2k + 2 and he must have k + 1 friends in that group. Again they are already seated with at most k people separating them so there must be two adjacent that he can be seated between.

So, in either case the statement is true for n + 1, and is therefore true for all n >2.

The key to the solution is that with the arrival of a new person he has in any case a minimum of k + 1 friends among 2k or 2k + 1 people already seated.

Regards

Arun (askIITians forum expert)

Siddhant Kumar

4 Years ago

If suppose n is a multiple of 3 and then a polygon(inscribed polygon) is made of n people seated then one person has at least half the friends as per question

Then that will be out of (n-1) people

Or it will be any (n-1)/2 people

Now for a person who has friends out of (n-1)/2 people by polygon diagonal formula we observe one vertice(here one person)has almost (n-3) projections and also that (n-1)/2 = [(n-3)/2]+1 therefore again the one person must have half of these projections as friends but according to formula 1 more is needed to complete total friends which can be done by selecting any one more projection or any adjacent vertex thus totalling to (n-1)/2 for n people each which means a person of the group can have a friend next to him/her as [(n-3)/2]+1 and each vertex is a person