Решение задачи.
Каждому школьнику сопоставим тройку целых чисел m, n, k, где
m — номер спортивной секции
n — номер научного кружка
k — номер художественной студии
Здесь m, n, k = 0, 1, 2, 3, 4, 5, 6, 7
Число таких троек (m, n, k) будет равно 512 = 8*8*8, что больше 505 — количеству
школьников по условию задачи.
Рассмотрим случай когда все школьники имеют несовпадающие номера, хотя бы по
одной позиции. Определим тогда некоторую группу из всевозможных троек чисел не дружищах школьников,
следующим образом:
(0, 0, 0) (0, 1, 1) (0, 2, 2) (0, 3, 3) (0, 4, 4) (0, 5, 5) (0, 6, 6) (0, 7, 7)
(1, 7, 0) (1, 0, 1) (1, 1, 2) (1, 2, 3) (1, 3, 4) (1, 4, 5) (1, 5, 6) (1, 6, 7)
(2, 6, 0) (2, 7, 1) (2, 0, 2) (2, 1, 3) (2, 2, 4) (2, 3, 5) (2, 4, 6) (2, 5, 7)
(3, 5, 0) (3, 6, 1) (3, 7, 2) (3, 0, 3) (3, 1, 4) (3, 2, 5) (3, 3, 6) (3, 4, 7)
(4, 4, 0) (4, 5, 1) (4, 6, 2) (4, 7, 3) (4, 0, 4) (4, 1, 5) (4, 2, 6) (4, 3, 7)
(5, 3, 0) (5, 4, 1) (5, 5, 2) (5, 6, 3) (5, 7, 4) (5, 0, 5) (5, 1, 6) (5, 2, 7)
(6, 2, 0) (6, 3, 1) (6, 4, 2) (6, 5, 3) (6, 6, 4) (6, 7, 5) (6, 0, 6) (6, 1, 7)
(7, 1, 0) (7, 2, 1) (7, 3, 2) (7, 4, 3) (7, 5, 4) (7, 6, 5) (7, 7, 6) (7, 0, 7)
Здесь третья компонента будет суммой чисел m, n по модулю 8.
Очевидно к-во троек равно 64.
Всего будет 8 подгрупп троек одинаковых по 3 компоненте. Очевидно внутри этих подгрупп
нет троек у которых совпадают точно две компоненты. И также очевидно между двумя тройками из
разных подгрупп не будет троек у которых совпадают точно две компоненты.
То есть в этой группе школьники не дружат.
Другую группу можно получить изменяя третью компоненту добавив к ней 1 и взяв это число по модулю 8.
Тогда подгруппы будут следующего вида:
(0, 0, 1) (0, 1, 2) (0, 2, 3) (0, 3, 4) (0, 4, 5) (0, 5, 6) (0, 6, 7) (0, 7, 0)
(1, 7, 1) (1, 0, 2) (1, 1, 3) (1, 2, 4) (1, 3, 5) (1, 4, 6) (1, 5, 7) (1, 6, 0)
(2, 6, 1) (2, 7, 2) (2, 0, 3) (2, 1, 4) (2, 2, 5) (2, 3, 6) (2, 4, 7) (2, 5, 0)
(3, 5, 1) (3, 6, 2) (3, 7, 3) (3, 0, 4) (3, 1, 5) (3, 2, 6) (3, 3, 7) (3, 4, 0)
(4, 4, 1) (4, 5, 2) (4, 6, 3) (4, 7, 4) (4, 0, 5) (4, 1, 6) (4, 2, 7) (4, 3, 0)
(5, 3, 1) (5, 4, 2) (5, 5, 3) (5, 6, 4) (5, 7, 5) (5, 0, 6) (5, 1, 7) (5, 2, 0)
(6, 2, 1) (6, 3, 2) (6, 4, 3) (6, 5, 4) (6, 6, 5) (6, 7, 6) (6, 0, 7) (6, 1, 0)
(7, 1, 1) (7, 2, 2) (7, 3, 3) (7, 4, 4) (7, 5, 5) (7, 6, 6) (7, 7, 7) (7, 0, 0)
Повторяя эту процедуру 7 раз можно получит 8 таких групп школьников которые также не дружат внутри каждой группы.
Но здесь надо учесть, что всего школьников 505, то есть из этих 8 групп надо убрать 7 троек-школьников, так как 7 = 512-505.
Тогда получиться, что хотя бы одна из групп будет содержать группу из 64 троек-школьников.
Нетрудно показать, что указанное свойство будет иметь место и в случае когда могут быть тройки у которых есть все совпадающие компоненты.
Дело в том что школьники по условию задачи не дружат, если у них будут все компоненты совпадать (по условию задачи дружат: должны совпадать ровно две компоненты).
Приведём пример такой группы с дублирующими тройками чисел.
(0, 0, 1) (0, 1, 2) (0, 2, 3) (0, 3, 4) (0, 4, 5) (0, 5, 6) (0, 6, 7) (0, 7, 0)
(1, 7, 1) (1, 0, 2) (1, 1, 3) (1, 2, 4) (1, 3, 5) (1, 4, 6) (1, 5, 7) (1, 6, 0)
(2, 6, 1) (-, --, --) (2, 0, 3) (-, --, --) (2, 2, 5) (2, 3, 6) (2, 4, 7) (2, 5, 0)
(3, 5, 1) (3, 6, 2) (3, 7, 3) (-, --, --) (3, 1, 5) (3, 2, 6) (3, 3, 7) (3, 4, 0)
(4, 4, 1) (4, 5, 2) (-, --, --) (4, 7, 4) (4, 0, 5) (4, 1, 6) (4, 2, 7) (4, 3, 0)
(5, 3, 1) (5, 4, 2) (5, 5, 3) (5, 6, 4) (5, 7, 5) (5, 0, 6) (5, 1, 7) (5, 2, 0)
(6, 2, 1) (6, 3, 2) (6, 4, 3) (6, 5, 4) (6, 6, 5) (6, 7, 6) (6, 0, 7) (6, 1, 0)
(7, 1, 1) (7, 2, 2) (7, 3, 3) (7, 4, 4) (7, 5, 5) (7, 6, 6) (7, 7, 7) (7, 0, 0)
--------------------------------------------------------------------------------------------------
(1, 7, 1) ---------- (7, 3, 3) (0, 3, 4) ---------------------- (2, 4, 7)
(5, 3, 1)
В этой группе будет 5 дублирующих троек (они вынесены внизу таблицы) и четыре отсутствующих троек помеченных как (-, --, --).
В каждой подгруппе будут только тройки которые не дружат между собой и точно также тройки из разных подгрупп не будут дружить между собой.
Всего таких групп может быть меньше или равно восемь и найдётся группа которая будет содержать больше 63 троек.