The Gateway to Computer Science Excellence
0 votes
There is a party of $n$ people. Each attendee has at most $r$ friends in the party. The friend circle of a person includes the person and all her friends. You are required to pick some people for a party game, with the restriction that at most one person is picked from each friend circle. Show that you can pick $\dfrac{n}{r^{2}+1}$ people for the game.
in Combinatory by
edited by | 103 views
Some intuition,

Say we have total friends,n = 10

So, at most one people can have n-1 friends = 9 = r

But we are supposed to pick $\bf{at most}$ 1 friend, that means, I can pick 0(no friend) or a 1 friend.

So, two cases,

i. Minimum case:

If I pick 1 friend friend of each out of n = 10 people

then $\frac{n}{r^2+1}$ = 10/(1^2+1) = 5.


ii. Maximum Case:

If 0 friend picked.

then $\frac{n}{r^2+1}$ = 10/(0^2 + 1) = 10.


This calculation can be generalized with the help of a graph.

@`JEET Can you explain to me what have you done?

I just take the sample input to verify.

In case of picking $0$ friends I am getting the answer as Maximum.
You can try with $0$, $1$ which is asked in the question and you will get your answer.

Its so easy.

Just substitute the values.

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,489 answers
95,296 users