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


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

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

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

Ре­ше­ние.

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

Упо­ря­до­чить так на­бо­ры можно мно­ги­ми спо­со­ба­ми. Одна из воз­мож­ных идей со­сто­ит в сле­ду­ю­щем: каж­дый па­роль будем ин­тер­пре­ти­ро­вать как ко­ор­ди­на­ты точки в трех­мер­ном про­стран­стве (см. рис.). Ко­ор­ди­на­ты точек, ле­жа­щих на пря­мой, па­рал­лель­ной одной из ко­ор­ди­нат­ных осей, как раз от­ли­ча­ют­ся толь­ко в одном сим­во­ле. Зна­чит, если, дви­га­ясь па­рал­лель­но осям, мы обой­дем все точки, то тем самым по­лу­чим тре­бу­е­мое упо­ря­до­че­ние. Один из воз­мож­ных об­хо­дов пред­став­лен на ри­сун­ке.

 

Ответ: 26 на­жа­тий. Один из спо­со­бов пе­ре­бо­ра пред­став­лен на ри­сун­ке: (0, 0, 0), (0, 1, 0), …, (2, 0, 2).