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

Question

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

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

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

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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