ВсОШ 2023, 7 класс, задача 5
( баллов) В лесу живут эльфы и гномы. Однажды жителей этого леса встали в ряд лицом в одну сторону, в этот момент некоторые из них могли быть в колпаках. (Эльфов могло быть от до включительно, жителей в колпаках тоже могло быть от до включительно.)
Каждый из жителей сказал одну из следующих фраз:
- «Мой сосед справа — эльф».
- «Мой сосед справа — в колпаке».
Известно, что эльфы без колпаков всегда говорят правду, а эльфы в колпаках всегда лгут. У гномов всё наоборот: гномы без колпаков всегда лгут, а гномы в колпаках всегда говорят правду.
(а) ( балла) Какое наибольшее количество эльфов без колпаков могло быть в ряду?
(б) ( балла) Какое наибольшее количество эльфов в колпаках могло быть в ряду?
Ответ
Ответ: (а) ; (б) .
Решение. (а) Заметим, что самый правый житель не может говорить правду, ведь правее него никого нет. Это значит, что он не может быть эльфом без колпака, поэтому всего эльфов без колпаков не более .
Теперь приведём пример ситуации, когда эльфов без колпаков ровно . Пусть самый правый житель — это эльф в колпаке, а остальные — это эльфы без колпака. Пусть все говорят фразу «Мой сосед справа — эльф». Тогда эльфы без колпаков говорят правду, а эльф в колпаке лжёт.
(б) Заметим, что среди любых двух соседей не может быть двух эльфов в колпаках. Действительно, если это так, то левый из них точно сказал бы правду. Но такого не может быть, ведь эльфы в колпаках всегда лгут.
Разобьём всех жителей на пар соседей. В каждой из этих пар не больше одного эльфа в колпаке, поэтому всего эльфов в колпаках не больше .
Теперь приведём пример ситуации, когда эльфов в колпаках ровно . Пусть чередуются гномы в колпаках и эльфы в колпаках, причём самый левый житель — гном. Пусть все говорят фразу «Мой сосед справа — эльф». Тогда гномы в колпаках говорят правду, а эльфы в колпаках лгут.
Верное решение пункта (а).
Верное решение пункта (б).