Наименьшее число попыток. Комба с мегаполисов 2021

  • +20 социальных кредитов тому, кто решит. Этот тип задач часто встречается, поэтому думаю полезно знать основные подходы к ним.

Есть сейф, который можно открыть, введя секретный код, состоящий из n цифр, каждая из которых – это 0 или 1. Изначально было введено n нулей, но сейф остался закрыт (т.е. все нули – это не секретный код).

За одну попытку можно ввести произвольную последовательность из n цифр, каждая из которых – это 0 или 1. Если введенная последовательность совпадет с секретным кодом, то сейф откроется. Если введенная последовательность совпадет с секретным кодом в большем количестве позиций, чем предыдущая введенная последовательность, то будет слышен щелчок. В иных случаях сейф останется закрытым и щелчка не будет.

За какое наименьше количество попыток гарантированно удастся открыть сейф?

1 симпатия

Наверное самая банальная идея это строить ответ по цифрам. Вначале пытаемся 10000…000, если слышно щелчок то первая цифра один, иначе первая цифра это ноль. И так далее. По итогу гарантировано можно за n попыток открыть сейф.

Можно еще попробовать такой алгоритм: вначале первую цифру делаем 1, если слышно щелчок, то пытаемся первые 2 цифры сделать 1, после этого первые 4, 8 и тд. В момент когда щелчка нет, мы первые 2^k цифр фиксируем и для оставшихся применяем такой же алгоритм.

UPD: Второй алгоритм работает хуже если пароль это 11001100… Так что он не подходит, наверное лучше чем за n попыток нельзя.

1 симпатия

Тебе не только нужно узнать пароль от сейфа, но и открыть его. То есть если не было щелчка то тебе придётся откатить свое действие вроде и тогда это работает 2n - 1?

Думаю стоит это доказать?

Так нужно количество попыток, а не количество действий. По идее, мы можем менять последовательность внутри одной попытки как угодно

Он про то что щелчок по правилам сравнивает текущую последовательность с предыдущей. И если мы сделали попытку, то в следующий раз она будет “предыдущей”. И тогда предлагается сделать “откат”, то есть ввести строку которая была до этого вновь. Но этого делать нет смысла, можно просто использовать “неверный” префикс последовательности дальше. Если вы на iтую позицию поставили 1, и после проверки не было щелчка, то можно запомнить что здесь стоит 0, но в последующих запросах оставить на позиции i цифру 1, ведь она точно неверная, а значит не повлияет на щелчок.

В самом деле в первом комменте я этого не учёл. По итогу все ещё имеем алгоритм который работает за n операций.

Интуиция подсказывает что быстрее чем за n делать нельзя. Но доказательство придумать не могу.

Я кажется придумал, как доказать что n – минимальное количество попыток, для того чтобы узнать код замка

Ячейка может быть только правильной или неправильной. Изменим одну любую ячейку, под номер i. Если она стала правильно, то после проверки будет щелчок, если нет – не будет. Получается мы точно узнали стала ли ячейка правильной.

Изменим две любые ячейки i и j. Если они обе стали правильными, то мы услышим щелчок, так как количество правильных увеличилось на 2. Если же мы не слышим щелчка, то возможны три случая:

  1. Ячейка i – стала правильной, ячейка j – стала неправильной. Тогда количество правильных ячеек не изменилось 1-1 = 0
  2. Ситуация противоположная верхней. Ячейка i стала неправильной, j – правильной. Количество правильных ячеек не изменилось
  3. Обе ячейки стали неправильными. Тогда количество правильных ячеек уменьшилось на 2.

Как видно, изменение одной ячейки даёт нам достоверную информацию об одной ячейке. Изменение 2 ячеек даёт нам достоверную информацию об обоих только в случае, если они обе правильные, если же хотя бы одна из них неправильна, отсутствие щелчка не даёт нам достоверной информации ни об одной ячейке, так как есть три варианта правильности каждой ячейки.

Аналогично доказывается, что изменение трёх и более ячеек не даст нам достоверной информации о правильности каждой из них.

У нас есть два алгоритма

  1. Мы сразу возвращаем установленные неправильно цифры в правильное положение
  2. Мы узнаем весь код, а после возвращаем неправильно изменённые цифры в правильное положение.

Для первого алгоритма максимальное количество ходов будет при единственной единице на конце. Тогда мы выполнил 2n-1 ходов, как и сказал @Zhabka

Для второго алгоритма после n-ного хода введено будет 11111...111111, в этом случае максимальное количество ходов после этого будет n-1, так как он поменяет максимальное количество цифр, не равное n. В итоге получаем тоже 2n-1 ходов.

Для наибольшей эффективности алгоритма сравним вероятности исходов.

  1. В первом случае вероятность равна \frac {1}{2^n}, где 2^n – количество размещений n цифр, которые могут равнятся единице или нулю
  2. Во втором случае вероятность равна \frac{n}{2^n}, так как есть n исходов, при котором код является набором из n-1 нулей и единицы

Так как вероятность первого исхода меньше, чем второго, имхо, лучше использовать первый метод

Если ты знаешь код, то тебе нужна всего одна попытка чтобы открыть. Там не 2n-1

А не заметил, спасибо

Сорри, что долго не отвечал.

Ответ действительно n. Некоторые алгоритмы здесь похоже, что верны.
Вот официальные решения:


2 симпатии

Да, изменение двух не дает нам достоверной информации. Но это не доказывает, что мы не можем гарантированно открыть сейф меньше, чем за n ходов.
То, что изменение одной ячейки выгоднее на данный момент, не значит, что оно выгоднее в общем. (То, что операция выгодна локально, не значит, что она выгодна глобально). Например вопрос, на который ваше решение не отвечает: Почему, мы не можем после двух каких-то операций изменений двух ячеек получить достоверную информацию? То есть одна операция не дает достоверной информации, но вместе со второй они исключают какие-то варианты и остается только один.

2 симпатии
© 2021-2022 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)