Maths Olympiad Prep

Library / /60 of 69

Combinatorics Difficulty 6.9 National olympiad Prove it Mongolia

Consider a class of students. Within any group of six students, there are always two students who are not friends. Furthermore, if we select two of these non-friends, there will always be a student among the remaining four who is friends with both of the chosen students. How many students are there in the class altogether?
(Nyamdavaa Amar)

Solution

Answer: 25.
Let's denote the number of students in the class as NN. To begin, we show that it is possible for NN to equal 25. The class is divided into five groups, with each group consisting of five students who are not friends with each other. Furthermore, any two different groups of two children are friends. If we select a group of six students, there will always be at least two children from the same group who are not friends. As a result, among these children, there will be at least one child who is not part of their respective groups but is friends with them.

Next, we prove that NN is less than or equal to 25. Let's assume, by contradiction, that N26N \ge 26. We select a student, denoted as a1a_1, who has at least N5N-5 friends. If a1a_1 does not have at least five non-friends, it would contradict our assumption. We then choose another student, denoted as a2a_2, who is a friend of a1a_1. By following this pattern, we find that students a1,a2,,a5a_1, a_2, \dots, a_5 have at least N251N-25 \ge 1 common friends. This directly contradicts the given condition that there are no pairs of non-friend students among any group of six students.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.