Регион 2021

Пример. Покажем, что если то мы не сможем гарантированно найти дом Знайки. Разместим Знайку и лжеца Незнайку в дома с номерами и соответственно. Покажем, что может оказаться так, что по ответам жителей нельзя однозначно определить, в каком из этих двух домов живёт Знайка.

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

Оценка. Покажем, что если то мы сможем гарантированно найти дом Знайки. Пусть есть два подозрительных дома с номерами и Можно считать, что т.к. можно повернуть квадрат требуемым образом. Так как оба неравенства одновременно не могут быть равенствами, без ограничения общности будем считать, что Рассмотрим столбцы и (возможно, это один и тот же столбец).

Если или — нечётно, то в этих столбцах нет ни одного коротышки, расстояния от которого до двух выделенных домов одинаковы.

Если а чётно, то в столбце находится один коротышка, расстояния от которого до двух домов одинаковы.

Если а чётно, то в столбцах и находятся по одному коротышке, расстояния от которого до двух домов одинаковы.

Если же то в столбце места, от которых расстояния до и одинаковы, имеют вид где и таких мест ровно Аналогично, в столбце места, от которых расстояния до и одинаковы, имеют вид где и таких мест ровно

Заметим, что

Значит, какое-то из чисел не больше

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