2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Краденый чемодан
Сообщение03.01.2019, 18:56 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 19:59 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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, уже не нужно.

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 21:08 
Аватара пользователя


07/01/16
1426
Аязьма
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}$

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 21:41 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 22:43 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 22:50 
Экс-модератор
Аватара пользователя


23/12/05
12046
PETIKANTROP в сообщении #1365769 писал(а):
010 020 030
110 120 130 + 101 и 000
210 220 230
310 320 330

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

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 22:58 
Аватара пользователя


15/04/15
1570
Калининград
photon в сообщении #1365771 писал(а):
А почему тут нет ни одной комбинации заканчивающейся на 2 или 3? И на 1 всего одна?

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

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 23:01 
Заслуженный участник
Аватара пользователя


09/09/14
6328
PETIKANTROP в сообщении #1365769 писал(а):
Если честно, то я дико туплю с вашими поэтажными планами.
Вот Вам 8 без этажей:
000, 330, 121, 211, 112, 222, 033, 303.

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

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 23:03 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 23:27 
Аватара пользователя


15/04/15
1570
Калининград
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 писал(а):
Мы ищем, чтоб было как можно меньше

Удачи!
Изображение

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение03.01.2019, 23:44 
Аватара пользователя


07/01/16
1426
Аязьма
PETIKANTROP в сообщении #1365779 писал(а):
Понятно! Забавно, что у вас с напарником нет ни одного общего межэтажного перекрытия.
А поменяйте у меня $0$ на $3$ и $1$ на $2$ - получится в точности вариант grizzly. Модульное домостроительство!
+ котик могуч и великолепен :-) :-)

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение04.01.2019, 02:19 
Аватара пользователя


07/01/16
1426
Аязьма
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: в академии генштаба задача могла бы звучать так: "сложить куб из наименьшего количества противотанковых ежей"

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение04.01.2019, 07:29 


15/05/13
324
Осталось показать, что 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 из таких кодов.

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение04.01.2019, 12:35 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Нашёл простую схему, которая масштабируется на любое $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 покрашенными клетками.

 Профиль  
                  
 
 Re: Краденый чемодан
Сообщение04.01.2019, 13:07 
Аватара пользователя


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

-- 04.01.2019, 13:14 --

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

-- 04.01.2019, 13:26 --

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 31 ]  На страницу Пред.  1, 2, 3  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group