aforismos e afins

22 dezembro 2005

Quizz nº 5

Há 100 prisioneiros que estão encarcerados em solitárias. Há uma sala onde está uma lâmpada, inicialmente desligada. Nenhum prisioneiro consegue ver a lâmpada da sua cela. Todos os dias, o guarda escolhe, aleatoriamente, um prisioneiro para visitar a sala onde está a lâmpada. Uma vez nessa sala, o prisioneiro pode decidir ligar a lâmpada. O prisioneiro tem ainda a opção de afirmar que todos os 100 prisioneiros já passaram pela sala. Se isto for falso, todos os 100 prisioneiros são mortos. Se for verdade, os prisioneiros são soltos. Logo, a afirmação só deve ser feita quando o prisioneiro estiver 100% certo daquilo que afirma. Aos 100 prisioneiros é dada a possibilidade de se reunirem no pátio, para discutir um plano.
.
Que 'plano' devem eles escolher de forma a que um deles possa eventualmente fazer uma afirmação correcta?
.
Nota 1: "aleatoriamente" significa que em cada período, todo e qualquer prisioneiro pode ser escolhido com probabilidade 1/100, independentemente das escolhas passadas. Ou seja, um indivíduo pode ser escolhido mais do que uma vez. Por exemplo, nas 100 primeiras chamadas, não é lícito que sejam chamados os 100 tipos. Isso seria muito improvável até. Em cada período, todos os prisioneiros estão na mesma situação e qualquer deles pode (voltar a) ser escolhido com igual probabilidade.
.
Nota 2: naturalmente, a lâmpada nunca se "gasta".
.
Nota 3: em jeito de "dica", não se foquem na "rapidez" com que determinado plano (algoritmo) possa resultar ou não. Imaginem, se isso facilitar, que o guarda escolhe um prisioneiro a cada minuto.
.
A resposta a este e ao anterior quizz será dada depois do Natal. Os comentários voltam a ser moderados. O Miguel Madeira adiantou já duas respostas, sendo uma delas correcta. O Pedro Romano adiantou uma certeira (apesar de não ter a certeza que a resposta estava correcta*). O jcd forneceu são só a descrição mais sucinta duma possível solução, como ofereceu também um refinamento que a torna mais eficiente. O Karloos também já picou o ponto. Parabéns aos quatro.
.
*porque uma das belezas da matemática e da lógica é que temos obrigação de saber se o resultado a que chegamos é correcto ou não.

posted by Tiago Mendes at 8:11 da tarde

