Задача 8.
У Коли есть 100 монет и доска 𝑚 × 𝑛, где 𝑚 ≥ 𝑛 и 𝑚 > 1. Он разложил все монеты в клетки доски так, что в любых двух соседних по стороне клетках суммарно оказалось ровно 10 монет (в каких-то клетках могло оказаться несколько монет, а какие-то клетки могли оказаться пустыми). Какие значения может принимать 𝑚? Укажите все возможные варианты.
Ответ на Задачу 8.
Ответ: 5, 7, 10, 19, 20, 21.
Решение:
Предположим, что какое-то из чисел 𝑚 и 𝑛 чётно. Тогда всю доску можно разбить на прямоугольники 1 × 2. Из условия следует, что в каждом таком прямоугольнике должно оказаться 10 монет. Значит, таких прямоугольников должно быть 100 ∶ 10 = 10, а всего клеток в доске должно быть 10 ⋅ 2 = 20. В этом случае есть 3 подходящих варианта для размеров доски: 20 × 1, 10 × 2 и 5 × 4, поэтому 𝑚 может быть равно 20, 10 или 5.
Теперь рассмотрим случай, когда оба числа 𝑚 и 𝑛 нечётны. В этом случае можно разбить на прямоугольники 1 × 2 всю доску, кроме одной угловой клетки. Поскольку в каждом прямоугольнике должно быть 10 монет, а всего монет 100, то количество монет в оставшейся клетке должно делиться на 10. При этом это количество не превышает 10, так как иначе в паре этой клетки с любой из соседних получится в сумме больше 10 монет. Остаются два случая: либо в прямоугольниках разбиения суммарно находится 90 монет (т.е. прямоугольников 1 × 2 ровно 9), а в оставшейся клетке 10, либо в прямоугольниках находится суммарно 100 монет (т.е. прямоугольников 1 × 2 ровно 10), а в оставшейся клетке 0.
В первом случае в доске 19 клеток, и это возможно только в случае доски 19 × 1, поэтому в этом случае 𝑚 = 19.
Во втором случае в доске 21 клетка, и это бывает в случаях 21 × 1 и 7 × 3. Поэтому подходящие варианты для 𝑚 — это 21 и 7.
Также отметим, что все вышеописанные варианты для 𝑚 реализуемы. Для этого соответствующие доски покрасим в шахматную раскраску. Для случаев 21 × 1 и 7 × 3 рассмотрим шахматную раскраску, где углы доски белые, а для случая 19 × 1 рассмотрим раскраску, где углы чёрные. Для случаев 20 × 1, 10 × 2 и 5 × 4 можно рассмотреть любую из двух возможных раскрасок. Во всех этих шахматных раскрасках ровно 10 чёрных клеток. В каждую из них положим по 10 монет, а в каждую из белых клеток положим по 0 монет. Ясно, что все условия задачи выполняются.