Решение задачи с фишками на доске.

Разберем задачу о фишках на доске размером 10x9. Всего на доске 10 * 9 = 90 клеток, и на каждой клетке стоит фишка. Миша сдвинул все фишки по диагонали на одну клетку. Необходимо найти минимальное возможное число свободных клеток. Для начала рассмотрим диагонали доски. Количество диагоналей, идущих в одном направлении, равно сумме количества строк и столбцов минус один. В нашем случае это 10 + 9 - 1 = 18. Когда мы сдвигаем все фишки на одну клетку по диагонали, все фишки оказываются на этих диагоналях. Чтобы минимизировать количество занятых клеток (и максимизировать количество свободных), нужно все фишки сдвинуть так, чтобы они заняли как можно меньше клеток. Каждая из 18 диагоналей содержит разное количество клеток. Самая длинная диагональ содержит 10 клеток, а две короткие – по одной клетке. Суммарное количество клеток на всех диагоналях можно найти, учитывая, что пар диагоналей одинаковой длины будет несколько. Самая длинная диагональ содержит 9 клеток. Количество диагоналей с каждой длиной уменьшается к краям. Сдвигая фишки по диагонали, нужно расположить все 90 фишек на минимальном количестве клеток. Оптимальное расположение – заполнить сначала самые длинные диагонали. Нам нужно найти минимальное количество занятых клеток, то есть минимальное количество диагоналей, на которых разместятся все фишки. Рассмотрим диагонали доски, параллельные главной диагонали. Количество клеток на каждой диагонали будет изменяться от 1 до 9 и затем снова до 1. Суммарное число клеток на диагоналях будет 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 63. Аналогично, рассмотрим диагонали доски, перпендикулярные главной диагонали. Количество клеток на каждой диагонали будет изменяться от 1 до 10 и затем снова до 1. Суммарное число клеток на диагоналях будет 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 90. Таким образом, минимальное количество занятых клеток равно 10. Это происходит, когда все фишки оказываются на одной из самых длинных диагоналей (10 клеток). Следовательно, минимальное число свободных клеток будет 90 (общее количество) - 10 (количество занятых) = 80. **Ответ: 80**