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

Понятно, что в каждой строчке стоит не более двух фишек. Рассмотрим все строчки. Если в строке две фишки, то назовем правую фишку правой, левую — левой. В строчках, где стоит одна фишка называем её правой. Тогда заметим, что в столбце, в котором стоит левая фишка, никаких других фишек стоять не может. Пусть — количество правых фишек, — количество левых фишек. Тогда столбцов у нас не меньше, чем При этом , откуда Но так как у нас может быть нечётно, а сумма фишек целое число, то оценка будет равна

Осталось привести пример на нужное количество фишек. Разобьем доску на квадратики причём в случае нечётного оставим непокрытыми самую верхнюю и самую правую полоски. Теперь выберем в каждом квадратике правый верхний уголок из трёх клеток. Для чётного всё сойдётся сразу, а для нечётного — отметим ещё угловую клетку на пересечении двух крайних полосок.