Question

Решить клетчатая доска 4´4 покрыта тринадцатью доминошками 1´2, стороны которых идут по линиям сетки. доказать, что одну из доминошек можно убрать так, что оставшиеся будут по-прежнему покрывать всю доску.

Answer 1

Во-первых, заметим, что если какие-то 2 доминошки совпадают, то одну из них можно убрать так, чтобы условие выполнялось. Поэтому предположим, что они не совпадают. Кроме того, по условию, каждая из доминошек целиком находится на доске.

Предположим, что при удалении любой доминошки возникает хотя бы 1 непокрытая клетка. Тогда каждой из 13 доминошек можно поставить в соответствие клетку, которая оказывается непокрытой после удаления этой доминошки. Заметим, что 1 клетка не может соответствовать 2 доминошкам, иначе после удаления одной из доминошек она по-прежнему покрыта второй. Значит, не менее 13 клеток на доске покрыты ровно одной доминошкой. 

Напишем на каждой клетке число, равное числу доминошек, которые эту клетку покрывают. Тогда у нас будет не менее 13 единиц. Сумма всех чисел равна 13*2=26, а это значит, что сумма чисел на оставшихся 3 клетках равна 26-13=13. Так как каждое число - целое, хотя бы одно из них не менее 5.

Если клетку покрывает хотя бы 5 доминошек, то хотя бы 2 из них совпадает, а это противоречит нашему предположению. Значит, предположение неверно, и одну доминошку можно удалить так, чтобы остальные 12 по-прежнему покрывали всю доску.