Question

CPOЧНО!!! В центрах 64 клеток шахматной доски поставили по точке. Центры некоторых соседних по стороне клеток соединили отрезками. Получилась замкнутая ломаная без самопересечений, симметричная относительно одной из диагоналей доски. Какую наибольшую длину может иметь эта ломаная?

Answer 1

Ответ:

52

Пошаговое объяснение:

Из-за симметрии ломаная проходит через клетки диагонали. Будем двигаться по ломаной от этой точки в направлении вправо-вверх. Из-за того, что ломаная не самопересекается, существует еще одна точка на диагонали, через которую она проходит. Из-за симметрии при движении по ломаной в направлении влево-вниз мы придем в эту же точку - а значит уже получим, что пройденные звенья образуют замкнутую ломаную => эта ломаная и есть искомая. Значит ломаная проходит ровно через 2 клетки на диагонали.

Соседние по стороне клетки доски имеют разный цвет => цвет вершин ломаной чередуется.

Рассмотрим часть ломаной, расположенной ниже диагонали. Т.к. диагональ состоит из черных клеток, концы этой части белые.

Число черных клеток ниже диагонали равно (32-8)/2=12

Тогда число белых вершин в этой части ломаной не превосходит 12+1=13

Тогда общее число вершин в этой части не превосходит 13+12=25. Тогда общее число вершин не превосходит 25*2+2=52 => длина ломаной не превосходит 52

С другой стороны, нетрудно привести пример такой ломаной

Answer 2

Для решения этой задачи давайте представим, что каждая клетка шахматной доски - это вершина графа, а отрезки между соседними клетками - это рёбра этого графа. Замкнутая ломаная без самопересечений, симметричная относительно одной из диагоналей доски, будет иметь следующий вид:

Copy code
x x x x x
x x x x x
x x x x x
x x x x x
x x x x x

Где "x" представляют собой вершины, которые соединены рёбрами. Мы хотим найти наибольшую длину этой ломаной.

Давайте рассмотрим несколько случаев:

1. Диагональ с чётным количеством клеток: Например, диагональ соединяет вершины (1,1) и (8,8) (первый и последний ряд доски). В этом случае, мы можем соединить вершины в следующем порядке: (1,1) -> (8,1) -> (8,8) -> (1,8) -> (1,1), и получится замкнутая ломаная без самопересечений. Длина ломаной в этом случае будет равна периметру квадрата, ограничивающего диагональ, что равно 32 клеткам.

2. Диагональ с нечётным количеством клеток: Например, диагональ соединяет вершины (1,1) и (7,7). В этом случае, мы можем соединить вершины в следующем порядке: (1,1) -> (8,1) -> (8,8) -> (1,8) -> (1,1), и опять получится замкнутая ломаная без самопересечений. Длина ломаной в этом случае также будет равна периметру квадрата, ограничивающего диагональ, что равно 28 клеткам.

Таким образом, наибольшая длина замкнутой ломаной без самопересечений, симметричной относительно одной из диагоналей доски, равна 32 клеткам.