Версия для печати
Убрать все задачи
На острове живут рыцари, лжецы и подпевалы; каждый знает про всех, кто из них кто. В ряд построили всех 2018 жителей острова и попросили каждого ответить "Да" или "Нет" на вопрос: "На острове рыцарей больше, чем лжецов?". Жители отвечали по очереди и так, что их слышали остальные. Рыцари отвечали правду, лжецы лгали. Каждый подпевала отвечал так же, как большинство ответивших до него, а если ответов "Да" и "Нет" было поровну, давал любой из этих ответов. Оказалось, что ответов "Да" было ровно 1009. Какое наибольшее число подпевал могло быть среди жителей острова?

Решение
Изначально на белой клетчатой плоскости конечное число клеток окрашено в чёрный цвет. На плоскости лежит бумажный клетчатый многоугольник $M$, в котором больше одной клетки. Его можно сдвигать, не поворачивая, в любом направлении на любое расстояние, но так, чтобы после сдвига он лежал "по клеткам". Если после очередного сдвига ровно одна клетка у $M$ лежит на белой клетке плоскости, эту белую клетку окрашивают в чёрный цвет и делают следующий сдвиг. Докажите, что существует такая белая клетка, которая никогда не будет окрашена в чёрный цвет, сколько бы раз мы ни сдвигали $M$ по описанным правилам.

Решение