Черная шкала подсчитывается до 19 с двумя битами, и только toggleable?

Question

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

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

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

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

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

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

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

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

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

Answer 1

Это звучит как вариации Prisoners and the Light Switch riddle, где обозначен один заключенный как «счетчик», а все остальные «увеличивают свой счет» только один раз.

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

Answer 2

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

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

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

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