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


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

При входе в лич­ный ка­би­нет на тер­ми­на­ле тре­бу­ет­ся вве­сти пя­ти­знач­ный па­роль из 0 и 1. Для этого на тер­ми­на­ле име­ют­ся 5 кно­пок и 5 око­шек. При на­жа­тии на кноп­ку в ей со­от­вет­ству­ю­щем окош­ке те­ку­щий сим­вол за­ме­ня­ет­ся на про­ти­во­по­лож­ный (то есть, если в окош­ке сей­час горит цифра 1, то после на­жа­тия на кноп­ку там будет 0, и на­о­бо­рот). Сей­час во всех окош­ках вы­став­ле­на 1. Какое наи­мень­шее ко­ли­че­ство на­жа­тий кно­пок по­тре­бу­ет­ся, чтобы пе­ре­брать все воз­мож­ные ва­ри­ан­ты па­ро­ля?

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

Ре­ше­ние.

Всего име­ет­ся 32=2 в сте­пе­ни левая круг­лая скоб­ка 5 пра­вая круг­лая скоб­ка пя­ти­знач­ных па­ро­лей из 0 и 1. Один такой па­роль 11111 уже на­бран, зна­чит, нам оста­ет­ся пе­ре­брать еще 31 ва­ри­ант, для чего по­тре­бу­ет­ся по край­ней мере 31 на­жа­тие кно­пок. По­ка­жем, что 31 на­жа­тия дей­стви­тель­но хва­тит. Для этого все пя­ти­знач­ные на­бо­ры упо­ря­до­чим так, чтобы со­сед­ние на­бо­ры от­ли­ча­лись толь­ко в одном сим­во­ле (клас­си­че­ский код Грея). Тогда пе­ре­ход от од­но­го на­бо­ра к со­сед­не­му будет осу­ществ­лять­ся на­жа­ти­ем одной кноп­ки, и всего по­тре­бу­ет­ся как раз 31 на­жа­тие.

Упо­ря­до­чить так на­бо­ры можно мно­ги­ми спо­со­ба­ми. Одну из воз­мож­ных идей про­ил­лю­стри­ру­ем на при­ме­ре трех­знач­ных па­ро­лей, ко­то­рые будем ин­тер­пре­ти­ро­вать как ко­ор­ди­на­ты вер­шин трех­мер­но­го куба со сто­ро­ной 1. Ко­ор­ди­на­ты вер­шин, ле­жа­щих на одном ребре, как раз от­ли­ча­ют­ся толь­ко в одном сим­во­ле. Зна­чит, если, дви­га­ясь вдоль ребер, мы обой­дем все вер­ши­ны куба, то тем самым по­лу­чим тре­бу­е­мое упо­ря­до­че­ние. От­ме­тим, что все вер­ши­ны лежат или на верх­ней А, или на ниж­ней грани В (рис.). То есть, можно ска­зать, что наш трех­мер­ный куб пред­став­ля­ет собой сумму двух гра­ней (или дбух­мер­ных кубов) А и В. Нач­нем обход, на­при­мер, с вер­ши­ны 111. Сна­ча­ла обой­дем вер­ши­ны дву­мер­но­го куба В (при этом по­след­няя цифра па­ро­ля (ко­ор­ди­на­та z) равна 1), затем пе­ре­ме­стим­ся на куб А и обой­дем его вер­ши­ны. По­лу­чим ис­ко­мую по­сле­до­ва­тель­ность па­ро­лей:

111 011 001 101 100 110 010 000.

Не­слож­но те­перь про­де­лать тоже самое и для пя­ти­знач­ных па­ро­лей (пя­ти­мер­ный куб равен сумме двух че­ты­рех­мер­ных кубов, а че­ты­рех­мер­ный куб равен сумме двух трех­мер­ных): 1) сна­ча­ла об­хо­дим двух­мер­ный куб, то есть ме­ня­ют­ся пер­вые две цифры, а три

по­след­ние так и оста­ют­ся рав­ны­ми 1:

11111 01111 00111 10111.

Пе­ре­хо­дим на вто­рую грань: те­перь тре­тья цифра 0, а по­след­ние две по-преж­не­му 1:

10011 11011 01011 00011.

Обход од­но­го трех­мер­но­го куба за­кон­чи­ли. Пе­ре­хо­дим на вто­рой трех­мер­ный куб́ (пред­по­след­няя цифра стала 0):

00001 01001 11001 10001 10101 00101 01101 11101.

Один че­ты­рех­мер­ный куб обо­шли. Пе­ре­хо­дим на вто­рой че­ты­рех­мер­ный куб, то есть, на­ко­нец, по­след­няя цифра ста­но­вит­ся

11100 01100 00100 10100 10000 11000 01000 00000 00010 01010 11010 10010 10110 00110 011 10 11110.

 

Ответ: 31 на­жа­тие. Па­ро­ли можно пе­ре­би­рать, на­при­мер, в таком по­ряд­ке:

1111101111001111011110011110110101100011000010100111001100011010100101011 0111101111000110000100101001000011000010000000000010010101101010010101100 01100111011110.


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