13.2.06

Desafio difícil - A fuga dos prisioneiros

Numa prisão do Texas, o director decide divertir-se à custa dos 23 reclusos. Reúne-os todos numa sala vazia. Todas as paredes estão nuas, excepto uma onde se podem ver dois interruptores, lado a lado, na posição "on". O director explica as regra de um jogo que inventou.



- Vamos escrever o nome de cada recluso num papel e metemos os 23 papéis num saco. Cada dia tira-se aleatoriamente um nome do saco, e o prisioneiro sorteado terá de vir a esta sala. Após isso, o nome volta a ser colocado no saco. Uma vez na sala, o recluso terá obrigatoriamente de mudar a posição de um só interruptor, o da direita ou o da esquerda. Tem de mudar a posição de um, mas não dos dois. Depois disso, voltará para a sua cela.

- No início, como vêm, os interruptores estão ambos na posição "on". Iremos jogar este jogo até um qualquer prisioneiro dizer que todos os seus colegas encarcerados já passaram pelo menos uma vez por esta sala. Se de facto for verdade, todos vocês são libertados. Caso contrário, serão todos condenados a prisão perpétua.



- Para comemorar o início do jogo, vamos ter um grande banquete hoje à noite. Depois disso, e durante a duração do jogo, todos os prisioneiros estarão impedidos de falar uns com os outros! Ficarão nas respectivas celas. Cada dia, o prisioneiro cujo nome seja sorteado será levado em segredo à sala para cumprir o acordado, após o qual será de novo confinado à sua cela.

Nessa noite, os prisioneiros combinam uma estratégia... Como fazer para conseguir ter a certeza absoluta de que todos já passaram pela sala?

Resumo:

- cada dia é sorteado um prisioneiro, de entre os 23. Quem já foi sorteado anteriormente pode voltar a sê-lo;


- o prisioneiro sorteado tem de mexer um dos interruptores. Nem mais, nem menos;

- no início, ambos os interruptores estão na posição "on";


- o jogo acaba quando um prisioneiro afirmar que todos os outros passaram pela sala. Estando certo, todos os reclusos são libertados. Caso contrário, serão condenados a prisão perpétua.

11 comentários:

Mr Fights disse...

na foto ilustrativa os botões estão off ao contrário do que diz o texto. se repararem estes botões não são dos comuns em que se carrega mas sim dos antigos com uma patilha que se puxa para cima ou para baixo. como a sombra está em baixo os botões estão em off... mas o k interessa para o quebra cabeças é mesmo apenas e só o texto

/me disse...

Obrigado, mr. :) Alterei a foto, para ficar mais claro!

Joao disse...

Eu cá acho que eles usam código morse. Chegam à cela e fazem sapateado. Assim cada um sabe a cada noite quem foi! :P

LeGourmet disse...

Deixam caír um cabelo num sítio combinado e depois fazem-lhes testes de DNA. Quando estiverem todos, avisam o chefe. :S

Anónimo disse...

