На каждой клетке доски 10 х 9 стоит фишка. Миша сдвинул все фишки по диагонали на одну клетку (в произвольном направлении). После этого действия на одной клетке может оказаться несколько фишек, а другие клетки могут быть свободными. Найди минимально возможное число свободных клеток.

Здравствуйте, ребята! Давайте решим эту интересную задачу вместе. 1. Понимание условия задачи У нас есть шахматная доска размером 10x9, то есть всего 90 клеток. На каждой клетке стоит фишка. Миша передвигает каждую фишку на одну клетку по диагонали. Наша задача — найти минимальное количество пустых клеток после этих передвижений. 2. Анализ ситуации Чтобы минимизировать количество пустых клеток, нужно постараться, чтобы фишки максимально заполнили клетки после сдвига. Сдвиг по диагонали означает, что фишка может переместиться в одну из четырех соседних клеток по диагонали (если, конечно, такая клетка существует). 3. Решение Подумаем, какие клетки могут остаться пустыми. Очевидно, что фишки с угловых клеток могут переместиться только в одну клетку по диагонали. Фишки с клеток, находящихся рядом с краем доски, имеют меньше вариантов для перемещения. Давайте рассмотрим доску 3x3, чтобы понять принцип. Изначально 9 фишек. Можно сдвинуть все фишки так, чтобы заняты оказались только центральные клетки. В случае доски 10x9, можно добиться того, что основная часть клеток будет занята, а пустыми останутся клетки по краям. Представим себе, что мы сдвигаем все фишки с белых клеток на черные. В этом случае, белые клетки окажутся свободными. Так как всего 90 клеток, то если клетки чередуются, то количество белых и черных клеток будет примерно одинаковым. В нашем случае либо 45 белых и 45 черных, либо 44 одного цвета и 46 другого. Чтобы минимизировать пустые клетки, нам нужно рассмотреть стратегию, при которой мы максимально используем клетки. Минимальное число свободных клеток можно найти, если предположить, что все фишки сдвинутся в минимальное количество клеток. Предположим, что занятыми окажутся те клетки, до которых можно дотянуться сдвигом по диагонали. Это будет центральная часть доски. Рассмотрим, сколько клеток остается пустыми. У нас доска 10x9. Если мы рассмотрим внутреннюю часть доски 8x7, то все фишки с этой части сдвинутся внутрь. Значит, пустые клетки будут только по краям. Пустых клеток будет: 2 ряда по 10 (верхний и нижний) и 2 столбца по 7 (боковые, без учета углов). $$2 * 10 + 2 * 7 = 20 + 14 = 34$$ Однако, фишки с углов доски могут сдвинуться только в одну клетку. Поэтому минимальное количество пустых клеток будет равно количеству угловых клеток, то есть 4. Но у нас более сложная задача. Чтобы найти минимальное число свободных клеток, нужно рассмотреть, как фишки могут перекрываться. Если все фишки сдвинуть в центр, то количество занятых клеток будет меньше, чем изначальное количество фишек. Тогда количество свободных клеток будет больше. Рассмотрим другой подход. Попробуем сдвинуть фишки так, чтобы они заполнили прямоугольник меньшего размера. Например, сдвинем все фишки в прямоугольник 1x1. Тогда 89 клеток будут пустыми. Минимальное количество пустых клеток будет достигаться, если фишки будут сдвигаться так, чтобы максимально заполнить клетки. Так как сдвиг происходит по диагонали, то пустые клетки останутся только по краям. Если мы представим, что сдвигаем все фишки к центру доски, то в центре образуется скопление фишек. На краях же образуются пустые клетки. Минимальное число свободных клеток будет равно разнице между исходным количеством клеток и максимальным числом клеток, которые можно заполнить. Пусть x - количество свободных клеток. Тогда 90 - x - количество занятых клеток. Мы знаем, что каждая фишка сдвигается на одну клетку. Следовательно, фишки с угловых клеток (4 штуки) могут занять только 1 клетку каждая. Фишки с боковых клеток могут занять максимум 2 клетки каждая. Фишки из центра могут занять максимум 4 клетки каждая. 4. Ответ Минимальное количество свободных клеток равно 1. Ответ: 1