2
1

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

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

задан 2 Янв '19 17:06

10|600 символов нужно символов осталось
2

Будем считать, что цифры изменяются от 0 до 7. Рассмотрим 63 комбинации, у которых первые две цифры принимают все значения помимо 00, а третья цифра некоторым образом зависит от первых двух. Если первые две цифры кода не 00, то замок откроется. В противном случае возможно 8 кодов 000, 001, ... , 007. Возьмём наши варианты с первыми двумя цифрами 01, 02, ... , 07, и положим третью цифру равной второй. Тогда все замки с кодами кроме 000 можно открыть. Для первых двух цифр 10 положим третью равной 0, что позволит открыть и этот замок.

Видно, что тут есть некоторый "запас", поэтому есть ощущение, что и меньшего числа перебираемых вариантов будет достаточно. Скажем, для замков с двоичной системой достаточно всего двух попыток: 010 и 101.

ссылка

отвечен 2 Янв '19 18:56

@falcao, большое спасибо! Любопытно, чему равен этот самый «запас» и каково минимальное число попыток.

(2 Янв '19 19:38) Казвертеночка
2

@Казвертеночка: да, мне тоже интересно, но я пока не успел над этим подумать. Можно для троичной системы посмотреть сначала. А вообще, такие вещи может знать @knop.

(2 Янв '19 19:51) falcao

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

(3 Янв '19 2:10) Казвертеночка
1

@Казвертеночка: странно, конечно. Но, с другой стороны, там вообще не предложено никакого решения. Произносимая фраза -- это никак не решение. А где это вообще проводилось?

(3 Янв '19 2:22) falcao
2

@Казвертеночка, @falcao, это задача о покрытии с параметрами q=8, n=3, r=1. Известно, что K=32 (http://old.sztaki.hu/~keri/codes/6-21_tables.pdf).

(3 Янв '19 3:45) Urt

@Urt: интересно! Как Вы думаете, что здесь будет проще -- пример или оценка?

(3 Янв '19 4:23) falcao
1

@falcao, я эту задачку "не пощупал", но по интуиции напрашивается 4х8 комбинаций с проверкой по модулю 8. Граница минимального объема дает плохой результат K>=23. Получение точной оценки снизу мне представляется проблематичным.

(3 Янв '19 4:33) Urt

@falcao, «А где это вообще проводилось?» ..... Там написано только: «Задания

школьного этапа Всероссийской олимпиады школьников

по математике

11 класс», они не уточняют.

(3 Янв '19 11:23) Казвертеночка
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
2

Появилась такая идея построения кода покрытия с параметрами $%q=8, n=3, r=1, K=32.$%

  1. Сначала строим код $%E_0$% с параметрами: $%q=4$% (над алфавитом $%A_0=\{0,2,4,6\}), n=3, r=1, K_0=16,$% с одним проверочным символом по модулю 8. Код обладает свойством: Любые две позиции кода содержат все пары над $%A_0$%, т. е. являются информационными.
  2. Затем строим такой же код $%E_1$% над алфавитом $%A_1=\{1,3,5,7\}$% (т. е. класс смежности кода $%A_0$%).
  3. Объединяем эти коды и получаем код $%E=E_0\cup E_1 $% над алфавитом $%A=\{0,1,...,7\}$%, с параметрами $%q=8, n=3, r=1, K=32.$% Действительно, в каждой тройке символов над $%A$% содержится либо два четных, либо два нечетных символа. Следовательно, для любой последовательности $%w$% длины $%n=3$% над $%A$% либо в $%E_0$%, либо в $%E_1$% найдется кодовое слово (кода $%E$%), находящееся на расстоянии $%r=1$% от $%w.$%
ссылка

отвечен 3 Янв '19 7:20

изменен 3 Янв '19 7:48

@Urt, большое спасибо!

(3 Янв '19 11:25) Казвертеночка
1

@Urt: у меня была такая же идея (насчёт присутствия двух символов одной чётности). Но я её не реализовал до конца. Правильно ли я понимаю, что в первом случае берутся тройки вида a,b,-a-b, где третье число выбирается mod 8? Типа 000, 026, 422 и т.п.?

(3 Янв '19 12:18) falcao
2

@falcao, да это так. В коде E символы a,b,c всех кодовых слов (abc) имеют одинаковую четность, причем a+b+c+I=0 mod 8, где I – индикатор четности символов a,b,c.

(3 Янв '19 12:48) Urt
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,484
×1,405
×276
×272
×51

задан
2 Янв '19 17:06

показан
808 раз

обновлен
3 Янв '19 12:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru