Задача М705‍‍‍

а) Мы докажем более общее утверждение: из покрытия любого конечного множества клеток карточками размером $1\times2$‍‍ клетки (с выполнением условий задачи) можно выбрать часть карточек так, чтобы каждая клетка множества оказалась покрытой ровно одной карточкой.

Рассмотрим произвольную клетку. Пусть её покрывают карточки $A_0$‍‍ и $A_1$‍.‍ Карточка $A_1$‍‍ покрывает ещё одну клетку, которая покрыта также карточкой $A_2$‍‍ ($A_2$‍‍ может, вообще говоря, совпасть с $A_0$‍).‍ Аналогично, карточка $A_2$‍‍ покрывает клетку, которую покрывает также карточка $A_3$‍,‍ и т. д. Если очередную карточку получить нельзя, мы обрываем эту цепочку.

Ясно, что это произойдёт в том случае, когда цепочка карточек замкнётся, т. е. когда очередная карточка окажется одной из уже выбранных. Ясно, что такой карточкой будет карточка $A_0$‍,‍ поскольку в противном случае какая-то клетка оказалась бы покрытой трижды. Нетрудно видеть, что в полученной цепочке число карточек чётно (убедитесь в этом!). Раскрасим все карточки цепочки в два цвета: с чётными номерами — в один цвет, с нечётными — в другой. Легко видеть, что наше множество клеток карточками каждого цвета оказывается покрытым в один слой.

С оставшимися непокрытыми клетками множества поступаем аналогично до тех пор, пока все клетки исходного множества не будут покрыты карточками разного цвета. Утверждение а) доказано.

б) Ответ: нет. Соответствующий пример изображён на рисунке 1: прямоугольный лист размером $3\times2$‍‍ клетки покрыт в два слоя четырьмя карточками размером $1\times2$‍,‍ одной карточкой $1\times3$‍‍ и одной — размером $1\times1$‍‍ клетки (на рисунке карточка $1\times1$‍‍ отмечена одной красной точкой; крайние точки карточек $1\times2$‍‍ и $1\times3$‍‍ соединены отрезками; попытка раскраски покрытия в два цвета не приводит к успеху).

в) Ответ: нет. Пример для прямоугольника $6\times7$‍‍ клеток, покрытого в два слоя 28 карточками $1\times3$‍‍ клетки, изображён на рисунке 2 (мы попытались раскрасить и его). На рисунке З изображён фрагмент рисунка 2 (раскрашенный иначе), на котором выделены пять «попарно зацепленных» карточек. Ни одну из этих карточек удалить нельзя. В самом деле, удалив первую карточку, мы должны оставить вторую; следовательно, должны удалить третью карточку, оставив четвёртую, удалить пятую, а потому — оставить первую карточку, что приводит нас к противоречию (она имеет противоположную окраску).