Раскраски

Предположим, что можно. Разберём два случая:

Случай Пусть Занумеруем столбцы полученного прямоугольника и закрасим все столбцы с номерами вида в красный цвет. Ясно, что любой прямоугольник покрывает ровно красных клеток, а любой прямоугольник покрывает либо либо красных клеток. После потери одного прямоугольника количество красных клеток, покрываемых этими прямоугольниками, уменьшилось на Следовательно, эти клеток должны быть покрыты прямоугольниками Как мы выяснили ранее, такие прямоугольники покрывают либо либо красных клеток, то есть кратно Но мы предположили, что а значит (из равенства ). Таким образом, не может делиться на Противоречие.

Случай Если то Занумеруем строки и покрасим строки с номерами в красный цвет. Далее по аналогичным рассуждениям получим, что кратно Снова пришли к противоречию.