Черный ящик, считающий до 19 только с 2 битами, и только переключаемый?

Question

Некоторые студенты спрашивали об этом на другом сайте, но не получили ответов. У меня было несколько ударов, но это было довольно сложно.

Выполнение этого с помощью только переключателей потребует степени сжатия 9: 1, поэтому я полагаю, что хитрость заключается в правилах, которые вы назначаете студентам. Возможно, каждому ученику нужен свой набор правил?

Я думал о том, чтобы разрешить много итераций, где нет ответа, обращая внимание только на студентов в правильной последовательности. Я также думал о кодировании числа ученика в двоичном виде и объединении его с битами от коммутаторов, чтобы получить больше битов для работы, но это все еще проблема сжатия / проверки: даже если один из этих битов использовался для проверки на четность у вас все еще есть большой потенциал для ложных срабатываний.

Предположительно, проблему не спросили бы, если бы не было способа сделать это. Может быть, это распространенная проблема на курсах компьютерных и общеизвестных? Во всяком случае, без лишних слов ...

«Вот проблема, которая у меня есть для компьютерного класса. Мне это кажется математической и может включать двоичный код. Я не уверен, все мои идеи ведут в тупик.

Девятнадцати студентам предоставляется возможность выиграть приз, играя в игру. Через некоторое время, чтобы определиться со стратегией, все ученики будут помещены в отдельные звукоизолирующие изоляторы, в которых абсолютно нет возможности общаться.

Игра ведется следующим образом. В комнате есть два выключателя, которые начинаются в положении «выключено». Я буду приводить студентов в эту комнату по одному. Каждый раз, когда студент входит в комнату, он или она должен нажать один из переключателей. Все ученики будут в конечном итоге доставлены в комнату, но некоторые ученики могут быть привлечены более одного раза.

Если один человек правильно скажет мне, что все были в комнате, тогда все выиграют приз. Однако, если кто-то неправильно скажет мне, что все были в комнате, то все будут накормлены аллигаторами! Обратите внимание, что либо все студенты выиграли приз, либо все проиграли.

Ваша задача - определить стратегию, которая позволит каждому выиграть приз (а не быть съеденным аллигаторами). "

Answer 1

Это звучит как вариация Заключенных и загадки Переключателя света , где один заключенный обозначен как "счетчик", а все остальные "увеличивают свой счет" только один раз.

Предположительно, счетчик включит один переключатель, и если вы никогда не считали, вы выключите этот переключатель; другой переключатель был бы "мусором". Когда счетчик выключил выключатель 18 раз, он знает, что все остальные ученики были в комнате.

Answer 2

В том виде, как эта проблема сформулирована, организатор / учитель может убедиться, что ему никогда не придется выдавать приз: впускать каждого учащегося в комнату по очереди - что позволяет счетчику только подсчитать еще одного ученика. Затем итерируйте только часть студентов - скажем, 3 из них.

Тогда или Счетчик может сосчитать двух других учеников, а затем застрянет, или Счетчик никогда не вернется в комнату.

Это удовлетворяет указанным условиям: каждый человек входит в комнату хотя бы один раз, а некоторые учащиеся входят несколько раз.

Чтобы позволить студентам побеждать, вам необходимо добавить условие, что между посещениями любого отдельного студента в раздевалке существует определенный предел.