2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3  След.
 
 Краденый чемодан
Сообщение02.01.2019, 16:13 
Аватара пользователя
Лиса Алиса и кот Базилио украли у Буратино чемодан. Замок на чемодане должен открыться, если три колёсика на нём (каждое из которых может занимать одну из восьми допустимых позиций) установлены в определённой комбинации. Однако, в силу ветхости механизма, чемодан откроется, если любые два колёсика из трёх поставлены в правильное положение.

Можно ли гарантированно открыть чемодан менее чем за 64 попытки?

 
 
 
 Re: Краденый чемодан
Сообщение02.01.2019, 17:12 
Аватара пользователя
Ну 64 это уж перебор (в очковом смысле). Любая набранная комбинация открывает 22 шифра. Меньше, чем за 24 попытки гарантировать вскрытие нельзя, но заложившись на перекрытия можно предположить, что попыток 37 хватит. Впрочем, это уж надо подбирать.
Хотя бывает так, что вроде бы очевидные предположения оказываются несостоятельными. Желаю вашей задаче, чтобы оказалось, что вопреки здравому смыслу нужно 64 попытки! Иначе зачем ей быть :-(

 
 
 
 Re: Краденый чемодан
Сообщение02.01.2019, 17:56 
Аватара пользователя
8 попыток
Надо тянуть крышку чемодана и одновременно крутить пальце (от кончика мизинца до локтя) все восемь позиций при каждой пробной цифре другого колеса. Где-нибудь механизм щёлккнет.
И одна позиция уже стоИт на замке)

 
 
 
 Re: Краденый чемодан
Сообщение02.01.2019, 18:33 
Аватара пользователя
mvvm
Попыткой называется установка какой-либо комбинации колёсиков

 
 
 
 Re: Краденый чемодан
Сообщение02.01.2019, 20:10 
Аватара пользователя
Если я нигде не ошибся, то достаточно $29$ проверок: сначала по очереди ставим $(0,0,0) - (1,1,1) - \ldots - (7,7,7)$. Каждая из комбинаций откинет по $22$ варианта. Затем из оставшихся $336$ берем первый попавшийся непроверенный, выставляем, попутно с ним проверится еще $15$, то есть $16$ за проверку. Затем берем следующий из еще непроверенных - еще $16$, и так до конца. Итого, $21 + 8$ проверок.

 
 
 
 Re: Краденый чемодан
Сообщение02.01.2019, 20:12 
gris в сообщении #1365407 писал(а):
Любая набранная комбинация открывает 22 шифра. Меньше, чем за 24 попытки гарантировать вскрытие нельзя, но заложившись на перекрытия можно предположить, что попыток 37 хватит.

А можете развернуть мысль? Что значит "Любая набранная комбинация открывает 22 шифра"? Из условия задачи я вижу, что любая набранная комбинация $ABC$ не содержит ни одной корректной пары (если чемодан не открылся), однако при этом любое колёсико замка (но только одно) может стоять в правильной позиции. А может и ни одного колёсика не стоять правильно в этом самом любом $ABC$.

 
 
 
 Re: Краденый чемодан
Сообщение02.01.2019, 20:18 
Аватара пользователя
Vladimir-80 в сообщении #1365442 писал(а):
"Любая набранная комбинация открывает 22 шифра"

Например, комбинация $(0,0,0)$ покрывает $8$ кодов вида $(0,0,a)$, где $a \in[0,7]$, еще $7$ кодов вида $(0,b,0)$, где $b \in[1,7]$ и еще $7$ вида $(c,0,0)$, где $c \in[1,7]$

 
 
 
 Re: Краденый чемодан
Сообщение02.01.2019, 20:22 
А, так понятней. Я думал в этом направлении, но размышлял про перебор разных пар двух колёсиков при последовательном вращении третьего. И упирался в те же 64 варианта.

 
 
 
 Re: Краденый чемодан
Сообщение02.01.2019, 21:18 
Аватара пользователя
Вообще, задача открывает путь к задачам о покрытиях. Допустив, есть некоторое множество и покрывающее его семейство подмножеств. Надо выбрать покрывающее подсемейство, удовлетворяющее различным требованиям. Часто описывается в графских терминах. В нашем случае множество состоит из трёхзначных чисел из трёх цифр. Каждое число генерирует известным образом подмножество из покрывающего семейства. Надо выбрать покрывающее подсемейство поменьше. В регулярных случаях это можно сделать рассуждением.
Надеюсь, ученики ТС двинутся не в криминальную сторону, а в компьютерную.

 
 
 
 Re: Краденый чемодан
Сообщение03.01.2019, 10:29 
Аватара пользователя
Обиднее всего то, что авторы олимпиады, на которой предлагалась эта задача, дают ответ - 64: http://gigabaza.ru/doc/117096.html (задача №3) Так и подмывает спросить, они там упоротые штоле? :shock:

 
 
 
 Re: Краденый чемодан
Сообщение03.01.2019, 11:52 
Аватара пользователя
А чего вы так спешить хоронить задачу? Если бы взаимная открываемость шифров была бы отношением эквивалентности, то да. Но беда в том, что нет транзитивности. Например, 123 открывает 124, а 124 открывает 524. Но 524 не открывает 123 :-( Подмножества пересекаются.

 
 
 
 Re: Краденый чемодан
Сообщение03.01.2019, 14:10 
Аватара пользователя
photon в сообщении #1365440 писал(а):
достаточно $29$ проверок
$29$ не хватит, к такой схеме можно привести контрпример:

$\begin{tabular}{cccc}
000&012&107&201\\
111&021&120&210\\
222&034&132&235\\
333&043&145&246\\
444&056&153&257\\
555&067&164&263\\
666&075&176&274\\
777&&&
\end{tabular}$

Ни один элемент не эквивалентен другому, в то же время много комбинаций непокрыто, например, $302$. Есть, гм, ощущение, что ответ и вправду $8+8\times7=64$

 
 
 
 Re: Краденый чемодан
Сообщение03.01.2019, 15:08 
Аватара пользователя
Хм. Выходит, что не по 16 покрывает? Буду думать

 
 
 
 Re: Краденый чемодан
Сообщение03.01.2019, 15:17 
Аватара пользователя
Уже для трех позиций (вместо восьми) не вижу как покрыть такой набор меньше чем за $9$ попыток:

$\begin{tabular}{cccc}
000&012&102&201\\
111&021&120&210\\
222&&&
\end{tabular}$

Ну, то есть, окей, конкретно эти $9$ вариантов можно покрыть за меньше, чем $9$ попыток; но ведь есть еще $27-9=18$ вариантов...

 
 
 
 Re: Краденый чемодан
Сообщение03.01.2019, 15:51 
8 попыток 011 022 033 044 055 066 077 100 взламывают все коды, которые начинаются с 01 02 03 04 05 06 07 10, а также все коды, начинающиеся с 00. Любые 55 попыток, которые начинаются с оставшиеся 55 комбинаций первых дух цифр заведомо откроют чемодан.

 
 
 [ Сообщений: 31 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group