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