Будем на­зы­вать ле­сен­кой сле­ду­ю­щую часть таб­ли­цы из кле­ток: самый левый стол­бец, сле­ду­ю­щий стол­бец без верх­не­го числа, сле­ду­ю­щий стол­бец без двух верх­них чисел, ..., самый пра­вый стол­бец без верх­них чисел.

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

Оцен­ка. I спо­соб. Пусть   — числа на глав­ной диа­го­на­ли (по­ря­док, в ко­то­ром они там стоят, нам не­из­ве­стен). Для каж­до­го по­кра­сим само и все числа, сто­я­щие либо под в том же столб­це, либо слева от в той же стро­ке, в цвет номер k. Тогда чисел каж­до­го цвета будет ровно n, и каж­дое число ле­сен­ки, кроме чисел глав­ной диа­го­на­ли, будет по­кра­ше­но ровно в два цвета  — «цвет стро­ки» и «цвет столб­ца» (а каж­дое число на глав­ной диа­го­на­ли  — толь­ко в один свой цвет).

За­ме­тим, что боль­ше всех осталь­ных чисел цвета k и боль­ше всех чисел, цвет ко­то­рых имеет номер мень­ше k (так как Тем самым не мень­ше, чем ко­ли­че­ство чисел с цве­та­ми от 1 до k. Но таких чисел ровно

по­сколь­ку чисел цвета ровно n, чисел цвета 2, но не цвета ровно чисел цвета k, но ни од­но­го из цве­тов   — ровно От­сю­да

II спо­соб. Пусть   — числа на глав­ной диа­го­на­ли. Рас­смот­рим не­ко­то­рое Если число из ле­сен­ки на­хо­дит­ся в одной стро­ке или в одном столб­це с одним из диа­го­наль­ных чисел то оно не пре­вос­хо­дит его, и, зна­чит, не пре­вос­хо­дит числа могут на­хо­дить­ся толь­ко в стро­ках и столб­цах с чис­ла­ми   — таких чисел всего Все осталь­ные чисел ле­сен­ки не боль­ше то есть Скла­ды­вая, по­лу­ча­ем точ­ную оцен­ку на

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

Далее дей­ству­ем ана­ло­гич­но. Имен­но, пусть мы уже про­ве­ли стрел­ки в клет­ки k-й диа­го­на­ли так, что пути по стрел­кам из не имеют общих кле­ток. Берём клет­ки k-й диа­го­на­ли, в ко­то­рые при­хо­дят пути из и про­во­дим из них стрел­ки в по­пар­но раз­лич­ные клет­ки -й диа­го­на­ли. Из остав­шей­ся клет­ки про­во­дим любую стрел­ку на -ю диа­го­наль.

Те­перь не­труд­но до­ка­зать оцен­ку. Из кле­ток ведут k путей, причём их на­ча­ла длины со­от­вет­ствен­но не имеют общих кле­ток. Число не мень­ше всех чисел, встре­ча­ю­щих­ся на этих путях; по­это­му

Сум­ми­руя, по­лу­ча­ем

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

от­ку­да и сле­ду­ет оцен­ка.