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

База Воз­мож­ны два раз­ме­ще­ния чер­ных кле­ток A и B: в со­сед­них уг­ло­вых клет­ках и в про­ти­во­по­лож­ных уг­ло­вых клет­ках. С точ­но­стью до по­во­ро­та доски они разо­бра­ны на верх­них двух ри­сун­ках.

Пе­ре­ход от n к

Если клет­ки A и B можно на­крыть до­с­кой ни один из углов ко­то­рой не сов­па­да­ет с углом доски то под­пра­вим путь фишки из A в B, об­хо­дя­щий доску сле­ду­ю­щим об­ра­зом. В какой-то мо­мент путь по­па­дет в вер­ши­ну, по­ме­чен­ную на ри­сун­ке бук­вой c (рис. а). Тогда с точ­но­стью до сим­мет­рии фишка шла по марш­ру­ту Пе­ре­на­пра­вим ее из d в f, затем по ча­со­вой стрел­ке по ка­ем­ке доски до g и потом в c.

Если так на­крыть клет­ки A и B нель­зя, то хотя бы одна из них на­хо­дит­ся на гра­ни­це доски Пусть для опре­де­лен­но­сти это клет­ка A (в про­тив­ном слу­чае A и B можно по­ме­нять ро­ля­ми, рас­смот­рев об­рат­ный путь). Если клет­ка B рас­по­ло­же­на не на краю, то сде­ла­ем обход таким об­ра­зом. От клет­ки A пой­дем по ка­ем­ке про­тив ча­со­вой стрел­ки до клет­ки c, затем на клет­ку A′ и после этого по марш­ру­ту от A′ до B, ко­то­рый су­ще­ству­ет по пред­по­ло­же­нию ин­дук­ции (рис. б).

Рис. а

Рис. б

Рис. в

Если же клет­ка B также рас­по­ло­же­на на краю, то сде­ла­ем обход иначе. От­ме­тим сле­ду­ю­щую за B по ча­со­вой стрел­ке клет­ку c и со­сед­нюю с ней чер­ную клет­ку в квад­ра­те   — клет­ку A′. Также от­ме­тим сле­ду­ю­щую за A по ча­со­вой стрел­ке клет­ку d и со­сед­нюю с ней чер­ную клет­ку в квад­ра­те   — клет­ку B′. Клет­ки c и d не могут ока­зать­ся уг­ло­вы­ми, по­сколь­ку они белые, а уг­ло­вые клет­ки по усло­вию чер­ные. От клет­ки A пой­дем по ка­ем­ке про­тив ча­со­вой стрел­ки до клет­ки c, затем на клет­ку A′ и после этого по марш­рут от A′ до B′, потом на d и даль­ше по ка­ем­ке до B (рис. в).

Ответ: да.