Question: Let a and b be positive integers, with a ≤ b. A certain class has b students, and among any a of them there is always one that is friends with the other a − 1. Find all values of a and b for which there must necessarily be a student who is friends with everyone else in the class.

My thoughts are that a can be any integer greater than 1 because a student in a class of one cannot have friends, and that b must equal a, as one student must be friends with everyone and a-1 equals maximum number of friendships. Therefore there are infinites values for a and b, provided that a is greater than 1.

Is my solution correct and logical? If it isn't please explain why, thanks.


You need to observe what the question is asking: it doesn't ask how many $(a,b)$ pairs there are that satisfy this condition, it asks you to list all of those pairs. You're right that $(b,b)$ will always satisfied this condition, but for you to have the complete answer, you need to show that there are no other solutions except for $(b,b)$.

As it turns out, there are other solutions. Try $a=4$ and $b=5$. I can give a more detailed explanation if you want, but it turns out that you'll have to get somebody who is friends with everyone.

I don't know the complete solution, but I can say that yours is not complete.

  • $\begingroup$ If a equals 4 then than the maximum number of friendships is 3. The question states that there must be a student who is friends with everyone. So doesn't a have to equal b for that to be satisfied? $\endgroup$ – user266729 Sep 18 '17 at 22:45
  • $\begingroup$ @Okeh If $a=4$, every group of $4$ people will have somebody who is friends with the other $3$. That doesn't mean that the maximum number of friends a person can have is $3$. $\endgroup$ – Kevin Long Sep 18 '17 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy