Раскраски

Наверняка вы уже встречались с задачами на разрезания. В некоторых из них нужно было догадаться, как строить примеры разрезания шахматных досок и других фигур. Но что делать, если разрезать нельзя? Есть ли какой-то способ доказательства этого факта? На самом деле такой метод есть — это метод раскраски. Давайте посмотрим на примере, как его применять.

1.  Из шахматной доски вырезали две противоположные угловые клетки. Можно ли оставшуюся доску разрезать на доминошки, то есть прямоугольнички

Ответ. Нет, нельзя

Решение. Раскрасим доску в шахматном порядке.

Заметим, что обе вырезанные клетки одного цвета — белого. Тогда в оставшейся доске остается 32 черных клетки и 30 белых. Но как бы мы не положили доминошку на доску, она будет занимать одну белую и одну черную клетки, значит, больше 30 доминошек из оставшейся доски мы не вырежем. А так как клеток осталось 62, то доминошек при разрезании должно получиться 31, чего не может быть.

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

2.  Можно ли выложить шахматную доску 32 доминошками так, чтобы 17 из них были расположены горизонтально, а 15 — вертикально?

Ответ. Нет, нельзя

Решение. Сначала отметим, что шахматная раскраска здесь вряд ли поможет: она не различает вертикальные и горизонтальные доминошки, ведь и в тех, и в других одна белая и одна черная клетки. Поэтому поищем раскраску, при которой вертикальные и горизонтальные доминошки все же различаются.

Раскрасим шахматную доску вертикальным «матрасиком» в два цвета:

При такой раскраске любая горизонтальная доминошка содержит по одной белой и черной клетке, а вертикальная — либо 2 белых и 0 черных, либо наоборот, 0 белых и 2 черных. Поэтому 17 горизонтальных доминошек покроют 17 черных клеток, а 15 вертикальных — еще некоторое четное количество черных клеток. Значит, всего будет покрыто нечетное количество черных клеток. А при данной раскраске на доске 32 черные клетки, противоречие.

Существует множество других раскрасок — полосками в несколько цветов, диагональные и другие. В первой задаче можно было догадаться, какая нужна раскраска, попробовав построить пример — у вас будут оставаться две клеточки одного цвета. Во второй же сразу было ясно, что такая раскраска уже не подойдет. Ваша задача —догадаться, где какая раскраска сможет помочь. Возможно, для этого нужно будет попробовать построить примеры. Тогда, если разрезать можно, вы найдете это разрезание, а если нет — догадаетесь в чем возникает противоречие.