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

[waxtep]

Да, есть даже очень туполинейный способ взломать за $48$ попыток: на всех восьми "этажах" кубика $8\times8\times8$ применить по четыре комбинации $00z,11z,22z,33z$ и на любом одном этаже "выжечь" квадрат $4\times4$ с $4\leqslant x,y\leqslant7$. Наверное, можно и еще лучше

[grizzly]

waxtep в сообщении #1365671 писал(а):

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

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

000,222,110,101,011.

waxtep в сообщении #1365671 писал(а):

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

Ну так для остальных вариантов ничего, кроме этих 5, уже не нужно.

[waxtep]

grizzly в сообщении #1365726 писал(а):

Ну так для остальных вариантов ничего, кроме этих 5, уже не нужно.

Да, я уже осознал, что $n^2$ - это с запасцем. Тогда, может быть, мы имеем дело с $\frac{n(n+1)}2-1$? По трем точкам, исходя из того, что оно все таки должно быть квадратично (для $n=1$ формула дает ноль попыток, но, это и логично: в этом случае чемодан открыт прямо сразу, не нужно ни одной попытки). Для исходной задачи это дает прогноз в $35$ попыток

-- 03.01.2019, 21:16 --

Неа, для $n=4$ можно за $8$ попыток, а предлагаемая формула дает $9$

-- 03.01.2019, 21:29 --

"Поэтажный план" для $n=4$:

$\begin{tabular}{|c|c|c|c|} \hline \bullet&&&\\ \hline &&&\\ \hline &&&\\ \hline &&&\bullet\\ \hline \end{tabular}$

$\begin{tabular}{|c|c|c|c|} \hline &&&\\ \hline &&\bullet&\\ \hline &\bullet&&\\ \hline &&&\\ \hline \end{tabular}$

$\begin{tabular}{|c|c|c|c|} \hline &&&\\ \hline &\bullet&&\\ \hline &&\bullet&\\ \hline &&&\\ \hline \end{tabular}$$

$\begin{tabular}{|c|c|c|c|} \hline &&&\bullet\\ \hline &&&\\ \hline &&&\\ \hline \bullet&&&\\ \hline \end{tabular}$

[grizzly]

waxtep в сообщении #1365744 писал(а):

для $n=4$ можно за $8$ попыток

Да, этот случай даже проще, чем $n=3$ (у меня то же решение). Не исключено, что формулы для чётных и нечётных могут быть разными или хотя бы отличаться на 1. К такому выводу я пришёл когда искал стратегию для $n=3$ (из-за пересечения диагоналей).

Думаю, для $n=8$ нужно искать 32-решение.

[PETIKANTROP]

Если честно, то я дико туплю с вашими поэтажными планами. У меня выходит расчет по формуле (n-1)$\cdot $n+2.
Одну комбинацию можно зачесть как исходную. Т.о. всего для n=4 у меня получается 12+2 комбинаций:
010 020 030
110 120 130 + 101 и 000
210 220 230
310 320 330

[photon]

PETIKANTROP в сообщении #1365769 писал(а):

010 020 030
110 120 130 + 101 и 000
210 220 230
310 320 330

А почему тут нет ни одной комбинации заканчивающейся на 2 или 3? И на 1 всего одна? Их должно быть с нулями поровну.

[PETIKANTROP]

photon в сообщении #1365771 писал(а):

А почему тут нет ни одной комбинации заканчивающейся на 2 или 3? И на 1 всего одна?

потому что они не нужны. К примеру задан код 012. А мы набрали 010. Совпали две первые цифры - чемодан вскрыт. Т.е. комбинация 010 кодирует 012 и 013. Так же и для остальных триплетов.

[grizzly]

PETIKANTROP в сообщении #1365769 писал(а):

Если честно, то я дико туплю с вашими поэтажными планами.

Вот Вам 8 без этажей:
000, 330, 121, 211, 112, 222, 033, 303.

Мы ищем, чтоб было как можно меньше.

[waxtep]

PETIKANTROP в сообщении #1365769 писал(а):

Если честно, то я дико туплю с вашими поэтажными планами.

По-моему, удобно всю эту галантерею геометрически представлять, как куб $n\times n\times n$ в координатных осях; каждый кубик $1\times1\times1$ представляет из себя попытку, которая так же взламывает все кубики над и под ним, слева и справа и ближе/дальше. Например, мои картиночки для $n=4$ выше соответствуют восьми комбинациям $030,300,111,221,122,212,003,333$. Они взламывают все возможные $64$ варианта шифра

