Таб­ли­цу раз­ме­ра­ми n x n будем обо­зна­чать Оче­вид­но, что для таб­ли­цы ис­ко­мое мак­си­маль­ное k равно 3. Экс­пе­ри­мен­ти­руя с таб­ли­цей можно за­ме­тить, что (ниже мы до­ка­жем это стро­го). Сде­лан­ные на­блю­де­ния поз­во­ля­ют пред­по­ло­жить, что для про­из­воль­но­го мак­си­маль­ное зна­че­ние k равно До­ка­жем это.

Пре­жде всего, по­ка­жем, что еди­ни­цы таб­ли­ца со­дер­жать не может. Для этого при­ве­дем контр­при­мер, но сна­ча­ла вспом­ним опре­де­ле­ние транс­вер­са­ли. Транс­вер­са­лью таб­ли­цы T_n на­зы­ва­ют набор из n ячеек, со­дер­жа­щих 1, любые две из ко­то­рых рас­по­ло­же­ны в раз­ных стро­ках и раз­ных столб­цах. Ясно, что если какие-то ячей­ки об­ра­зо­вы­ва­ли транс­вер­саль, то и после пе­ре­ста­нов­ки строк или столб­цов они снова об­ра­зу­ют транс­вер­саль. На ри­сун­ке изоб­ра­же­на таб­ли­ца n x n с еди­ни­ца­ми, рас­по­ло­жен­ны­ми на глав­ной диа­го­на­ли, а также в таб­ли­це 2 × 2 в левом верх­нем углу. Такая таб­ли­ца со­дер­жит две транс­вер­са­ли. В то же время таб­ли­ца, у ко­то­рой все 1 лежат на или выше по­боч­ной диа­го­на­ли, со­дер­жит не более одной транс­вер­са­ли. Зна­чит, к тре­бу­е­мо­му в за­да­че виду таб­ли­ца на ри­сун­ке при­ве­де­на быть не может. По­это­му

По­ка­жем, что еди­ни­цу все­гда можно пе­ре­не­сти на по­боч­ную диа­го­наль или выше. Итак,

дана таб­ли­ца T_n, со­дер­жа­щая еди­ниц. В такой таб­ли­це обя­за­тель­но есть стро­ка или ровно с одной 1, или не со­дер­жа­щей еди­ниц вовсе. Рас­смот­рим эти слу­чаи.

 ·  В таб­ли­це T_n есть стро­ка, со­дер­жа­щая ровно одну 1. По­ста­вим эту стро­ку на по­след­нее место. Затем, пе­ре­став­ляя столб­цы, пе­ре­ме­стим эту един­ствен­ную 1 в край­ний левый стол­бец.

 ·  В таб­ли­це T_n есть стро­ка, со­дер­жа­щая толь­ко нули. По­ста­вим эту стро­ку на по­след­нее место. Пе­ре­став­ляя столб­цы, сде­ла­ем так, чтоб в край­нем левом столб­це была хоть одна еди­ни­ца.

В каж­дом слу­чае по­лу­че­на под­таб­ли­ца со­дер­жа­щая, по край­ней мере, на одну 1 мень­ше, чем таб­ли­ца С таб­ли­цей можно вы­пол­нить ана­ло­гич­ные пре­об­ра­зо­ва­ния. В ре­зуль­та­те за шага при­дем к таб­ли­це для ко­то­рой уже уста­нов­ле­но, что Фор­му­ла до­ка­за­на.

Ответ: n + 1.