Минимум разных героев на фото: олимпиадная задача по комбинаторике 8-11 класс
Задача
В семейном альбоме есть десять фотографий. На каждой из них изображены три человека: в центре стоит мужчина, слева от мужчины – его сын, а справа – его брат. Какое наименьшее количество различных людей может быть изображено на этих фотографиях, если известно, что все десять мужчин, стоящих в центре, различны?
Решение
Назовём десятерых мужчин, стоящих в центре фотографий, главными лицами. Разделим всех мужчин на фотографиях на уровни. К уровню 0 отнесём тех, кто не имеет отцов на фотографиях, к уровню k + 1 (k = 0, 1, 2,...) отнесём мужчин, имеющих на фотографиях отцов уровня k. Обозначим через rk число главных лиц, а через tk – число всех остальных мужчин уровня k. Число отцов мужчин уровня k + 1 не больше чем ½ rk+1 + tk+1, так как каждое главное лицо имеет брата. В то же время, отцов мужчин уровня k + 1 не меньше rk, так как каждое главное лицо имеет сына. Следовательно, rk ≤ ½ rk+1 + tk+1. Заметим также, что 1 ≤ ½ r0 + t0. Складывая все эти неравенства, получим ½ (r0 + r1 + ...) + (t0 + t1 + ...) ≥ (r0 + r1 + ...) + 1, откуда
(r0 + r1 + ...) + (t0 + t1 + ...) ≥ 3/2 (r0 + r1 + ...) + 1 = 3/2·10 + 1 = 16.
Итак, на фотографиях изображено не менее 16 мужчин. На рисунке представлены 16 мужчин с 10 главными лицами (пронумерованы от 1 до 10).
Ответ
16 человек.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь