Обозначим через ответ в задаче; положим Докажем сначала, что

После отмечания исходных клеток можно отметить хотя бы одну клетку ; это значит, что либо в столбце, либо в строке этой клетки уже отмечено других клеток - пусть для определённости в строке

Мысленно отметим все клетки строки Ясно, что любую клетку по-прежнему можно отметить. Удалим из клетчатой плоскости строку и сдвинем вместе две получившиеся полуплоскости так, чтобы снова получилась клетчатая плоскость. Теперь мы можем отметить любую клетку этой новой плоскости, отмечая на каждом шагу клетку, в кресте которой уже есть не менее отмеченных клеток (поскольку из этого креста удалена одна клетка строки ). Следовательно, изначально на этой плоскости должно было быть отмечено не менее клеток. Значит, на исходной плоскости сначала должно быть хотя бы отмеченных клеток не из ; отсюда и следует

Поскольку из доказанного неравенства (*) следует, что

Осталось показать, как отметить клеток так, чтобы затем можно было отметить любую другую клетку плоскости. Покажем по индукции, что подходит пример, показанный на рисунке, состоящий из двух «лесенок» высот и ; нетрудно понять, что в нём как раз клеток. При утверждение очевидно: при одной отмеченной клетке можно отметить любую клетку в её кресте, а затем и любую клетку вообще.

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