Одним из интересных способов решения задач является метод использующий раскраски. Задачи могут быть явно на раскраски, например сказано «Раскрасим плоскость в 3 цвета» и быть не явно на раскраски. Часто задачи на доске (шахматной или любой другой) решаются с помощью раскраски. Наиболее популярная конечно шахматная раскраска, но вообще говоря она может быть любой.
Рассмотрим задачу для которой не очевидно, что она должна решаться раскраской.
Условие:
Есть два типа доминошек 2x1 и 1x2 (поворачивать доминошки не разрешается). Причем вертикальных 17, а горизонтальных 15. Можно ли этими доминошками замостить доску 8x8.
Идея:
Раскрасить таким образом, чтобы решение стало очевидным.
Решение:
Раскрасим доску в два цвета, полосками. Первую в белый, вторую в черный, третью в белый и т. д.
Заметим, что горизонтальная доминошка может быть либо полностью белой, либо полностью черной, а вертикальная доминошка всегда двуцветная. Таким образом расставив все вертикальные доминошки у нас останется 17 белых клеток и 17 черных. Но, чтобы замостить горизонтальными нужно, чтобы число белых клеток было четным и число черных клеток было четным.
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!