[PETIKANTROP]

grizzly в сообщении #1365774 писал(а):

Вот Вам 8 без этажей:
000, 330, 121, 211, 112, 222, 033, 303.

waxtep в сообщении #1365775 писал(а):

Например, мои картиночки для $n=4$ выше соответствуют восьми комбинациям $030,300,111,221,122,212,003,333$.

Понятно! Забавно, что у вас с напарником нет ни одного общего межэтажного перекрытия.

grizzly в сообщении #1365774 писал(а):

Мы ищем, чтоб было как можно меньше

Удачи!

[waxtep]

PETIKANTROP в сообщении #1365779 писал(а):

Понятно! Забавно, что у вас с напарником нет ни одного общего межэтажного перекрытия.

А поменяйте у меня $0$ на $3$ и $1$ на $2$ - получится в точности вариант grizzly. Модульное домостроительство!
+ котик могуч и великолепен

[waxtep]

grizzly в сообщении #1365757 писал(а):

Думаю, для $n=8$ нужно искать 32-решение.

А, так вот же:

$$\begin{tabular}{c|c|c|c|c|c|c|c|c|c} x\rightarrow&0&1&2&3&4&5&6&7&y\downarrow\\ \hline &0&6&7&5&&&&&0\\ \hline &7&0&5&6&&&&&1\\ \hline &6&5&0&7&&&&&2\\ \hline &5&7&6&0&&&&&3\\ \hline &&&&&2&4&3&1&4\\ \hline &&&&&3&2&1&4&5\\ \hline &&&&&4&1&2&3&6\\ \hline &&&&&1&3&4&2&7\\ \hline \end{tabular}$$

Перебираем $32$ комбинации $xyz$, где $z$ берется из таблицы, а $x,y$ - номер строки и столбца для данного (непустого) $z$. Понятно, что любую цифру можно обменять местами с любой другой, важен общий кхм паттерн!
PS: в академии генштаба задача могла бы звучать так: "сложить куб из наименьшего количества противотанковых ежей"

[fiviol]

Осталось показать, что 31 попытки не хватит. В этом случае хотя бы для одной цифры из восьми (пусть для нуля) есть только три попытки, начинающиеся с этой цифры (пусть это, не меняя общности, 000, 011 и 022). Но они закрывают не более 39 кодов, то есть 15+13+11, начинающихся с 0 (а именно те коды, которые имеют на оставшихся двух позициях хотя бы одну цифру 0, 1 или 2). Оставшиеся 25 кодов, начинающихся с 0, таким образом, должны закрываться 25 попытками, у которых на первой позиции не 0, а на второй и третьей позициях - всевозможные комбинации двух цифр, среди которых нет 0, 1 или 2. Остается всего 3 попытки, которыми надо покрыть еще по крайней мере те коды, где на первой позиция не 0, а на второй и третьей позиции 01, 02, 10, 12, 20 или 21. Но таких кодов 42 штуки, а каждая из трех оставшихся попыток может покрыть не более 9 из таких кодов.

[grizzly]

Нашёл простую схему, которая масштабируется на любое $n$ вида $n=2^k$ с требуемым количеством попыток $2^{2k-1}$. Уверен, что для таких $n$ это оптимум, а для других будет неизбежно хуже.

Для примера покажу на $n=8$ в терминах кубика $8\times 8\times 8$ с его квадратными слоями. Каждый слой поделим на зоны: один внутренний квадрат $4\times 4$, четыре угловых квадрата $2\times 2$ и 4 прямоугольника $2\times 4$. В половине слоёв красим 4 клетки во внутреннем квадрате, покрывая всё, кроме угловых квадратов (в разных слоях покрашенные клетки должны иметь разные координаты). В другой половине слоёв красим по 2 клетки в двух угловых квадратах, расположенных по диагонали (тоже следим, чтобы в разных слоях покрашенные клетки имели разные координаты). В итоге получаем нужное решение с 32 покрашенными клетками.

[waxtep]

Задача известна: A000982, и, похоже, берет свое начало в "Кванте". На OEIS ссылка на французскую компиляцию, стр.56 и далее (файл в открытом доступе)

-- 04.01.2019, 13:14 --

Вот оригинал в "Кванте" №4, 1972

-- 04.01.2019, 13:26 --

+ в статье в "Кванте" пишут, что для $k$-мерной задачи при $k\geqslant4$ общий ответ неизвестен, только оценки с двух сторон