12 Comments:

  • Vejo uma hipotese, mas implica que os prisioneiros possam contar os dias (ou os minutos), para saber quantas vezes um prisioneiro foi à sala antes:

    Sempre que um prisioneiro fosse chamado pela segunda vez à sala, mandava acender a luz.

    Se o prisioneiro chamado no 100º dia vir a luz apagada, diz que já foram todos à sala (porque, em 100 dias, foi um diferente à sala). Se vir a luz acesa, apaga-a.

    No 101º (e ao 201º, 301º) dia, recomeçam o esquema a partir do principio (se não forem soltos), e só acendem a luz se tiverem sido chamados mais que uma vez após o dia 100. De novo, se no dia 200 a luz estiver apagada, é sinal que lá foram todos.

    Mas acho que isto iria levar uns milhões de anos (mesmo se fosse por minuto e não por dia)

    By Blogger Miguel Madeira, at 10:26 da tarde  

  • Uma hipótese que é capaz de ser melhor é combinarem que 99 prisioneiros, da primeira vez que forem à sala, acendem a luz (se a luz já estiver acesa, deixa estar acesa, e acende-a da prímeira vez em que chegar à sala e a luz estar apagada). Ou seja, cada um dos 99 prisioneiros vai acender a luz só uma vez.

    Há um 100º prisioneiro que não acende a luz, e, se chegar à sala e a luz estiver acesa, apaga-a. Na 99º vez que apagar a luz, é sinal que todos os outros prisioneiros já foram à sala e acenderam a luz.

    Então ele diz que já todos foram à sala.

    By Blogger Miguel Madeira, at 1:33 da manhã  

  • Pequena dúvida:
    ´Sabendo que o guarda escolhe aleatoriamente um prisioneiro e que, eventualemnte, todos acabarão por passar pela sala da lampada, pergunto se essa escolha aleatória significa (ou pode significar) que o guarda poderá escolher o mesmo prisioneiro mais que uma vez?

    Rá

    By Anonymous Anónimo, at 10:50 da manhã  

  • Ando à procura duma solução elegante, mas até agora só consigo lá chegar pela força bruta.

    Escolhe-se um porta voz, que é o único autorizado a dar a resposta ao carcereiro.

    O procedimento a seguir por cada prisioneiro seria:

    1. Da primeira vez que entrar na sala com a luz apagada, acende-a.

    2. Se a luz estiver acesa, não faz nada.

    3. Se já acendeu a luz anteriormente, não faz nada, mesmo que a luz esteja apagada.

    O porta-voz, sempre que for à sala e encontar a luz acesa, apaga-a.

    Quanto apagar a luz pela 99ª vez, sabe que já todos visitaram a sala. O problema é que isto pode demorar anos.

    By Blogger jcd, at 4:16 da tarde  

  • Até se pode poupar algum tempo dia. O primeiro prisioneiro a visitar a sala não precisa fazer nada. Conta sempre como um. O porta-voz só tem que encontrar a luz acesa 98 vezes.

    By Blogger jcd, at 4:38 da tarde  

  • BomNatal para ti meu caro amigo cibernautico.
    LA-C

    By Blogger Luís Aguiar-Conraria, at 10:51 da tarde  

  • Só me lembro desta para já. Selecciona-se um prisioneiro X para ser um marco. Cada um dos outros prisioneiros acenderia a luz apenas uma vez e, caso a luz já esteja acesa, não fazem nada. Cada vez que o prisioneiro X fôr chamado à sala, apagará a luz (se ela estiver acesa). À 99ª vez que o prisioneiro X vir a luz acesa terá a certeza que todos já passaram por lá. Sem fazer cálculos, penso que isto corresponderá a uma pena perpétua. Penso que esta será válida mas irei pensar numa melhor :)

    By Blogger Carlos Guimarães Pinto, at 1:00 da manhã  

  • Já agora, mais um pequeno refinamento.

    Combina-se que o que for chamado no primeiro dia acende a luz e o que for chamado no segundo dia apaga-a. Se for o mesmo preso a ser chamado nos dois primeiros dias, a luz fica acesa.

    O porta-voz é sempre aquele que for chamado no terceiro dia, que apaga a luz se esta estiver acesa, e a regra começa a funcionar a partir daí já com uma informação adicional: parte-se quase certamente com o contador em 2 (ou 3 se contarmos com o porta-voz) e só no caso de haver repetição é que a contagem começa em 1, ou uma em cada mil vezes com o contador a zero, se for o mesmo prisioneiro a ser chamado nos 3 primeiros dias.

    By Blogger jcd, at 1:56 da tarde  

  • Obrigado, meu caro. Tudo de bom para ti também. Abraço,

    By Blogger Tiago Mendes, at 3:06 da tarde  

  • Já agora...

    Vamos combinar as coisas de outra forma.

    Concordamos para os primeiros 'n' dias um procedimento diferente.

    Nestes primeiros 'n' dias, ninguém acende a luz até alguém visitar a sala pela segunda vez.

    Esse passa a ser o porta voz. Se o primeiro a entrar duas vezes na sala for o 10º, já a contagem pode começar em 9. Nessa altura, acende a luz. O nº apaga-a. SE o nº encontrar a luz apagada, sabe que já visitaram a sala antes dele n-1.

    Daqui para a frente segue o esquema proposto, mas os que entraram na sala nos primeiros x dias com a luz apagada, nunca mais a acendem.

    Deve haver um 'n' que optimiza isto.

    By Blogger jcd, at 3:12 da tarde  

  • Há 100 prisioneiros que estão encarcerados em solitárias. Há uma sala onde está uma lâmpada, inicialmente desligada. Nenhum prisioneiro consegue ver esta lampada antes de entrar na sala. Todos os dias, o guarda escolhe, aleatoriamente, um prisioneiro para visitar a sala onde está a lâmpada. Uma vez nessa sala, o prisioneiro pode decidir ligar a lâmpada(ou não). O prisioneiro tem ainda a opção de afirmar que todos os 100 prisioneiros já passaram pela sala. Se isto for falso, todos os 100 prisioneiros são mortos. Se for verdade, os prisioneiros são soltos. Logo, a afirmação só deve ser feita quando o prisioneiro estiver 100% certo daquilo que afirma. Aos 100 prisioneiros é dada a possibilidade de se reunirem no pátio, para discutir um plano(uma unica vez).

    Um grupo de pessoas com olhos de diferentes cores mora numa ilha. Eles são perfeitos em seu pensamento lógico — se uma conclusão pode ser deduzida logicamente, eles o farão instantaneamente. Ninguém sabe a cor de seus próprios olhos. Toda noite, à meia-noite, uma balsa pára na ilha. Se qualquer um descobrir a cor de seus próprios olhos, ele deve deixar a ilha na mesma noite. Todos podem ver qualquer um o tempo todo e mantêem a contagem do número de pessoas que eles vêem com cada cor dos olhos (excluindo a si próprios), mas eles não podem se comunicar. Todo mundo na ilha conhece as regras deste parágrafo.

    Nessa ilha há 100 pessoas de olhos azuis, 100 de olhos castanhos e a Guru (ela tem olhos verdes). Então, cada pessoa de olhos azuis pode ver 100 pessoas de olhos castanhos e 99 de olhos azuis (e uma de olhos verdes), mas isso não lhe diz a cor de seus próprios olhos; tanto quanto ele sabe os totais podem ser 101 castanhos e 99 azuis. Ou 100 castanhos, 99 azuis, e ele pode ter olhos vermelhos.

    A Guru pode falar apenas uma vez (digamos, ao meio-dia), e um único dia em todos os seus anos sem fim na ilha. Em pé em frente aos habitantes da ilha, ela diz:

    “Eu posso ver alguém que tem olhos azuis.”

    Quem deixa a ilha, e em que noite?

    No resto do texto original, o autor basicamente explica que não há truques. O que a Guru quis dizer é exatamente o que você entendeu, não há espelhos ou superfícies reflexivas, nenhum jogo de palavras no problema. É só lógica mesmo.

    E, por fim, a resposta não é “ninguém deixa a ilha”.

    By Anonymous Anónimo, at 8:07 da manhã  

  • Os envolvidos precisam definir um líder que poderá alterar o estado da lampada mais que uma vez, diferindo ele dos outros.
    Os demais, acho que só podem alterar o estado da lâmpada uma única vez. Dependo da decisão do líder, eles podem apagar, ou acender.
    Todas as vezes que o "líder" entrar na sala, ele ascende ou apaga ela dependo da decisão que deu início na "jornada" sendo que, se ela estiver acesa, ele deverá deixá-la acesa.
    O tal "Líder", contará todas as vezes que ele ascende ou apaga a lâmpada.
    Já os outros prisioneiros, estarão indo á sala e apagando a lâmpada. Mas na sua primeira vez que vão, e depois, deixando ela do jeito que está. Não alterando o estado da lampada das outras vezes que voltam à aquela sala.

    By Anonymous Anónimo, at 3:15 da tarde  

Enviar um comentário

<< Home