Задача на раскраски( метод мат индукции)

[Akopyan Albert]

Недавно нашел следующую задачу:
Клетки шахматной доски 100×100 раскрашены в 4 цвета так,
что в любом квадрате 2 × 2 все клетки разного цвета. Докажите, что
угловые клетки раскрашены в разные цвета.
Хочу решить методом мат индукции, но не знаю как подобраться буду рад советам.

[gris]

С базой индукции всё нормально . Обратите внимание, что для квадрата $3\times3$ теорема не верна.

[Akopyan Albert]

я понимаю, что так происходит из-за четности стороны:как базу я взял квадрат 4 на 4 и т.к. в ЛЮБОМ квадрате 2x2 все клетки разного цвета, то пробовал рассматривать квадраты с шагом в 1 клетку. Но как-то не получается обобщить на общий случай. ( возможно базу надо брать как квадрат 2x2, и как-то хитрить с шагом индукции?)

[gris]

А чем база $2\times 2$ плоха? И шаг $2$.

[Akopyan Albert]

просто я не понимаю как доказать переход, на что опереться

[Null]

Попробуйте сделать утверждение про цвета углов для досок произвольного размера.

[ewert]

Akopyan Albert в сообщении #1225439 писал(а):

не понимаю как доказать переход, на что опереться

Допустим, есть квадрат

12
34

Как он может продолжаться вниз?

Третьей строчкой будет, естественно, 12 или 21. Четвёртой -- 34 или 43 и т.д.

Вот на это и опирайтесь. Представьте себе прямоугольную табличку с чётными длинами сторон, в углах которой по индуктивному предположению стоят эти же цифирки (прямоугольную, т.к. квадратная для доказательства менее выгодна). Добавьте к ней по одной колонке слева и справа. Докажите, исходя из чётности длин колонок, что:

1) в новых углах слева от единички и тройки могут стоять только двойки или четвёрки;
2) и что эти циферки не могут совпадать.

Справа от старых двойки и четвёрки -- разумеется, аналогично.