Eu tenho uma teoria mas é tão rebuscada que me parece impraticável, mas é tudo o que consegui após mais de 12h com este enigma na cabeça!!! :S
(Enoch's going mad because of you...)

Vamos lá ver se me consigo explicar...
Pensei que os reclusos podiam estipular que os interruptores seriam mudados sempre na mesma ordem. Ou seja, o jogo começa com os dois interruptores para cima. O recluso número 1 começaria então, por exemplo, por baixar o interruptor da direita, o nº 2 baixaria o da esquerda, o nº 3 levantaria o da direita, o nº 4 levantaria o da esquerda... and so on, seguindo sempre a mesma ordem. Cada recluso podia, então, prever a posição dos interruptores em cada noite. O truque estaria em que a primeira vez que um recluso se repetisse, por vez de seguir a ordem estabelecida para mover os interruptores, infringi-la-ia desfazendo o último movimento, de forma a que o recluso que se lhe seguisse notasse que alguém já lá tinha estado pelo menos uma segunda vez, já que os interruptores tinham um movimento em atraso. Constatando isto, todos os reclusos seguiriam com o movimento estabelecido -- mesmo se já tivessem sido chamados à sala anteriormente --, mas todos notariam que alguém já lá tinha estado uma segunda vez. Isto, durante os primeiros 23 dias. A partir do 24º dia e até ao dia 46º, este jogo repetir-se-ia: a primeira pessoa repetida na sala infringiria o movimento estabelecido dos interruptores, os que se lhe seguissem mantê-la-iam -- ah, e o que tinha infringido o movimento na primeira ronda de 23 dias, a partir de agora já não faria nada de anormal; seguiria mantendo a rotação estabelecida dos interruptores.
Estes ciclos de 23 dias ter-se-iam de repetir no mínimo 22 vezes!! Estamos a falar de 506 dias. A partir deste dia, o recluso que tivesse a honra de fazer a 23ª infracção poderia afirmar que já todos os reclusos tinham passado pela sala!

Não sei se isto faz sentido... Enigmas algorítmicos nunca foram o meu forte -- suponho que o Mindful ou o Zé poderiam (ou não!...) sustentar a minha teoria com alguma equação matemática -- mas parece-me que tenho razão. A parte de como prever a posição dos interruptores é a que encontro mais difícil de explicar e acho que nem vou tentar... Também é a parte mais nebulosa, para mim... Mas acho que seria possível!...

Any better ideas??

Enoch

/me disse...

Lamento, Enoch, não funciona... Imagina que na primeira "sessão" de 23 vezes, calhava sempre o mesmo recluso na sala. Estragava o teu esquema todo. ;)
Nunca mais ninguém saberia que ele tinha chegado a estar na sala.

Uma pista: é preciso (para a solução que sei) haver um recluso de referência. Chamemos-lhe "Butch". Por exemplo. Ou Zé, porque não? :p

Anónimo disse...

no no no! Porque cada recluso apenas poderia alterar a ordem estabelecida na 1ª vez que se encontrasse repetido na sala! Ainda que o Sr. Butcher fosso chamado 60.000 vezes à sala, apenas teria feito uma alteração. Só é permitida uma alteração em cada ciclo de 23 dias, de forma que assim que um recluso detectasse uma alteração no 23º ciclo (ou estivesse a ponto de fazê-la), podia inferir que todos os 23 reclusos já tinham vindo à sala pelo menos 2 vezes! Quanto a isto não tenho dúvidas. O único ponto onde confesso que não me aclaro (e onde estaria bem uma fórmula matemática daquelas que não sei fazer...) é na previsão dos movimentos dos interruptores, porque teria de fazer-se 22 alterações à ordem e os interruptores apenas permitem 4 posições diferenciadas...

Ai, sei lá, eu estudei música!!

Enoch

Anónimo disse...

Punha o gajo do chapéu amarelo virado para o muro dos interruptores.

/me disse...

Enoch, assim não funciona. Lembra-te que os prisioneiros não falam entre si. Assim, ao fim da 5ª volta, é possível que tenha passado sempre a mesma pessoa pela sala, ou 5 pessoas diferentes...

O que se pode fazer é escolher um prisioneiro como referência, chamemos-lhe Butch. Quanto aos outros, procedem do seguinte modo: da primeira vez que passarem pela sala, se o botão da direita estiver "on", passam-no para "off". Se já estiver "off", mexem no da esquerda. Quando o Butch passar pela sala, se o botão da direita estiver no "off", ele conta 1 e passa-o para "on". O prisioneiro que já mexeu o botão da direita não volta a mexer nesse, só no da esquerda. E só o Butch pode passar o botão da direita para "on".

Estou com sono, mas espero ter-me feito entender, hehe.

Bom esforço, Enoch. :)

Anónimo disse...

...
...mas ainda acho... com alguns cálculos mesmo muuuito complicados... :S
*Humpf...*
Eca!

Enoch

/me disse...

Enoch, se tu achas, acredito. :P
Eca mesmo. ;)
Abraço. ;)