Two out of five in a group have the same number of friends.....

Question

I recently came across a problem-

Prove that in a group of five people,there are two who must have the same number of friends in the group.

I assume it must be solved by Pigeon Hole Principle (PHP).But I cannot do this.I know a geometric solution of a similar problem.I want a purely arithmetical proof.I also have problem in associating this problem with real life.

Thank you for any solutions/hints.

Answer 1

In a group of five people, the maximum amount of friends any given person can have is four, and the minimum amount of friends any given person can have is zero. But if one person has four friends, then all other people must have at least one friend; and if one person has no friends, then all other people cannot have four friends. Now, by the pigeonhole principle...

Answer 2

There is only one order-less combination with each person having a different number of friends:

• A person with $0$ friends
• A person with $1$ friend
• A person with $2$ friends
• A person with $3$ friends
• A person with $4$ friends

The person with $4$ friends must be friend with all the others.

This makes it impossible for any person to have $0$ friends.

So the above combination is impossible.

Answer 3

Because of the symmetry of the friendship relation one person is completely determined by his friends, the second person can choose to be friend with the first or not. Irregardless of the choice they then get the same friend count. The third person must then break this tie by befriending one of them. But then him and that chosen person get a tie which the next person must break and so on forever.

If this reasoning works, then we could replace group size 5 with any positive number and it would still be impossible.

---

Here is a Matlab/Octave snippet showing that for > 16000 random configurations for sizes of matrices $N \times N$ for $N\in [6,20]$ we do not find any where all $N$ have different number of friends:

for N_ = 6:16

[xs,ys] = meshgrid(1:N_,1:N_);

[i_x,i_y] = find(xs < ys);

disp(['Running 16*1024 random symmetric matrices for size ', num2str(N_)]);

for o_1 = 1:1024*16

T_vec = rand(N_*(N_-1)/2,1)>0.5;

T = zeros(N_,N_);

T(xs < ys) = T_vec;

T = T'+T; % Construct symmetric matrix since friendship is symmetric.

if sum(sum((sum(T,1) - sum(T,1)')==0)) == N_ % If no two had the same number of friends, then this would be true.

disp("Found one configuration !");

end

end

end