ответ:Объяснение:Предположим, что клетки квадрата n × n удалось раскрасить таким образом, что для любой клетки с какой-то стороны от неё нет клетки одного с ней цвета. Рассмотрим тогда все клетки одного цвета и в каждой из них нарисуем стрелочку в том из четырёх направлений, в котором клетки того же цвета нет. Тогда на каждую клетку «каёмки» нашего квадрата будет указывать не более одной стрелки. Так как клеток каёмки всего 4n – 4, то и клеток каждого цвета не более 4n – 4. С другой стороны, каждая из n² клеток нашего квадрата раскрашена в один из четырёх цветов, то есть n² ≤ 4(4n – 4). Для решения задачи теперь достаточно заметить, что последнее неравенство неверно при n = 50. Несложно убедиться, что оно неверно при всех n ≥ 15, и, следовательно, утверждение задачи верно уже в квадрате 15 × 15 — а заодно и в любом большем квадрате.
1 шаг. Проверим справедливость утверждения при n=1:
- верно
2 шаг. Предположим, что при n=k следующее утверждение верно:
3 шаг. Докажем, что при n=k+1 следующее утверждение также будет верно:
Для доказательства выполним преобразования:
Рассмотрим получавшуюся сумму. Первое слагаемое делится на 9 по предположению, сделанному на предыдущем шаге. Во втором слагаемом первый множитель делится на 3. Значит, остается доказать, что второй множитель также делится на 3. Докажем это, используя арифметику остатков:
Мы получили, что выражение дает при делении на 3 такой остаток, как и число 3. Но число 3 кратно 3, значит и выражение кратно 3.
Возвращаясь к выражению , повторим, что первое слагаемое делится на 9, второе слагаемое представляет собой произведение двух множителей, каждое из которых делится на 3, то есть само слагаемое делится на 9. Сумма двух выражений, делящихся на 9, также делится на 9, или другими словами, кратна 9. Доказано.
1 шаг. Проверим справедливость утверждения при n=1:
2 шаг. Предположим, что при n=k следующее утверждение верно:
3 шаг. Докажем, что при n=k+1 следующее утверждение также будет верно:
Для доказательства выполним преобразования:
Рассмотрим получавшуюся сумму. Первое слагаемое
делится на 9 по предположению, сделанному на предыдущем шаге. Во втором слагаемом 
первый множитель делится на 3. Значит, остается доказать, что второй множитель также делится на 3. Докажем это, используя арифметику остатков:
Мы получили, что выражение
дает при делении на 3 такой остаток, как и число 3. Но число 3 кратно 3, значит и выражение 
кратно 3.
Возвращаясь к выражению
, повторим, что первое слагаемое делится на 9, второе слагаемое представляет собой произведение двух множителей, каждое из которых делится на 3, то есть само слагаемое делится на 9. Сумма двух выражений, делящихся на 9, также делится на 9, или другими словами, кратна 9. Доказано.