0

Guest

Courses New

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.

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.

Grade:11

3 Answers

Arun
25750 Points
6 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
14 Points
one year 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
Siddhant Kumar
14 Points
one year ago
I made an error 
Actually n has to be odd 
Rest is same
 
The above one helped a bit to correct 
................
......
 
 
 
 
 
..........
 
...........
100 characters ......
 
.........

Think You Can Provide A Better Answer ?

Other Related Questions on Algebra

View all Questions »

ASK QUESTION

Get your questions answered by the expert for free

Answer and earn gift vouchers

Win Gift vouchers upto Rs 500/-

View courses by askIITians

Design classes One-on-One in your own way with Top IITians/Medical Professionals

Click Here Know More

Complete Self Study Package designed by Industry Leading Experts

Click Here Know More

Live 1-1 coding classes to unleash the Creator in your Child

Click Here Know More

a Complete All-in-One Study package Fully Loaded inside a Tablet!

Click Here Know More