Разбиение доски на части

Заметим, что на дне имеется плиток цвета Каждую из них нужно перекрасить дважды, притом за одно перекрашивание перекрашивается не более одной такой плитки. Значит, нужно хотя бы перекрашивания.

Построим пример. Давайте рассмотрим трёхклеточный уголок, у которого в концах стоят а в середине — Ясно, что за два перекрашивания его можно превратить в уголок с тремя тройками. Теперь рассмотрим квадрат состоящий из уголка, у которого в центре стоит а по краям единицы, и клетка с Его тоже можно перекрасить так, чтобы он состоял из троек. Давайте сначала перекрасим одну доминошку с и Потом перекрасим доминошку с этой же единицей и тройкой. Теперь дважды перекрасим доминошку с другой единицей и тройкой (которая после предыдущего перекрашивания стала единицей). Осталось разбить дно на такие фигуры. Давайте занумеруем клетки по вертикали и горизонтали числами от до Тогда можно взять уголки с центральными клетками в и квадратики с нижней левой клеткой в координатах