Задача 6.
Экскурсионная группа из 6 туристов осматривает достопримечательности. Около каждой достопримечательности три человека фотографируются, а остальные их фотографируют. После какого минимального числа достопримечательностей каждый турист будет иметь фотографии всех остальных участников экскурсии?
Ответ на Задачу 6.
Ответ: после 4 достопримечательностей.
Решение:
Оценка. Всего нужно провести 6 · 5 = 30 фотографирований (рассматриваем фотографирование только между двумя людьми $A$ и $B$, то есть если человек $A$ сфотографировал 3 других участников $B$, $C$, $D$ на одной фотографии — это 3 фотографирования $A$ ⟶ $B$, $A$ ⟶ $C$, $A$ ⟶ $D$).
За одну достопримечательность может произойти не более 3 · 3 = 9 новых фотографирований. Таким образом, трёх достопримечательностей не хватит.
Приведем пример, как можно организовать фотографирования около четырёх достопримечательностей. Пронумеруем людей от 1 до 6. Тогда мы можем организовать всё следующим образом:
(123) ⟶ (456)
(145) ⟶ (236)
(256) ⟶ (134)
(346) ⟶ (125)
Нетрудно проверить, что каждый сфотографирует каждого хотя бы один раз.
