Задача 65603

Темы:    [ Последовательности (прочее) ] [ Инварианты ] [ Примеры и контрпримеры. Конструкции ] [ Перебор случаев ]

Сложность: 4- Классы: 6,7,8

Условие

Авторы: Шаповалов А.В., Ященко И.В.

На конкурсе "А ну-ка, чудища!" стоят в ряд 15 драконов. У соседей число голов отличается на 1. Если у дракона больше голов, чем у обоих его соседей, его считают хитрым, если меньше, чем у обоих соседей, – сильным, остальных (в том числе стоящих с краю) считают обычными. В ряду есть ровно четыре хитрых дракона – с 4, 6, 7 и 7 головами и ровно три сильных – с 3, 3 и 6 головами. У первого и последнего драконов голов поровну.
  а) Приведите пример того, как такое могло быть.
  б) Докажите, что число голов у первого дракона во всех примерах одно и то же.

Решение

  Удобно изображать ряд драконов в виде графика: вместо каждого дракона нарисуем точку на высоте, соответствующей числу голов дракона, и соединим эти точки.

  а) См. рисунок.

  б) Заметим, во-первых, что где-то в промежутке между каждыми двумя хитрыми драконами стоит сильный. Действительно, если мы будем идти вдоль ряда драконов, то после того, как мы миновали хитрого дракона, количество голов начинает уменьшаться. В некоторый момент оно должно начать увеличиваться – это и есть позиция, где стоит сильный дракон. Аналогично, далее увеличение когда-то закончится на хитром драконе.

  Первый способ. Посмотрим в каком порядке могут стоять сильные и хитрые драконы. Сильный дракон с шестью головами может стоять только между двумя хитрыми драконами с семью головами. Возникают три случая: два оставшихся сильных дракона стоят либо по одну сторону от этой троицы в одном из двух порядков, либо по разные стороны.

  В первом случае 14 драконов уже определены однозначно, и единственный способ добиться того, чтобы у первого и последнего дракона голов было поровну, – добавить справа с краю еще одного дракона с пятью головами.
  Второй и третий вариант невозможны, так как для них требуется более 15 драконов (даже без учёта условия одинакового количества голов у крайних драконов).

  Второй способ (набросок). Можно обойтись и без перебора. Выберем участок графика между каким-нибудь сильным драконом и ближайшими к нему хитрыми драконами и "распрямим" его, заменив "впадину" на "горку" (см. рисунок).

  Количество голов у драконов при этом изменится, и вместо двух хитрых драконов и одного сильного на этом участке теперь будет только один хитрый дракон. Заметим, что количество голов у нового хитрого дракона будет равно сумме количеств голов у исходных двух хитрых минус количество голов у бывшего сильного. Это означает, что при такой процедуре величина "сумма количеств голов всех хитрых минус сумма количеств голов всех сильных" не меняется.
  Заметим также, что количество голов у крайних драконов в ряду от такой операции заведомо не поменялось. Повторим теперь эту операцию, пока все сильные драконы не исчезнут. У нас останется один хитрый дракон, который по соображениям симметрии будет ровно посередине ряда. Подсчитаем, сколько у него будет голов. Мы знаем, что изначально сумма количеств голов хитрых драконов минус сумма количеств голов сильных драконов равна
4 + 6 + 7 + 7 – 3 – 3 – 6 = 12.  Но теперь эта сумма равна просто количеству голов единственного хитрого дракона!
  Зная, что у него 12 голов, мы далее без труда восстанавливаем, что у крайних драконов (отстоящих от него на семь позиций в ряду) по пять голов.

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

олимпиада
Название	Математический праздник
год
Год	2016
класс
Класс	7
задача
Номер	6