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

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

Таким образом, каждый раз мы закрашиваем хотя бы 3 отрезка. А после выставления 37 фишек мы закрасим зелёным как минимум 111 отрезков.

Заметим, что каждый отрезок границ между клетками покрашен не более, чем единожды, а так как этих отрезков всего , то не покрашен всего лишь один отрезок.

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

Таким образом, у каждой стороны квадрата будет не больше трёх клеток с фишками. Поэтому будет закрашено зелёным не более 6 из 7 отрезков границ в этой линии, то есть непокрашенных отрезков хотя бы 4, что противоречит выводу из пункта 2. Значит, 37 фишек выставить нельзя.

36 фишек выставить можно (числами обозначено, в какой последовательности выставляются фишки):