Black-box contando para 19 com apenas 2 bits e apenas alternável?

Question

Alguns alunos perguntaram isso em outro site, mas não obtiveram respostas. Eu tive algumas facadas, mas achei bastante complicado.

Fazer isso apenas com os comutadores exigiria uma taxa de compressão de 9: 1, então acho que o truque está muito nas regras que você atribui aos alunos. Talvez todo aluno precise de um conjunto diferente de regras?

Pensei em permitir muitas iterações em que nenhuma resposta surge, apenas prestando atenção aos alunos na sequência correta. Também pensei em codificar o número do aluno como binário e combiná -lo com os bits dos interruptores, para conseguir mais pedaços para trabalhar, mas isso ainda é um problema de compressão/validação: mesmo que um desses bits fosse usado para paridade , você ainda teria um grande potencial para falsos positivos.

Presumivelmente, o problema não teria sido perguntado se não havia uma maneira de fazê -lo. Talvez este seja um problema comum nos cursos da Comp-SCI e bem conhecido? Enfim, sem mais delongas ...

"Aqui está um problema que tenho para uma aula de computador. Parece meio matemático para mim e poderia envolver o código binário. Não tenho certeza, todas as minhas idéias levam a becos sem saída.

Dezenove alunos têm a oportunidade de ganhar um prêmio jogando um jogo. Depois de algum tempo para decidir sobre uma estratégia, todos os alunos serão colocados em câmaras de isolamento à prova de som separadas, com absolutamente nenhuma maneira de se comunicar.

O jogo é jogado da seguinte forma. Existem dois interruptores de luz em uma sala que começará na posição "off". Vou levar os alunos a esta sala, um de cada vez. Cada vez que um aluno entra na sala, ele ou ela deve virar um dos interruptores. Todos os alunos acabarão sendo trazidos para a sala, mas alguns estudantes podem ser trazidos mais de uma vez.

Se uma pessoa me diz corretamente que todo mundo esteve na sala, todo mundo ganha o prêmio. No entanto, se alguém me disser incorretamente que todo mundo esteve na sala, todos serão alimentados aos jacarés! Observe que todos os alunos ganham o prêmio ou outros perdem.

Sua tarefa é determinar uma estratégia que permitirá que todos ganhem o prêmio (e não sejam comidos por jacarés) ".

Answer 1

Isso soa como uma variação do Prisioneiros e o enigma do interruptor de luz, onde um prisioneiro é designado como um "contador" e todo mundo "aumenta sua contagem" apenas uma vez.

Presumivelmente, o balcão ligaria um interruptor e, se você nunca tivesse sido contado, desligaria esse interruptor; O outro interruptor seria "lixo". Uma vez que o balcão desligou o interruptor 18 vezes, ele sabe que todos os outros estudantes estiveram na sala.

Answer 2

A maneira como o problema é redigido, o organizador/professor pode garantir que ele nunca precise dar o prêmio: permitir que cada aluno entre na sala - o que apenas permite que o contador conte um outro aluno. Em seguida, apenas itera um subconjunto dos alunos - digamos 3 deles.

Então, o balcão pode contar dois outros estudantes e ficarem presos, ou o balcão nunca volta para a sala.

Isso satisfaz as condições especificadas: todo mundo entra na sala pelo menos uma vez e alguns estudantes vão várias vezes.

Para permitir que os alunos venham, você precisa adicionar a condição de que exista um limite finito entre as visitas de qualquer aluno à sala de troca.