Quebra -cabeças de indução
Content
Crianças enlameadas quebra -cabeça
Descrição
Há um conjunto de crianças atentas. Eles pensam perfeitamente logicamente. As crianças consideram possível ter um rosto lamacento. Nenhuma das crianças pode determinar o estado próprio. Mas toda criança conhece o estado de todas as outras crianças. Um custodiante diz às crianças que pelo menos um deles tem um rosto lamacento. As crianças são informadas de que devem dar um passo à frente se souberem que seu próprio rosto está enlameado. A seguir, o custodiante começa a contar e, após cada derrame, toda criança lamacenta tem a oportunidade de avançar.
Solução lógica
Vamos supor que apenas 2 filhos: Alice e Bob. Se apenas Alice estiver suja, ela avançará no primeiro golpe, porque não vê outros rostos sujos. O mesmo é para Bob. Se Alice vê Bob não dar um passo à frente no primeiro golpe, ela deve concluir que ele certamente vê outra criança lamacenta e eles avançarão simultaneamente no segundo golpe.
Vamos supor que existem apenas 3 filhos: Alice, Bob e Charly. Se houver menos de três crianças enlameadas, o quebra -cabeça evolui como no caso com 2 crianças. Se Charly vê que Alice e Bob estão enlameados e não estão avançando no segundo golpe, todos juntos darão avançar no terceiro golpe.
Pode -se provar que x {\ displayStyle x} crianças enlameadas avançarão após x {\ displayStyle x} golpes.
Solução teórica do jogo
O quebra -cabeça de crianças enlameadas também pode ser resolvido usando a indução para trás da teoria dos jogos. O quebra -cabeça de crianças enlameadas pode ser representado como um extenso jogo de forma de informação imperfeita. Todo jogador tem duas ações - fique para trás e dê um passo à frente. Há um movimento por natureza no início do jogo, que determina as crianças com e sem rostos lamacentos. As crianças não se comunicam como em jogos não cooperativos. Cada derrame é um movimento simultâneo de crianças. É um jogo seqüencial de comprimento ilimitado. A solução teórica do jogo precisa de algumas suposições adicionais:
All children are rational and all children's rationality is common knowledge. This means that Alice is rational, Alice knows that Bob is rational and Alice knows that Bob knows that Charly is rational and so on and vice versa.Stepping forward without having a muddy face results in a big penalty.Stepping forward with a muddy face results in a reward.Every stroke results in minor negative penalty aka discount factor for every child until any of them stepped forward. Any multiple of the minor penalty is always a lesser evil than the big penalty.Se apenas Alice estiver enlameada, a última suposição torna irracional para ela hesitar. Se Alice e Bob estão lamacentos, Alice sabe que o único motivo de Bob de ficar depois do primeiro golpe é a apreensão de receber a grande penalidade de dar um passo adiante sem um rosto lamacento. No caso de x {\ displayStyle x} crianças enlameadas, recebendo x {\ displaystyle x} vezes a penalidade menor ainda é melhor que a grande penalidade.
O quebra -cabeça de chapéu de homem sábio do rei
Descrição
O rei chamou os três homens mais sábios do país para sua corte para decidir quem se tornaria seu novo conselheiro. Ele colocou um chapéu em cada uma de suas cabeças, de modo que cada homem sábio pudesse ver todos os outros chapéus, mas nenhum deles podia ver o seu. Cada chapéu era branco ou azul. O rei deu sua palavra aos homens sábios de que pelo menos um deles estava usando um chapéu azul; Em outras palavras, pode haver um, dois ou três chapéus azuis, mas não zero. O rei também anunciou que o concurso seria justo com os três homens. Os homens sábios também foram proibidos de falar um com o outro. O rei declarou que o homem que se levantou primeiro e anunciou corretamente a cor de seu próprio chapéu se tornaria seu novo conselheiro. Os sábios ficaram sentados por muito tempo antes de se levantar e anunciar corretamente a resposta. O que ele disse e como ele deu certo?
Solução
Os sábios do rei são um dos quebra -cabeças de indução mais simples e um dos indicadores mais claros do método usado.
Suppose that there was one blue hat. The person with that hat would see two white hats, and since the king specified that there is at least one blue hat, that wise man would immediately know the colour of his hat. However, the other two would see one blue and one white hat and would not be able to immediately infer any information from their observations. Therefore, this scenario would violate the king's specification that the contest would be fair to each. So there must be at least two blue hats.Suppose then that there were two blue hats. Each wise man with a blue hat would see one blue and one white hat. Supposing that they have already realized that there cannot be only one (using the previous scenario), they would know that there must be at least two blue hats and therefore, would immediately know that they each were wearing a blue hat. However, the man with the white hat would see two blue hats and would not be able to immediately infer any information from his observations. This scenario, then, would also violate the specification that the contest would be fair to each. So there must be three blue hats.Como deve haver três chapéus azuis, o primeiro homem a descobrir que se levantará e dizem azul.
Solução alternativa: isso não requer a regra de que o concurso seja justo para cada um. Pelo contrário, depende do fato de que todos são homens sábios e que leva algum tempo antes que eles cheguem a uma solução. Só pode haver três cenários, um chapéu azul, dois chapéus azuis ou 3 chapéus azuis. Se houvesse apenas um chapéu azul, o usuário desse chapéu veria dois chapéus brancos, e rapidamente sabia que ele precisa ter um chapéu azul, para que ele se levantasse e anunciasse isso imediatamente. Como isso não aconteceu, deve haver pelo menos dois chapéus azuis. Se houvesse dois chapéus azuis, qualquer um dos que vestiam um chapéu azul olhavam e via um chapéu azul e um chapéu branco, mas não conhecem a cor do seu próprio chapéu. Se o primeiro usuário do chapéu azul assumisse que ele tinha um chapéu branco, ele saberia que o outro usuário do chapéu azul estaria vendo dois chapéus brancos, e assim o segundo usuário do chapéu azul já teria se levantado e anunciado que ele estava usando um chapéu azul. Assim, como isso não aconteceu, o primeiro usuário do chapéu azul saberia que ele estava usando um chapéu azul e poderia se levantar e anunciar isso. Como um ou dois chapéus azuis é tão fácil de resolver e que ninguém se levantou rapidamente, todos devem estar usando chapéus azuis.
Problema de Josephine
Descrição
No reino de Josephine, toda mulher tem que passar em um exame lógico antes de poder se casar. Toda mulher casada conhece a fidelidade de todo homem no reino, exceto seu próprio marido, e a etiqueta exige que nenhuma mulher seja contada sobre a fidelidade de seu marido. Além disso, um tiro disparado em qualquer casa no reino será ouvido em qualquer outra casa. A rainha Josephine anunciou que pelo menos um homem infiel havia sido descoberto no reino, e que qualquer mulher que que seu marido fosse infiel era obrigada a atirar nele à meia -noite após o dia depois de descobrir sua infidelidade. Como as esposas conseguiram isso?
Solução
O problema de Josephine é outro bom exemplo de um caso geral.
If there is only 1 unfaithful husband, then every woman in the Kingdom knows that except for his wife, who believes that everyone is faithful. Thus, as soon as she hears from the Queen that unfaithful men exist, she knows her husband must be unfaithful, and shoots him.If there are 2 unfaithful husbands, then both their wives believe there is only 1 unfaithful husband (the other one). Thus, they will expect that the case above will apply, and that the other husband's wife will shoot him at midnight on the next day. When no gunshot is heard, they will realise that the case above did not apply, thus there must be more than 1 unfaithful husband and (since they know that everyone else is faithful) the extra one must be their own husband.If there are 3 unfaithful husbands, each of their wives believes there to be only 2, so they will expect that the case above will apply and both husbands will be shot on the second day. When they hear no gunshot, they will realize that the case above did not apply, thus there must be more than 2 unfaithful husbands and as before their own husband is the only candidate to be the extra one.In general, if there are n unfaithful husbands, each of their wives will believe there to be n-1 and will expect to hear a gunshot at midnight on the n-1th day. When they do not, they know their own husband was the nth.Esse problema também é conhecido como o problema dos maridos traidores, o problema das esposas infiel, o problema das crianças lamacentas. É logicamente idêntico ao problema dos olhos azuis.
Esse problema também aparece como um problema que envolve chapéus pretos e chapéus brancos no clássico livro clássico de C. L. Liu 'Elementos de matemática discreta'. [Citação necessária]
Alice na convenção de lógicos
Descrição
Na convenção secreta dos lógicos, o lógico mestre colocou uma banda na cabeça de cada participante, de modo que todos os outros pudessem vê -la, mas a própria pessoa não poderia. Havia muitas cores diferentes da banda. Todos os lógicos estavam sentados em círculo, e o mestre os instruiu a que uma campainha fosse tocada na floresta em intervalos regulares: no momento em que um lógico conhecia a cor em sua própria testa, ele deveria sair no próximo sino. Eles foram instruídos a não falar, nem usar um espelho ou câmera ou evitar o uso da lógica para determinar a cor da banda. Caso quaisquer impostores tivessem se infiltrado na Convenção, qualquer pessoa que não saia de sair na hora seria removida rangermente no momento correto. Da mesma forma, qualquer pessoa que tenta sair mais cedo seria mantida no lugar e removida no momento correto. O mestre tranquilizou o grupo afirmando que o quebra -cabeça não seria impossível para nenhum verdadeiro lógico presente. Como eles fizeram isso?
Solução
Alice, na Convenção de Lógicos, é uma indução geral mais um salto de lógica.
Leap of logic: Every colour must appear at least twice around the circle. This is because the Master stated that it would not be impossible for any Logician to solve the puzzle. If any colour existed only once around the circle, the Logician who bore it would have no way of knowing that the colour even existed in the problem, and it would be impossible for them to answer.Each of the Logicians can look around the circle and count the number of times they see each colour. Suppose that you are one of the Logicians and you see another colour only once. Since you know each colour must exist at least twice around the circle, the only explanation for a singleton colour is that it is the colour of your own band. For the same reason, there can only be one such singleton colour, and so you would leave on the first bell.Likewise any Logicians who see another colour only once should be able to determine their own colour, and will either leave with dignity or be thrown out as an infiltrator. Equivalently, any colour for which there are only two bands of that colour will be eliminated after the first bell has rung. Thereafter there must be at least three bands of any remaining colour.Suppose you do not see any colour once, but you do see a colour twice. If these were the only bands of this colour, then these two Logicians ought to have left at the first bell. Since they did not, that can only be because your own band is the same colour, so you can leave at the second bell.Therefore, every logician would watch until a group of a given colour that they expected to leave failed to leave. Then they would know that they had that colour, and would leave on the next bell.When only one colour remained, that colour would all leave on the next bell, because they would know that they could not have any other colour (since then it would be impossible for them to know their colour).Quebra -cabeça básico de chapéu
Descrição
Vários jogadores estão usando um chapéu, que pode ter várias cores especificadas. Os jogadores podem ver as cores de pelo menos os chapéus de outros jogadores, mas não a própria. Com comunicação altamente restrita ou nenhuma, alguns dos jogadores devem adivinhar a cor do chapéu. O problema é encontrar uma estratégia para os jogadores determinarem as cores de seus chapéus com base nos chapéus que vêem e no que os outros jogadores fazem. Em algumas versões, eles competem para ser os primeiros a adivinhar corretamente; Em outros, eles podem descobrir uma estratégia de antemão para cooperar e maximizar a probabilidade de suposições corretas.
Uma variação recebeu alguma nova publicidade como resultado do doutorado de Todd Ebert em 1998. Tese na Universidade da Califórnia, Santa Barbara. É uma questão de estratégia sobre um jogo cooperativo, que tem conexões com a teoria da codificação algébrica.
Três jogadores são informados de que cada um deles receberá um chapéu vermelho ou um chapéu azul. Eles devem levantar as mãos se virem um chapéu vermelho em outro jogador enquanto ficam em círculo de frente para o outro. O primeiro a adivinhar a cor de seu chapéu vence corretamente.
Todos os três jogadores levantam as mãos. Depois que os jogadores se viram por alguns minutos sem adivinhar, um jogador anuncia "vermelho" e vence. Como o vencedor fez isso e qual é a cor dos chapéus de todos?
Solução
Primeiro, se duas pessoas tivessem chapéus azuis, nem a mão de todos teria sido levantada. Em seguida, se o jogador 1 tivesse visto um chapéu azul no jogador 2 e um chapéu vermelho no jogador 3, o jogador 1 saberia imediatamente que seu próprio chapéu deve estar vermelho. Assim, qualquer jogador que vê um chapéu azul pode adivinhar imediatamente. Finalmente, o vencedor percebe que, como ninguém adivinha de uma só vez, não deve haver chapéus azuis, então todo chapéu deve estar vermelho.
No caso em que todos os jogadores precisam adivinhar, mas são livres para escolher quando adivinhar, há uma estratégia cooperativa que permite que todos os jogadores adivinhem corretamente, a menos que todos os chapéus sejam da mesma cor. Cada jogador deve agir da seguinte maneira:
Count the numbers b of blue hats and r of red hats that you see.Wait b seconds or r seconds, whichever is sooner.If nobody has yet spoken, guess that your hat is blue if you can see fewer blue hats than red hats, or red if you can see fewer red hats than blue hats.If you have not yet spoken, guess that your hat is of the opposite colour to that of one of the first people to speak.Suponha que, no total, existem chapéus azuis B e chapéus vermelhos. Existem três casos.
Se b = r, então os jogadores usando chapéus azuis veem os chapéus azuis B -1 e os chapéus vermelhos B, então espere B - 1 segundos, então adivinhe que eles estão usando um chapéu azul. Da mesma forma, os jogadores que usam um chapéu vermelho esperam R -1 segundos antes de adivinhar corretamente que estão usando um chapéu vermelho. Então, todos os jogadores fazem um palpite correto ao mesmo tempo.
Se b
O caso em que r
Variante de dois chapéus
Descrição
Segundo a história, quatro prisioneiros são presos por um crime, mas a prisão está cheia e o carcereiro não tem lugar para colocá -los. Ele finalmente cria a solução de lhes dar um quebra -cabeça, por isso, se eles conseguirem, poderão se libertar, mas se falharem, serão executados.
O carcereiro assenta três dos homens em uma fila. B enfrenta a parede, C rostos B e D rostos C e B. O quarto homem, A, é colocado atrás de uma tela (ou em uma sala separada). O carcereiro dá a todos os quatro chapéus de festa dos quatro homens. Ele explica que existem dois chapéus pretos e dois chapéus brancos, que cada prisioneiro está usando um dos chapéus e que cada um dos prisioneiros vê apenas os chapéus à sua frente, mas nem por si mesmo nem atrás dele. O quarto homem atrás da tela não pode ver ou ser visto por nenhum outro prisioneiro. Nenhuma comunicação entre os prisioneiros é permitida.
Se algum prisioneiro puder descobrir qual é a cor que ele tem em sua própria cabeça com 100% de certeza (sem adivinhar), ele deve anunciá -lo, e todos os quatro prisioneiros se libertam. Se algum prisioneiro sugere uma resposta incorreta, todos os quatro prisioneiros serão executados. O quebra -cabeça é descobrir como os prisioneiros podem escapar.
Solução
Os prisioneiros sabem que existem apenas dois chapéus de cada cor. Portanto, se D observa que B e C têm chapéus da mesma cor, D deduzia que seu próprio chapéu é a cor oposta. No entanto, se B e C tiverem chapéus de cores diferentes, D poderá não dizer nada. A chave é que o prisioneiro C, depois de permitir um intervalo apropriado, e saber o que D faria, pode deduzir que se D não dissesse que os chapéus de B e C devem ser diferentes; Capaz de ver o chapéu de B, ele pode deduzir a cor do seu próprio chapéu.
Em comum com muitos quebra -cabeças desse tipo, a solução depende da suposição de que todos os participantes são totalmente racionais e inteligentes o suficiente para fazer as deduções apropriadas.
Depois de resolver esse quebra -cabeça, algumas dicas sobre a natureza da comunicação podem ser obtidas refletindo se o silêncio significativo do prisioneiro D viola a regra "sem comunicação" (dado que a comunicação é geralmente definida como a "transferência de informação").
Variante de três chapéus
Descrição
Nesta variante, existem 3 prisioneiros e 3 chapéus. Cada prisioneiro recebe um chapéu aleatório, vermelho ou azul. Ao todo, existem três chapéus vermelhos e dois azuis. Cada pessoa pode ver os chapéus de outros dois, mas não seus. Em uma sugestão, cada um deles tem que adivinhar o próprio chapéu ou passar. Eles vencem a liberação se pelo menos uma pessoa adivinhou corretamente e nenhuma adivinhou incorretamente (a passagem não está correta nem incorreta).
Esse quebra -cabeça não tem uma estratégia 100% vencedora, então a pergunta é: qual é a melhor estratégia? Qual estratégia tem a maior probabilidade de ganhar?
Se você pensa nas cores dos chapéus como bits, esse problema tem algumas aplicações importantes na teoria da codificação.
Solução
A solução e a discussão desse quebra-cabeça podem ser encontradas aqui (também uma solução para o quebra-cabeça análogo de 7 chapéus) e outras três variantes estão disponíveis nesta página de quebra-cabeças lógicos (eles são chamados de mestres da lógica i-IV).
Variante de quatro chapéus
Descrição
Em uma variante desse quebra -cabeça, os prisioneiros sabem que existem 2 chapéus pretos e 2 chapéus brancos, e há uma parede entre A e B, mas os prisioneiros B, C&D podem ver quem está na frente deles, ou seja, D vê B, C e a parede, B vê a parede e C vê b & the Wall. (A novamente não pode ser visto e existe apenas para usar um dos chapéus pretos.) Como eles podem deduzir as cores de todas elas sem se comunicar?
Solução
Existem dois casos: no caso trivial, dois dos quatro prisioneiros usam os chapéus pretos. Cada um dos outros dois prisioneiros pode ver que um prisioneiro está usando o chapéu de cor. No caso não trivial, dois dos quatro prisioneiros usam chapéus da mesma cor, enquanto A e C usam os chapéus pretos. , todos os quatro prisioneiros devem ser capazes de deduzir isso, porque D e B não foram capazes de declarar a cor de seu próprio chapéu, A e C devem estar usando os chapéus pretos.
Variante de cinco chapéus
Descrição
Em outra variante, apenas três prisioneiros e cinco chapéus de cores conhecidas (neste exemplo dois pretos e três brancos) estão envolvidos. Os três prisioneiros são condenados a ficar em linha reta de frente para a frente, com uma frente e C na parte de trás. Eles são informados de que haverá dois chapéus pretos e três chapéus brancos. Um chapéu é então colocado na cabeça de cada prisioneiro; Cada prisioneiro só pode ver os chapéus das pessoas à sua frente e não por conta própria. O primeiro prisioneiro capaz de anunciar corretamente a cor de seu chapéu será libertado. Nenhuma comunicação entre os prisioneiros é permitida.
Solução
Suponha que um usa um chapéu preto:
If B wears a black hat as well, C can immediately tell that he is wearing a white hat after looking at the two black hats in front of him.If B wears a white hat, C will be unable to tell the color of his hat (because there is a black and a white). So B can quickly deduce from A's black hat and C's lack of response that he (B) is wearing a white hat.Portanto, se um usa um chapéu preto, haverá uma resposta bastante rápida de B ou C.
Suponha que um usa um chapéu branco:
C does not see two black hats, so he is unable to tell his hat color.B sees only a white hat, so he can't tell anything about his hat.Nesse caso, A, B e C permaneceriam em silêncio por algum tempo, até que um finalmente deduz que ele deve ter um chapéu branco porque C e B permaneceram em silêncio por algum tempo.
Como mencionado, existem três chapéus brancos e dois chapéus pretos no total, e os três prisioneiros sabem disso. Neste enigma, você pode assumir que todos os três prisioneiros são muito inteligentes e muito inteligentes. Se C não conseguia adivinhar a cor de seu próprio chapéu, porque ele viu dois chapéus brancos ou uma de cada cor. Se ele visse dois chapéus pretos, poderia ter deduzido que estava usando um chapéu branco.
Variante de dez chumos
Descrição
Nesta variante, existem 10 prisioneiros e 10 chapéus. Cada prisioneiro recebe um chapéu aleatório, vermelho ou azul, mas o número de cada chapéu de cor não é conhecido pelos prisioneiros. Os prisioneiros estarão alinhados, onde cada um poderá ver os chapéus na frente dele, mas não para trás. Começando com o prisioneiro na parte de trás da linha e avançando, cada um deles deve, por sua vez, dizer apenas uma palavra que deve ser "vermelha" ou "azul". Se a palavra corresponde à cor do chapéu, eles serão lançados, se não, eles serão mortos no local. Um guarda simpático os adverte deste teste uma hora de antemão e diz a eles que eles podem formular um plano em que seguindo as regras declaradas, 9 dos 10 prisioneiros definitivamente sobreviverão e 1 tem uma chance de sobrevivência 50/50. Qual é o plano para atingir a meta?
Solução
Os prisioneiros concordam que, se o primeiro prisioneiro vir um número estranho de chapéus vermelhos, ele dirá "vermelho". Dessa forma, os nove outros prisioneiros conhecerão o próprio chapéu depois que o prisioneiro atrás deles responde.
Variante de dez chapéus sem ouvir
Descrição
Como antes, existem 10 prisioneiros e 10 chapéus. Cada prisioneiro recebe um chapéu aleatório, vermelho ou azul, mas o número de cada chapéu de cor não é conhecido pelos prisioneiros. Os prisioneiros são distribuídos na sala, de modo que possam ver os chapéus dos outros, mas não os deles. Agora, cada um deles deve, simultaneamente, dizer apenas uma palavra que deve ser "vermelha" ou "azul". Se a palavra corresponder à cor do chapéu, eles serão liberados e, se prisioneiros suficientes retomarem sua liberdade, poderão resgatar os outros. Um guarda simpático os adverte deste teste uma hora antes. Se eles puderem formular um plano seguindo as regras declaradas, 5 dos 10 prisioneiros serão definitivamente libertados e poderão resgatar os outros. Qual é o plano para atingir a meta?
Solução
Os prisioneiros se juntam. Em um par (a, b) dos prisioneiros A diz que a cor que ele pode ver na cabeça de B, que diz a cor oposta que ele vê na cabeça de A. Então, se ambos usam chapéus com a mesma cor, A é Lançado (e B não é), se as cores forem diferentes, B é liberado (e A não é). No total, 5 prisioneiros respondem corretamente e 5 não. Isso pressupõe que o par possa comunicar quem é A e quem é B, que pode não ser permitido.
Como alternativa, os prisioneiros constroem dois grupos de 5. Um grupo pressupõe que o número de chapéus vermelhos seja par, o outro pressupõe que haja um número ímpar de chapéus vermelhos. Semelhante à variante com a audição, eles podem deduzir a cor do chapéu dessa suposição. Exatamente um grupo estará certo, então 5 prisioneiros respondem corretamente e 5 não.
Observe que os prisioneiros não conseguem encontrar uma estratégia que garantisse a libertação de mais de 5 prisioneiros. De fato, para um único prisioneiro, existem tantas distribuições de cores de chapéu onde ele diz a resposta correta do que há onde não. Portanto, existem tantas distribuições de cores de chapéu em que 6 ou mais prisioneiros dizem a resposta correta do que há 4 ou menos o fazem.
Variante de chapéu de contagem infinita sem ouvir
Descrição
Nesta variante, um número de prisioneiros contravelmente infinitos, cada um com uma linha de arquivo única desconhecida e designada aleatoriamente. Cada prisioneiro se afasta do início da linha, e cada prisioneiro pode ver todos os chapéus à sua frente, e nenhum dos chapéus para trás. A partir do início da linha, cada prisioneiro deve identificar corretamente a cor do chapéu ou ele é morto no local. Como antes, os prisioneiros têm a chance de se encontrar de antemão, mas, ao contrário de antes, uma vez na fila, nenhum prisioneiro pode ouvir o que os outros prisioneiros dizem. A questão é: existe uma maneira de garantir que apenas muitos prisioneiros sejam mortos?
Solução
Se alguém aceita o axioma da escolha e assume que os prisioneiros têm a capacidade (irrealista) de memorizar uma quantidade incontável de informações e executar cálculos com uma complexidade computacional incontavelmente infinita, a resposta é sim. De fato, mesmo se permitirmos um número incontável de cores diferentes para os chapéus e um número incontável de prisioneiros, o axioma de escolha fornece uma solução que garante que apenas muitos prisioneiros finalmente devem morrer, desde que cada prisioneiro possa ver os chapéus de todos os outros prisioneiro (não apenas aqueles à frente deles em uma linha), ou pelo menos que cada prisioneiro pode ver quase muitos dos outros chapéus. A solução para o estojo de duas cores é a seguinte, e a solução para o caso de cor incouncamente infinita é essencialmente o mesmo:
Os prisioneiros que estão na fila formam uma sequência de 0s e 1s, onde 0 é levado para representar o azul e 1 é levado para representar o vermelho. Antes de serem colocados na linha, os prisioneiros definem a seguinte relação equivalência sobre todas as seqüências possíveis em que podem ser colocadas: duas sequências são equivalentes se forem idênticas após um número finito de entradas. A partir dessa relação de equivalência, os prisioneiros recebem uma coleção de aulas de equivalência. Assumindo o axioma da escolha, existe um conjunto de seqüências representativas - uma de cada classe de equivalência. (Quase todo valor específico é impossível de calcular, mas o axioma da escolha implica que existe algum conjunto de valores; portanto, assumimos que os prisioneiros têm acesso a um oráculo.)
Quando são colocados em sua linha, cada prisioneiro pode ver todos, exceto um número finito de chapéus, e, portanto, pode ver a qual classe de equivalência a sequência real de chapéus pertence. (Isso pressupõe que cada prisioneiro possa realizar um número incontavelmente infinito de comparações para encontrar uma correspondência, com cada comparação de classe exigindo um número contantevelmente infinito de comparações individuais de chapéus). Eles então prosseguem adivinhando o chapéu como se estivessem na sequência representativa da classe de equivalência apropriada. Como a sequência real e a sequência representativa estão na mesma classe de equivalência, suas entradas são as mesmas depois de algum número finito de prisioneiros. Todos os prisioneiros após esses primeiros n prisioneiros são salvos.
Como os prisioneiros não têm informações sobre a cor de seu próprio chapéu e tornariam o mesmo palpite que qualquer cor, cada prisioneiro tem 50% de chance de ser morto. Pode parecer paradoxal que um número infinito de prisioneiros tenha uma chance uniforme de ser morto e, no entanto, é certo que apenas um número finito é morto. A solução para esse paradoxo está no fato de que a função empregada para determinar o palpite de cada prisioneiro não é uma função mensurável.
Para ver isso, considere o caso de zero prisioneiros sendo mortos. Isso acontece se e somente se a sequência real for uma das seqüências representativas selecionadas. Se as seqüências de 0s e 1s forem vistas como representações binárias de um número real entre 0 e 1, as seqüências representativas formam um conjunto não mensurável. (Este conjunto é semelhante a um conjunto vitali, a única diferença é que as classes de equivalência são formadas em relação aos números com representações binárias finitas, em vez de todos os números racionais.) Portanto, nenhuma probabilidade pode ser atribuída ao evento de zero prisioneiros sendo mortos. O argumento é semelhante para outros números finitos de prisioneiros sendo mortos, correspondendo a um número finito de variações de cada representante.
Problema de chapéu infinito contável com a audição
Descrição
Essa variante é a mesma que a última, exceto que os prisioneiros podem ouvir as cores chamadas por outros prisioneiros. A questão é: qual é a estratégia ideal para os prisioneiros, de modo que o menor delas morra no pior caso?
Solução
Acontece que, se alguém permitir que os prisioneiros ouçam as cores chamadas pelos outros prisioneiros, é possível garantir a vida de todo prisioneiro, exceto o primeiro, que morre com uma probabilidade de 50%.
Para fazer isso, definimos a mesma relação de equivalência como acima e novamente, selecionamos uma sequência representativa de cada classe de equivalência. Agora, rotulamos todas as seqüências de cada classe com 0 ou A 1. Primeiro, rotulamos a sequência representativa com um 0. Então, rotulamos qualquer sequência que seja diferente da sequência representativa em um número par de lugares com 0, e qualquer sequência que difere da sequência representativa em um número ímpar de lugares com um 1. dessa maneira, rotulamos todas tem rótulos opostos.
Agora, quando o diretor pede à primeira pessoa que diga uma cor, ou em nossa nova interpretação, um 0 ou 1, ele simplesmente chama o rótulo da sequência que vê. Dada essas informações, todos depois dele podem determinar exatamente qual é a cor do seu próprio chapéu. A segunda pessoa vê todos, exceto o primeiro dígito da sequência que a primeira pessoa vê. Assim, até onde ele sabe, existem duas seqüências possíveis que a primeira pessoa poderia estar rotulando: uma começando com um 0 e uma começando com um 1. Devido ao nosso esquema de rotulagem, essas duas seqüências receberiam rótulos opostos, com base em que baseado Sobre o que a primeira pessoa diz, a segunda pessoa pode determinar qual das duas cordas possíveis que a primeira pessoa viu e, portanto, ele pode determinar a cor do seu próprio chapéu. Da mesma forma, toda pessoa posterior da linha conhece todos os dígitos da sequência, exceto a que corresponde à cor do seu próprio chapéu. Ele conhece aqueles antes dele porque foram chamados, e os que ele atrás dele, porque ele pode vê -los. Com essas informações, ele pode usar o rótulo chamado pela primeira pessoa para determinar a cor do seu próprio chapéu. Assim, todos, exceto a primeira pessoa, sempre adivinham corretamente.
Versão de Ebert e códigos de Hamming
Descrição
A versão do problema de Ebert afirma que todos os jogadores que adivinham devem adivinhar no mesmo tempo predeterminado, mas que nem todos os jogadores são obrigados a adivinhar. Agora, nem todos os jogadores podem adivinhar corretamente, então os jogadores vencem se pelo menos um jogador adivinhar e todos os que adivinham o fazem corretamente. Como os jogadores podem maximizar sua chance de ganhar?
Solução
Uma estratégia para resolver esta versão do problema do HAT emprega códigos de hamming, que são comumente usados para detectar e corrigir erros na transmissão de dados. A probabilidade de vencer será muito superior a 50%, dependendo do número de jogadores na configuração do quebra -cabeça: por exemplo, uma probabilidade de vitória de 87,5% para 7 jogadores.
Estratégias semelhantes podem ser aplicadas aos tamanhos da equipe de n = 2k-1 e atingir uma taxa de vitória (2k-1)/2k. Assim, a estratégia de código de hamming gera maiores taxas de vitória para valores maiores de N.
Nesta versão do problema, qualquer palpite individual tem 50% de chance de estar certo. No entanto, a abordagem do código de hamming funciona concentrando palpites errados juntos em certas distribuições de chapéus. Para alguns casos, todos os jogadores adivinharão incorretamente; Considerando que, para os outros casos, apenas um jogador adivinhará, mas corretamente. Embora metade de todas as suposições ainda esteja incorreta, isso resulta nos jogadores vencendo mais de 50% das vezes.
Um exemplo simples desse tipo de solução com três jogadores é instrutivo. Com três jogadores, existem oito possibilidades; Em dois deles, todos os jogadores têm o mesmo chapéu de cor e, nos outros seis, dois jogadores têm uma cor e o outro jogador tem a outra cor.
Os jogadores podem garantir que vencem nos últimos casos (75% das vezes) com a seguinte estratégia:
Any player who observes two hats of two different colours remains silent.Any player who observes two hats of the same colour guesses the opposite colour.Nos dois casos em que todos os três jogadores têm a mesma cor, todos eles adivinharão incorretamente. Mas nos outros seis casos, apenas um jogador adivinhará, e corretamente, que seu chapéu é o oposto de seus colegas jogadores.
Casas de Sneetchville
Descrição
Sneetches são criaturas da famosa história do Dr. Seuss "The Sneetches". Existem dois tipos de sneetches, estrelado e com barriga simples. Todos os sneetches devem passar em um teste lógico para morar em Sneetchville, que tem um número limitado de casas e uma lei imobiliária estrita de que cada casa deve conter não mais do que uma canela de barriga estrelada e uma caneca simples. Nenhum Sneetch é capaz de ver sua própria barriga, mas ainda pode ver todas as barrigas de outras canecas. Para evitar mais conflitos entre os sneetches, há uma lei que proíbe as canecas de discutir suas barrigas (veja também não pergunte, não conte). Cada Sneetch não pode pular uma casa até que tenha certeza de que não pode se mudar. Se um Sneetch quebrar a lei, ela é executada. Como os sneetches escolhem suas casas?
Solução
Como todos os sneetches estão potencialmente em risco, uma solução é para todas as canecas se encontrarem na rua; O modelo indica casas, portanto, uma estrada, rua ou perto. Lá, eles concordam em avançar em direção a sneetches que parecem parecidos e longe de sneetches que parecem diferentes; Isso evita a necessidade de se comunicar especificamente em relação às características físicas, isto é, estado da barriga. O movimento Sneetch começa com o movimento browniano, mas como na lógica do problema das crianças lamacentas, isso se transforma em aglomeração, por exemplo, um sneetch movendo -se em direção a duas canecas semelhantes sendo aceitas ou rejeitadas por eles, ou vice -versa, e eventualmente um único espaço de estado de dois Resultados dos grupos, os estrelados e lisos heliados. Um sneetch do primeiro grupo vai primeiro para cada casa, depois um sneetch do segundo grupo vai para cada casa.