Увидеть граф (переформулировки)

Оценка. Введем вспомогательный граф, вершинами которого будут клетки, а ребра проводятся между вершинами, у которых соответствующие им клетки граничат по стороне. Как только фишка ставится в очередную клетку, будем удалять все ребра, выходящие из соответствующей вершины. Заметим, что тем самым будут удаляться в точности ребра между вершиной, куда ставят фишку, и ее свободными соседями. Значит, после каждого выставления фишки должно удаляться не менее двух ребер.

Посчитаем общее количество ребер во введенном графе. Это количество перегородок между клетками; вертикальных перегородок и столько же горизонтальных, поэтому ребер в графе

Так как при выставлении одной фишки мы должны удалить хотя бы два ребра, то количество выставленных на доску фишек не превосходит то есть

Пример. Назовем диагональ доски, идущую из левого верхнего угла в правый нижний, главной. Будем выставлять фишки диагоналями, идя от диагонали, состоящей из одной клетки, к главной. На очередную диагональ фишки можно выставлять в любом порядке. Главную диагональ при этом не заполняем.