CPOЧНО!!! В центрах 64 клеток шахматной доски поставили по точке. Центры некоторых соседних по стороне клеток соединили отрезками. Получилась замкнутая ломаная без самопересечений, симметричная относительно одной из диагоналей доски. Какую наибольшую длину может иметь эта ломаная?
Ответы
Ответ:
52
Пошаговое объяснение:
Из-за симметрии ломаная проходит через клетки диагонали. Будем двигаться по ломаной от этой точки в направлении вправо-вверх. Из-за того, что ломаная не самопересекается, существует еще одна точка на диагонали, через которую она проходит. Из-за симметрии при движении по ломаной в направлении влево-вниз мы придем в эту же точку - а значит уже получим, что пройденные звенья образуют замкнутую ломаную => эта ломаная и есть искомая. Значит ломаная проходит ровно через 2 клетки на диагонали.
Соседние по стороне клетки доски имеют разный цвет => цвет вершин ломаной чередуется.
Рассмотрим часть ломаной, расположенной ниже диагонали. Т.к. диагональ состоит из черных клеток, концы этой части белые.
Число черных клеток ниже диагонали равно (32-8)/2=12
Тогда число белых вершин в этой части ломаной не превосходит 12+1=13
Тогда общее число вершин в этой части не превосходит 13+12=25. Тогда общее число вершин не превосходит 25*2+2=52 => длина ломаной не превосходит 52
С другой стороны, нетрудно привести пример такой ломаной
