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