Разделы 
Дополнительно
Задача по математике - 3706
2019-06-16 
Король обошел шахматную доску $8 \times 8$, побывав на каждом поле ровно один раз и вернувшись последним ходом на исходное поле (король ходит по обычным правилам). Когда нарисовали его путь, соединив отрезками центры полей, которые он последовательно проходил, то получилась замкнутая ломаная без самопересечений.
а) Приведите пример, показывающий, что король мог сделать ровно 28 ходов по горизонтали и вертикали.
б) Докажите, что он не мог сделать меньше, чем 28 таких ходов.
в) Какую наибольшую и какую наименьшую длину может иметь путь короля, если длина стороны клетки равна 1?
Решение:
а) См. рис. б.
б) Выделим на доске каемку из 28 крайних полей. При обходе доски король побывал в каждом из них. Занумеруем эти поля в том порядке, в каком король их посещал, Весь путь короля разобьется на 28 участков: от поля 1 до поля 2; от поля 2 до поля 5; ...; от поля 28 до поля 1, Путь короля не имеет самопересечений. Поэтому клетки 1 и 2, 2 и $5, \cdots, 27$ и 28, 28 и 1 являются соседними клетками каемки. (Если, например, клетки 1 и 2 не соседние, то они разбивают граничную каемку на 2 части и путь короля из любой клетки одной из этих частей в какую-нибудь клетку другой пересечет участок 1-2, что противоречит условию задачи.) Но для того чтобы попасть на соседнюю клетку каемки, король на некотором шагу должен перейти с клетки одного цвета на клетку другого цвета, т. е. сделать ход либо по вертикали, либо по горизонтали. Отсюда следует, что в пути короля таких ходов не меньше 28.
в) Ясно, что длина пути короля не меньше 64 и такой короткий путь существует (рис.б). С другой стороны мы доказали, что путь короля содержит не меньше 28 отрезков длины 1. Следовательно, король мог сделать не больше 36 диагональных ходов, так что весь его путь не больше $28 + 36 \sqrt 2$ (Пример такого пути приведен на рис. а.)
Король обошел шахматную доску $8 \times 8$, побывав на каждом поле ровно один раз и вернувшись последним ходом на исходное поле (король ходит по обычным правилам). Когда нарисовали его путь, соединив отрезками центры полей, которые он последовательно проходил, то получилась замкнутая ломаная без самопересечений.
а) Приведите пример, показывающий, что король мог сделать ровно 28 ходов по горизонтали и вертикали.
б) Докажите, что он не мог сделать меньше, чем 28 таких ходов.
в) Какую наибольшую и какую наименьшую длину может иметь путь короля, если длина стороны клетки равна 1?
Решение:
а) См. рис. б.
б) Выделим на доске каемку из 28 крайних полей. При обходе доски король побывал в каждом из них. Занумеруем эти поля в том порядке, в каком король их посещал, Весь путь короля разобьется на 28 участков: от поля 1 до поля 2; от поля 2 до поля 5; ...; от поля 28 до поля 1, Путь короля не имеет самопересечений. Поэтому клетки 1 и 2, 2 и $5, \cdots, 27$ и 28, 28 и 1 являются соседними клетками каемки. (Если, например, клетки 1 и 2 не соседние, то они разбивают граничную каемку на 2 части и путь короля из любой клетки одной из этих частей в какую-нибудь клетку другой пересечет участок 1-2, что противоречит условию задачи.) Но для того чтобы попасть на соседнюю клетку каемки, король на некотором шагу должен перейти с клетки одного цвета на клетку другого цвета, т. е. сделать ход либо по вертикали, либо по горизонтали. Отсюда следует, что в пути короля таких ходов не меньше 28.
в) Ясно, что длина пути короля не меньше 64 и такой короткий путь существует (рис.б). С другой стороны мы доказали, что путь короля содержит не меньше 28 отрезков длины 1. Следовательно, король мог сделать не больше 36 диагональных ходов, так что весь его путь не больше $28 + 36 \sqrt 2$ (Пример такого пути приведен на рис. а.)
