сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

В каж­дой клет­ке квад­ра­та 2019\times 2019 про­ве­де­ны обе диа­го­на­ли. Су­ще­ству­ет ли за­мкну­тый марш­рут, со­сто­я­щий из этих диа­го­на­лей, не про­хо­дя­щий ни по одной из диа­го­на­лей два­жды и по­се­ща­ю­щий при этом все клет­ки квад­ра­та (то есть со­дер­жа­щий хотя бы одну диа­го­наль из каж­дой клет­ки).

Спрятать решение

Ре­ше­ние.

Рас­кра­сим вер­ши­ны всех кле­ток в два цвета в шах­мат­ном по­ряд­ке. За­ме­тим, что каж­дая диа­го­наль со­еди­ня­ет две вер­ши­ны од­но­го цвета. Это зна­чит, что с диа­го­на­лей од­но­го цвета нель­зя по­пасть на диа­го­на­ли дру­го­го (марш­рут дол­жен со­сто­ять из диа­го­на­лей, а не из их ча­стей, то есть в се­ре­ди­не клет­ки пе­ре­хо­дить с диа­го­на­ли на диа­го­наль нель­зя).

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

 

Ответ: нет.

Спрятать критерии
Критерии проверки:

Толь­ко ответ «Нет» — 0 бал­лов.


Аналоги к заданию № 709: 782 Все