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

Рис. 1

Пусть n  — чётное. За­пол­ним таб­ли­цу чис­ла­ми от 1 до n² так: ста­вим их друг за дру­гом, на­чи­ная от 1, сна­ча­ла в пер­вой стро­ке слева на­пра­во, а потом  — вдоль столб­цов: вниз по по­след­не­му столб­цу, вверх по пред­по­след­не­му, и т. д. (по­лу­ча­ет­ся что-то по­хо­жее на змей­ку). В итоге число n² ока­жет­ся прямо под 1, см. при­мер для n  =  6 на ри­сун­ке 1.

За­ме­ним те­перь числа на их остат­ки по мо­ду­лю (см. рис. 2). Не­труд­но до­ка­зать, что они рас­став­ле­ны сле­ду­ю­щим об­ра­зом: для нечётного столб­ца по­след­нее (ниж­нее) число сов­па­да­ет с пер­вым чис­лом сле­ду­ю­ще­го чётного столб­ца и вто­рым чис­лом сле­ду­ю­ще­го нечётного. Зна­чит, каж­дый стол­бец на­чи­на­ет­ся с остат­ка i, рав­но­го сво­е­му но­ме­ру, кроме n-го, ко­то­рый на­чи­на­ет­ся с нуля, причём в чётных столб­цах остат­ки идут по воз­рас­та­нию с i до n − 1, а потом с нуля до i − 1 а в нечётных  — по убы­ва­нию с i до 0 , а потом с n − 1 до i + 1.

До­ка­жем, что в каж­дой стро­ке все остат­ки раз­лич­ны. Пусть в какой-то стро­ке сов­па­ли два остат­ка. Они не могут на­хо­дить­ся в столб­цах одной чётно­сти  — такие столб­цы по­лу­ча­ют­ся друг из друга цик­ли­че­ским сдви­гом. Зна­чит, один оста­ток на­хо­дит­ся в чётном столб­це, а вто­рой  — в нечётном. Но тогда эти два остат­ка стоят на клет­ках раз­но­го цвета и не могут сов­па­дать, про­ти­во­ре­чие. Пред­по­ло­жим, что уда­лось за­пол­нить таб­ли­цу при нечётном n. К про­ти­во­ре­чию можно прий­ти по-раз­но­му.

Рис. 2

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

Рас­смот­рим клет­ки таб­ли­цы, в ко­то­рых стоят числа, да­ю­щие оста­ток k при де­ле­нии на n. Сумма их но­ме­ров строк и столб­цов по усло­вию равна

так как каж­дая стро­ка и каж­дый стол­бец участ­ву­ют по од­но­му разу; в част­но­сти, эта сумма чётна. Но у каж­дой белой клет­ки сумма «ко­ор­ди­нат» нечётна, а у каж­дой чёрной  — чётна, сле­до­ва­тель­но, число белых кле­ток среди рас­смот­рен­ных чётно.

Взяв k  =  1 и k  =  2, по­лу­ча­ем, что среди чисел с остат­ком 1 чётное ко­ли­че­ство на­хо­дит­ся на белых клет­ках, и среди чисел с остат­ком 2  — тоже. Но для каж­до­го числа с остат­ком 1 сле­ду­ю­щее за ним число имеет оста­ток 2 и стоит на клет­ке про­ти­во­по­лож­но­го цвета. Зна­чит, на чёрных клет­ках стоит чётное ко­ли­че­ство чисел с остат­ком 2 и всего чисел с остат­ком 2 чётно  — про­ти­во­ре­чие с нечётно­стью n.

Ответ: при всех чётных n.

При­ведём дру­гое ре­ше­ние.

За­ме­ним числа на их остат­ки от де­ле­ния на n и про­ведём стрел­ку из каж­дой клет­ки с еди­ни­цей в со­сед­нюю клет­ку с двой­кой. У нас име­ет­ся n стре­лок, со­еди­ня­ю­щих еди­ни­цы и двой­ки. У не­ко­то­рых стре­лок могут быть пар­ные  — стрел­ки про­ти­во­по­лож­но­го на­прав­ле­ния, за­ни­ма­ю­щие те же два ряда (рис. 3). Но число стре­лок нечётно, по­это­му найдётся стрел­ка без пары.

Рис. 3

Рис. 4

Пусть, на­при­мер, такая стрел­ка го­ри­зон­таль­на и ведёт из i-го столб­ца в (i + 1)-й (рис. 4). В (i + 1)-м столб­це тоже есть еди­ни­ца. По­сколь­ку у пер­вой стрел­ки нет пары, вто­рая стрел­ка может вести толь­ко в (i + 2)-й стол­бец (двой­ка в (i + 1)-м столб­це уже за­ня­та). В (i + 2)-м столб­це тоже есть еди­ни­ца, и стрел­ка из неё может вести толь­ко в (i + 3)-й стол­бец (двой­ки в (i + 1)-м и (i + 2)-м столб­цах уже за­ня­ты). Про­дол­жая, дойдём до еди­ни­цы в n-м столб­це, от­ку­да стрел­ке идти уже не­ку­да. Про­ти­во­ре­чие.