Подсчеты в клетчатых задачах

Предположим противное. Ясно, что в таблице есть пустые столбцы. Заметим, что крайним пустой столбец быть не может. Действительно, если, скажем, правый столбец пуст, то из самого правого непустого столбца можно сдвинуть фишку вправо. Аналогично доказывается, что не может быть двух пустых столбцов подряд. Итак, слева от каждого пустого столбца есть фишка. Её нельзя сдвинуть вправо, значит, в той же строке справа через одну от неё стоит фишка. Таким образом, каждая “левая” фишка находится в строке, где есть другие фишки. Пусть всего пустых столбцов Тогда соответствующих “левых” фишек не меньше Следовательно, все фишки занимают не более строк, и пустых строк не меньше то есть больше чем пустых столбцов. Аналогично можно доказать, что пустых столбцов больше, чем пустых строк. Противоречие.