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

Решим задачу по шагам, чтобы понять, как Миша сдвинул фишки и какое минимальное количество клеток может остаться свободным. 1. **Начальное состояние доски**: У нас есть доска размером 10 × 9. Это означает, что всего есть 90 клеток, на каждой из которых изначально стоит по одной фишке. 2. **Действие Миши**: Миша сдвинул все фишки по диагонали на одну клетку в произвольном направлении. Диагональное смещение может быть как вниз-вправо, так и вверх-влево, и в каждом случае фишки занимают новые клетки. 3. **Исследуем перемещение фишек**: - Если фишки смещаются вниз-вправо, например с координатами (i, j) (где i - номер строки, j - номер столбца) на (i + 1, j + 1), некоторым фишкам может не хватить места на доске, если они выходят за границы. - Аналогично, если они смещаются вверх-влево, то фишки с координатами (i, j) сместятся на (i - 1, j - 1). 4. **Минимальное количество свободных клеток**: Чтобы минимизировать количество клеток, которые останутся свободными, нужно понять, когда фишки будут занимать одну и ту же клетку. Например, если несколько фишек смогут занять одну и ту же клетку после смещения, то на этой клетке не будет “свободно”. 5. **Подсчет**: - При сдвиге фишек вниз-вправо из 90 оригинальных фишек одна фишка из клеток к горизонту будет уходить "за границы" (например, фишки в последнему ряду не смогут сместиться вниз). - В случае, если фишки смещаются в разные направления, можно рассмотреть, что при таком сдвиге у нас есть ограниченный набор клеток, в которые фишки могут попасть, что также создаст ситуацию, когда некоторые клетки будут заполняться по нескольку раз. 6. **Достигнем минимального количества**: - Постараемся найти такие направления, чтобы, минимизируя расстояние для фишек, некоторые клетки остались не занятыми. - Максимально, когда клетки на краю доски оказываются сдвинутыми за пределы, в итоге можно выяснить, что минимум 10 клеток останется свободными. Итак, при перемещении всех фишек по диагонали, минимально возможное количество свободных клеток на доске размера 10 × 9 будет **10**.