Friends!

Probability Level 3

In a class of 1250 people, all my friends have more friends than me, but none of my friends are friends with other friends of me. If I have the largest number of friends I can possible have, how many friends do I have?

Details and Assumptions

  • Friendship can only occur between two different people.
  • My friend's friends are not necessarily my friends.


The answer is 624.

Ashwin Padaki by Ashwin Padaki , 20, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Krishna Shankar
Jun 9, 2015

This answer can be arrived at by smart guessing. Here are the details as they stand: FRIENDS written like this refers to your set of friends. None of your FRIENDS are friends with each other. Therefore, all of their friends (other than you) must be from those who aren't your friends but in your class, whom we'll call "outsiders". Then, if we suppose that you have 1249 FRIENDS, none of them can be friends with each other which means you have more friends than all of your friends. Clearly that won't work.

Here is a smart guess, let us divide these people into two equal (nearly, since the number is not even) parts: 625 FRIENDS and 624 outsiders. Now this is what we see: If each one of your FRIENDS has ALL outsiders as his/her friends, then each of your FRIEND has 625 friends (624 outsiders and 1 yourself) , and you will also have 625 friends, which will violate the rule that you must have lesser number for friends than each of your FRIENDS. Then, let's try to split as 624 FRIENDS and 625 outsiders. Then, using the same conditions, each of your FRIENDS will have 625+1 friends. You will have 624 FRIENDS. We have then shown that when you have 624 FRIENDS, everything works out fine. But if you have any more, you will end up having more friends than your friends. This means 624 has to be the maximum. Therefore the maximum number of friends you can have is 624.

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Vishnu Bhagyanath
Jun 22, 2015

It is stated that he the author has maximum number of friends, implying we need to tailor our answer in such a way to minimize the number of friends' friends.

Assume the author has n n friends. The smallest number of friends these friends can have, satisfying the given condition were if all the friends had a same group of common friends. Which were not a part of the original group. i.e. if A , B , C , D , E , F , G A,B,C,D,E,F,G were examples, A , B , C , D , E a n d F A,B,C,D,E \space and \space F can have the same common friend G G while you are not friends with G G . Noting this fact, we can say that his n n friends have all friends common, and atleast 1 friend more than the author. i.e. They all have the same common n + 1 n+1 friends.

So the total number of people in the room, including oneself is n + ( n + 1 ) + 1 = 1250 n + (n+1) + 1 = 1250 n = 624 \boxed{n = 624}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...