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

Занумеруем столбцы этой фигуры слева направо числами от до (пусть — количество столбцов). Пусть -й столбец содержит клеток, тогда

Нетрудно понять, что если выделить в -м столбце клетки через одну, то мы получим как минимум клеток, которые попарно не имеют общих вершин. Выделим таким образом клетки в столбцах с нечётными индексами и получим хотя бы клеток, попарно не имеющих общих вершин, потому что мы взяли столбцы через один. Если проделать то же самое с чётными столбцами, мы получим клеток. Заметим, что сумма чисел и равна а значит, по принципу Дирихле какое-то из них хотя бы получили требуемое.