Click to Chat

1800-1023-196

+91-120-4616500

CART 0

• 0

MY CART (5)

Use Coupon: CART20 and get 20% off on all online Study Material

ITEM
DETAILS
MRP
DISCOUNT
FINAL PRICE
Total Price: Rs.

There are no items in this cart.
Continue Shopping
`        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.`
2 years ago

Arun
24739 Points
```							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. RegardsArun (askIITians forum expert)
```
2 years ago
Think You Can Provide A Better Answer ?

## Other Related Questions on Algebra

View all Questions »

### Course Features

• 731 Video Lectures
• Revision Notes
• Previous Year Papers
• Mind Map
• Study Planner
• NCERT Solutions
• Discussion Forum
• Test paper with Video Solution

### Course Features

• 101 Video Lectures
• Revision Notes
• Test paper with Video Solution
• Mind Map
• Study Planner
• NCERT Solutions
• Discussion Forum
• Previous Year Exam Questions