Введение в криптографию
[an error occurred while processing this directive]

...К задачам восьмой олимпиады - часть 5


Расстояние между центром клетки и центром клетки равно . Заметим, что и . Обозначим , , . Тогда  - число натуральное, если . Отсюда получаем, что

В общем случае, если , то

Ясно, что и должны быть одинаковой четности. По условию, , поэтому искомыми решениями будут только пары

Клетку назовем существенной для клетки , если выполнено условие . Ясно, что цвет данной клетки менялся лишь тогда, когда Криптоша находился в какой-либо существенной для нее клетке. А так как в каждой клетке Криптоша побывал ровно 1999 раз (нечетное число), то цвет данной клетки изменился, если общее число существенных для нее клеток нечетно.

Для определения четности числа всех существенных клеток для данной клетки воспользуемся тем, что у симметричных клеток относительно той или иной диагонали квадрата или относительно центрального вертикального или центрального горизонтального рядов эти числа будут одинаковы. Это, в частности, означает, что достаточно определить указанную четность только для клеток , где , (этих клеток 15, занумеруем их, как показано на рис. ).

Рис. 23. Для клетки 1 жирными линиями выделена зона асимметрии. Серым цветом отмечены клетки верхнего левого угла , меняющие свой цвет

Кроме того, отметим, что у каждой из клеток на диагоналях квадрата, а также у каждой из клеток центрального вертикального и горизонтального рядов обязательно будет четное число существенных для нее клеток.

Зоной асимметрии для той или иной клетки мы назовем множество тех клеток, которые в пределах исходного квадрата не имеют клеток, симметричных относительно вертикального, горизонтального и правого диагональных рядов, содержащих данную клетку. Ясно, что для данной клетки число существенных клеток, не лежащих в ее зоне асимметрии, четно.

На рис.  показана зона асимметрии для клетки 1, а также все клетки верхнего левого угла , меняющие свой цвет.

Ответ на рис. .

Рис. 24.

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




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]