диагональная задачка

[avva]

Очень милая задачка для тех, кому нравится рисовать в тетрадках в клеточку. Из московского математического фестиваля несколько лет назад (задача для 7 класса).



(может показаться, что максимум 20, но на самом деле можно и больше. Обратите внимание, что пересекать путь нельзя, и возвращаться в ту же вершину, кроме как в конце пути, нельзя).

(по ссылке из блога Тани Ховановой)

Comments

[avva.livejournal.com]

Какие-то вы все крутые, у меня 20 не сразу получилось.

[(Anonymous)]

Сам не понимаю, с первого раза сделал, хотя 8х8 конём так и не смог в своё время обойти.
Ту ведь тоже конь!

[avva.livejournal.com]

Да, но нельзя пересекать, в отличие от коня. Это, плюс то, что надо вернуться в исходную точку, сильно усложняет.

[(Anonymous)]

Вот хорошая задача: доказать, что конь за чётное количество шагов не может попасть в соседнюю клетку.
Доказывается буквально одним словом.

Но, мой одноклассник, меня просто "убил" когда-то, выписав систему уравнений, которую якобы необходимо решить для доказательства.

[utnapishti.livejournal.com]

Единственное буквально-одно-слово, которое мне приходит в голову, это "чётность", но оно есть и в условии, так что непонятно, можно ли его считать решением.
Если бы я хотел выпендриться, я бы написал 1+2 = 1 (mod 2); 1+1 = 0 (mod 2). Как бы это ещё компактифицировать? Например, 0 \neq 1 (mod 2) :)

[avva.livejournal.com]

Я когда-то очень много лет назад на мат. олимпиаде решал задачу такого типа. У квадратной доски размером 100x100 вырезали два противоположных угла-квадратика, доказать, что ее нельзя покрыть целиком непересекающимися полосками 1x4 квадратика.

[kyty3ob.livejournal.com]

Ага, помню такую. Задачка на инвариант. Есть в сборнике Спивака.

[utnapishti.livejournal.com]

Ээээ что-то тут не так. 100х100-2 вовсе не делится на 4! Мб из каждого угла квадратик вырезают?

[rsokolov.livejournal.com]

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