Всесиб 2021, 11 класс, задача 5
( баллов) В некоторых клетках прямоугольной доски размера на сидят по одной черепашке. Каждую минуту каждая из них одновременно переползает в одну из клеток доски, соседнюю с той, в которой они находятся, по стороне. При этом, каждый следующий ход делается ими в направлении, перпендикулярном предыдущему: если предыдущий ход был горизонтальным - налево или направо, то следующий будет вертикальным - вверх или вниз, и наоборот. Какое максимальное количество черепашек может перемещаться по доске неограниченное время так, что в каждый момент в каждой клетке будет находиться не более одной черепашки?
Ответ
Ответ. .
Решение. Примеры неограниченного движения по доске черепашек.
Пример 1. Рассадим пресмыкающихся в клетки прямоугольника, состоящего из клеток, стоящих на пересечении нижних горизонталей и левых вертикалей. Ходить они будут одинаково: сначала все направо, потом все вверх, потом все налево и затем все вниз. После ходов ситуация совпадёт с первоначальной, поэтому движение может продолжаться разрешённым образом сколь угодно долго.
Пример 2. Исходная рассадка черепашек как в примере , но движение организовано так: разбиваем их на квадратики на клетки, в каждом из которых они одновременно двигаются по часовой стрелке.
Докажем, что большее, чем , количество черепашек правильно рассадить на доске на нельзя. Предположим противное, что черепашки размещены на доске некоторым образом так, что у них есть возможность неограниченно долго перемещаться по доске указанным в условии способом и не оказываться на одной клетке в количестве двух и более одновременно.
Раскрасим клетки доски в шахматном порядке так, что левая нижняя клетка, как обычно, чёрная. Получится чёрных и белых клетки. Среди чёрных клеток нечётными назовём клетки, номера вертикали и горизонтали которых нечётны, и чётными - номера вертикали и горизонтали которых чётны. Заметим, что для белых клеток один из этих номеров чётен, а другой - нечётен. Нечётных чёрных клеток будет , а чётных чёрных клеток . Ясно, что в каждый момент количество черепашек на чётных чёрных клетках не должно превосходить .
Заметим, что при выполнении двух последовательных ходов меняется чётность обеих координат каждой черепашки, поэтому после двух ходов все черепашки с нечётных чёрных клеток переместятся на чётные чёрные клетки и наоборот, а черепашки с белых клеток переместятся снова на белые клетки. Следовательно, в любой момент времени количество черепашек на всех чёрных клетках не превосходит .
Наконец, при выполнении одного хода черепашки с чёрных клеток переходят на белые и наоборот, поэтому общее количество черепашек на всей доске не может превосходить .
Замечание. На самом деле, мы доказали, что, если черепашек на доске больше, чем , то они смогут сделать не более двух ходов, не оказываясь на одной клетке в количестве двух и более одновременно.