Краденый чемодан

[Ktina]

Лиса Алиса и кот Базилио украли у Буратино чемодан. Замок на чемодане должен открыться, если три колёсика на нём (каждое из которых может занимать одну из восьми допустимых позиций) установлены в определённой комбинации. Однако, в силу ветхости механизма, чемодан откроется, если любые два колёсика из трёх поставлены в правильное положение.

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

[gris]

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

[mvvm]

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

[Ktina]

mvvm
Попыткой называется установка какой-либо комбинации колёсиков

[photon]

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

[Vladimir-80]

gris в сообщении #1365407 писал(а):

Любая набранная комбинация открывает 22 шифра. Меньше, чем за 24 попытки гарантировать вскрытие нельзя, но заложившись на перекрытия можно предположить, что попыток 37 хватит.

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

[photon]

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]$

[Vladimir-80]

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

[gris]

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

[Ktina]

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

[gris]

А чего вы так спешить хоронить задачу? Если бы взаимная открываемость шифров была бы отношением эквивалентности, то да. Но беда в том, что нет транзитивности. Например, 123 открывает 124, а 124 открывает 524. Но 524 не открывает 123 Подмножества пересекаются.

[waxtep]

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$

[photon]

Хм. Выходит, что не по 16 покрывает? Буду думать

[waxtep]

Уже для трех позиций (вместо восьми) не вижу как покрыть такой набор меньше чем за $9$ попыток:

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

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

[fiviol]

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