Минимум разных героев на фото: олимпиадная задача по комбинаторике 8-11 класс

  Назовём десятерых мужчин, стоящих в центре фотографий, главными лицами. Разделим всех мужчин на фотографиях на уровни. К уровню 0 отнесём тех, кто не имеет отцов на фотографиях, к уровню  k + 1  (k = 0, 1, 2,...)  отнесём мужчин, имеющих на фотографиях отцов уровня k. Обозначим через r_k число главных лиц, а через t_k – число всех остальных мужчин уровня k. Число отцов мужчин уровня  k + 1  не больше чем  ½ r_k+1 + t_k+1,  так как каждое главное лицо имеет брата. В то же время, отцов мужчин уровня  k + 1  не меньше r_k, так как каждое главное лицо имеет сына. Следовательно,  r_k ≤ ½ r_k+1 + t_k+1.  Заметим также, что  1 ≤ ½ r₀ + t₀.  Складывая все эти неравенства, получим  ½ (r₀ + r₁ + ...) + (t₀ + t₁ + ...) ≥ (r₀ + r₁ + ...) + 1,  откуда

(r₀ + r₁ + ...) + (t₀ + t₁ + ...) ≥ ³/₂ (r₀ + r₁ + ...) + 1 = ³/₂·10 + 1 = 16.

  Итак, на фотографиях изображено не менее 16 мужчин. На рисунке представлены 16 мужчин с 10 главными лицами (пронумерованы от 1 до 10).

  Горизонтальные линии соединяют братьев, остальные линии ведут (сверху вниз) от отца к сыну. Фотографии:  (3, 1, 2),  (5, 2, 1),  (7, 3, 4), (9, 4, 3), (11, 5, 6),  (12, 6, 5),  (13, 7, 8),  (14, 8, 7),  (15, 9, 10)  и  (16, 10, 9).