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


Задания
Версия для печати и копирования в MS Word
Тип 21 № 133
i

На плос­ко­сти изоб­ражён квад­рат n умно­жить на n кле­ток. Вер­ши­ны кле­ток будем на­зы­вать уз­ла­ми. Тре­бу­ет­ся в этом квад­ра­те уло­жить трубу («тёплый пол») так, чтобы вход был в левом ниж­нем углу, а выход – в со­сед­нем узле, и при этом труба про­шла бы ровно один раз через каж­дый узел. Трубу раз­ре­ша­ет­ся укла­ды­вать толь­ко по гра­ни­цам кле­ток. На ри­сун­ке изоб­ражён при­мер уклад­ки трубы в квад­ра­те 3×3. До­ка­жи­те, что уло­жить трубу воз­мож­но при любом нечётном зна­че­нии n и не­воз­мож­но ни при каком чётном n.

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

Ре­ше­ние.

Если n  — нечётное, то, на­при­мер, воз­мож­на уклад­ка «змей­кой» по ана­ло­гии с ри­сун­ком в усло­вии за­да­чи. Если n  — чётное, то ко­ли­че­ство узлов равно  левая круг­лая скоб­ка n плюс 1 пра­вая круг­лая скоб­ка \times левая круг­лая скоб­ка n плюс 1 пра­вая круг­лая скоб­ка   — нечётное число. Рас­кра­сим узлы в чер­ный белый цвет так, чтобы со­сед­ние узлы имели раз­ные цвета. Тогда марш­рут на­чи­на­ет­ся узлом оного цвета, а за­кан­чи­ва­ет­ся узлом дру­го­го цвета. Но тогда такой марш­рут имеет чётную длину (ко­ли­че­ство прой­ден­ных узлов). Сле­до­ва­тель­но, не­воз­мож­но по­стро­ить со­от­вет­ству­ю­щий марш­рут.

Источник/автор: Диана Лебедева