Олимпиадная задача о школьниках и одноклассниках — принцип Дирихле, 6-8 класс

  а) Разобьём всех 60 школьников на группы одноклассников. Если среди школьников нет 15 одноклассников, то в каждой группе не более 14 школьников. Пусть k – число групп, состоящих из двух и более школьников. Такие группы назовём большими.

  Из условия вытекает, что  k ≤ 4  (иначе, взяв по двое из пяти больших групп, мы получим 10 школьников, среди которых не будет трёх одноклассников). Рассмотрим два случая.

  1.  k ≤ 3.  Тогда общее число школьников в больших группах не превышает  14·3 = 42.  Следовательно, найдётся 18 школьников, которые не входят в большие группы, а значит, не имеют ни одного одноклассника! Противоречие.

  2.  k = 4 . Тогда общее число школьников в больших группах не превышает 56. Следовательно, найдутся 4 школьника, каждый из которых не имеет одноклассников. Взяв этих четверых и добавив к ним по два из всех четырёх больших групп, мы получим даже 12 школьников, среди которых не найдётся трёх одноклассников. Противоречие.   б) Не обязательно. Пример: по 15 школьников из четырёх классов.

а) Обязательно; б) не обязательно.