CMI2019-B-3

Question

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.

Comments

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.

Answer 1