Будем до­ка­зы­вать чуть более общее утвер­жде­ние. Пусть в бес­ко­неч­ном клет­ча­том квад­ран­те за­кра­ше­но кле­ток. Тогда у за­кра­шен­ньх кле­ток будет как ми­ни­мум со­се­дей. Ис­поль­зу­ем ин­дук­цию по n. Базу удоб­нее всего про­ве­рить при со­се­дей все­гда не мень­ше, чем самих за­кра­шен­ных кле­ток (по­сколь­ку у каж­дой за­кра­нен­ной клет­ки есть сосед спра­ва и все эти со­се­ди раз­лич­ны).

Для пе­ре­хо­да ис­поль­зу­ем для идеи. Они обе про­сты и не­за­тей­ли­вы, но мало свя­за­ны друг с дру­гом.

Идея 1. Разо­бьем весь квад­рант на вер­ти­каль­ные по­ло­сы ши­ри­ны 2. За­ме­тим, что в каж­дой такой по­ло­се, в ко­то­рой есть хотя бы одна за­кра­шен­ная клет­ка (будем на­зы­вать такие по­ло­сы не­пу­сты­ми), со­се­дей хотя бы на од­но­го боль­ше, чем за­кра­шен­ных кле­ток. В самом деле, в каж­дой го­ри­зон­таль­ной до­ми­нош­ке (из ко­то­рых сло­же­на эта по­ло­са) со­се­дей все­гда ровно столь­ко жсе, сколь­ко за­кра­шен­ных кле­ток  — про­верь­те это! Кроме того, самая верх­няя за­кра­шен­ная клет­ка в по­ло­се даёт еще од­но­го «лиш­не­го» со­се­да  — свер­ху от себя.

Таким об­ра­зом, если среди полос ши­ри­ны 2 есть хотя бы n не­пу­стых, то со­се­дей ока­жет­ся хотя бы на n боль­ше, чем за­кра­шен­ных кле­ток, что и тре­бо­ва­лось (и без вся­кой ин­дук­ции).

Идея 2. Все клет­ки квад­ран­та раз­би­ва­ют­ся на диа­го­наль­ные ряды (в самом пер­вом ряду всего одна клет­ка, в сле­ду­ю­щем  — две, и т. д.). Рас­смот­рим самую верх­нюю диа­го­наль, в ко­то­рой еть хотя бы одна за­кра­шен­ная клет­ка. Все за­кра­шен­ные клет­ки в этой диа­го­на­ли раз­би­ва­ют­ся на блоки под­ряд иду­щих. Рас­смот­рим один из таких бло­ков; пусть в нём k за­кра­шен­ных кле­ток.

В сле­ду­ю­щей (более длин­ной) диа­го­на­ли есть кле­ток, со­сед­них с клет­ка­ми этого блока. За­ме­тим, что дру­гих за­кра­шен­ных со­се­дей у них нет; здесь ис­поль­зу­ет­ся, что со­сед­ние в нашей диа­го­на­ли с рас­смат­ри­ва­е­мым бло­ком клет­ки не за­кра­ше­ны (или во­об­ще на­хо­дят­ся за гра­ни­цей квад­ран­та). По­это­му, если вы­ки­нуть k кле­ток этого блока (пе­ре­стать счи­тать их за­кра­шен­ны­ми), ис­чез­нет со­се­дей. И если ока­жет­ся, что со­се­дей оста­лось хотя бы на боль­ше, чем за­кра­шен­ных кле­ток, то на ис­ход­ной кар­тин­ке их было хотя бы на n боль­ше.

Оста­лось разо­брать два слу­чая. Если то клет­ки на­ше­го диа­го­наль­но­го блока за­тра­ги­ва­ют хотя n полос ши­ри­ны 2, а зна­чит, ра­бо­та­ет идея Если же то после вы­ки­ды­ва­ния этого блока оста­нет­ся

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