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
Menu
Grade: 11
        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.
9 months ago

Answers : (1)

Arun
13856 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.

 

Regards

Arun (askIITians forum expert)

9 months ago
Think You Can Provide A Better Answer ?
Answer & Earn Cool Goodies

Get Extra Rs. 1,590 off

COUPON CODE: SELF10


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


Get Extra Rs. 233 off

COUPON CODE: SELF10

Ask Experts

Have any Question? Ask Experts

Post Question

 
 
Answer ‘n’ Earn
Attractive Gift
Vouchers
To Win!!! Click Here for details