ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109524
Темы:    [ Задачи с ограничениями ]
[ Рекуррентные соотношения (прочее) ]
[ Полуинварианты ]
Сложность: 5-
Классы: 8,9,10,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).

  Горизонтальные линии соединяют братьев, остальные линии ведут (сверху вниз) от отца к сыну. Фотографии:  (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).


Ответ

16 человек.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1993
Этап
Вариант 5
класс
Класс 9
задача
Номер 93.5.9.4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .