Olympiad Maths Prep

Track / Stage 5 / 366 of 400 #966 of 2000

Problem 966

AIME late
Combinatorics Difficulty 5.9 Prove it

1. Prove that in a group of 6 students, there are 3 students such that each knows the other two, or there are 3 students such that each does not know either of the other two students.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Solution. Let AA be one of these students. Among the remaining 5 students, there are three who know AA, or there are three who do not know AA. Let's consider the case when we have three acquaintances of AA. If among these students there are two who know each other, then together with AA we have three students who all know each other. Otherwise, we have three students such that each does not know either of the other two students. The case when we have three students who are not acquaintances of AA is considered analogously. We leave the details to the reader as an exercise.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.