Encontrar o seu próprio número em uma caixa

https://stackoverflow.com/questions/34345

09-06-2019
|

Pergunta

100 (ou alguns mesmo número 2N :-) ) presos em uma sala A.Eles são numerados de 1 a 100.

Um por um, a partir de o prisioneiro #1 para o prisioneiro #100, na ordem), que vai ser deixado em uma sala B, na qual 100 caixas (numerados de 1 a 100) esperam.Dentro do (fechado) caixas são números de 1 a 100 (os números dentro das caixas são aleatoriamente para a troca!).

Uma vez dentro da sala B, cada prisioneiro fica para abrir 50 caixas (ele escolhe qual ele abre).Se ele encontra o número que foi atribuído a ele em uma dessas 50 caixas, o prisioneiro começa a andar em um quarto C e todas as caixas são fechadas novamente antes de entra na sala B da sala A.Caso contrário, todos os prisioneiros (em salas A, B e C) é morto.

Antes de entrar em sala B, os presos podem chegar a acordo sobre uma estratégia (algoritmo).Não há nenhuma maneira de se comunicar entre os quartos (e nenhuma mensagem pode ser deixado na sala B!).

Existe um algoritmo que maximiza a probabilidade de que todos os prisioneiros sobreviver?Que probabilidade é que o algoritmo de alcançar?

Notas:

Fazer as coisas aleatoriamente (o que você chama de "nenhuma estratégia de') de fato dá uma probabilidade de 1/2 para cada prisioneiro, mas, em seguida, a probabilidade de todos eles sobreviver 1/2^100 (o que é muito baixo).Pode-se fazer muito melhor!
Os prisioneiros não são permitidos para reordenar as caixas!
Todos os prisioneiros são mortos a primeira vez que um prisioneiro não consegue encontrar seu número. E nenhuma comunicação é possível.
Dica:pode-se economizar mais de 30 prisioneiros em média, que é muito mais do que (50/100) * (50/99) * [...] * 1

Solução

Este quebra-cabeça está explicado na http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml e a pessoa que faz um trabalho muito melhor de explicar o problema.

"Todos os prisioneiros são mortos" declaração é errado.O "você pode economizar mais de 30 anos, em média" também está errada, o artigo diz-se que 30% do tempo você pode salvar 100% dos prisioneiros.

Outras dicas

Eu acho um low tech solução para este tipo de problema é sempre o melhor caminho a percorrer.

primeiro vamos fazer algumas suposições sobre a situação

Os prisioneiros não são todos os programadores ou matemáticos
Eles não querem morrer
Os guardas estão bem armados

Assim, com um 0.005% de chance de que eles vão ver amanhã, há uma forma muito simples e de baixa tecnologia solução para este problema. RIOT

tudo sobre perdas v potencial de ganho, as chances são de que os prisioneiros longe número de guardas, e usando o outro como escudos humanos, como eles estão todos mortos de qualquer maneira, se eles não, eles podem aumentar as chances de eles sobre o poder de uma guarda, uma vez que eles têm a sua arma há chance sobe, ajudando-os sobre o poder mais guardas para obter mais poder de fogo para aumentar ainda mais lá taxa de sobrevivência.uma vez que os guardas perceber o que está acontecendo, eles provavelmente vão correr para as montanhas e bloquear a prisão, isso vai dar o que media um heads-up, e depois é uma questão de direitos humanos.

Implementar um algoritmo de ordenação e de classificação as caixas de acordo com os números dentro delas.

Primeiro prisioneiro tipo 50 caixas, e o segundo prisioneiro classifica os outros 50 e funde-se com a primeira.(Note que o segundo prisioneiro pode adivinhar os valores dentro dos primeiros 50 caixas)

Após a 2ª prisioneiro, todas as caixas serão em ordem alfabética !!!

Todo mundo pode abrir as caixas com seus números facilmente.

Eu não sei se isso é permitido, mas a melhor aproximação que posso encontrar é:

EDITAR:Ok, eu acho que isso faz de ti.É claro que eu estou tratando isso como uma computação problema, eu não acho que qualquer prisioneira será capaz de realizar isto, ainda é muito para a frente, se você não.

Encontre os 50 primeiros números primos, vamos asume nós mantê-los em uma matriz chamada primos.

O primeiro prissioner entra na sala B e abre a primeira caixa e encontra o número m.
Aguarde primes[1]^m (que seria 3^m)
Abrir caixa 2 e leia o número --> n
Aguarde (primes[2]^n - 1) * primes[1]^m, que seria (5^n - 1) * 3^m e o tempo total em que ele estava esperando seria 3^n * 5^n

Repita.Após a primeira prisioneira do tempo total para ele seria:3^m * 5^n * 7^p ...= X

Antes da segunda prisioneira entra na sala factorizar X.Você sabe de antemão os números primos que foram utilizados para a fatoração é trivial.Fazendo isso, você obter m, n, p, etc.) para o segundo prisioneira conhece cada caixa/número de combinação anterior prisioneira utilizado.

A probabilidade de a primeira a ficar todo mundo morto é de 1/2, a segunda terá 50 / (100 - n) n (sendo n o número de tentativas de o primeiro) a terceira terá 50 / (100 - n - m) (se n + m = 100, então todas as posições são conhecidas) e assim por diante.

Obviamente, o próximo prissioner deve ignorar o já conhecido caixas (exceto para a última escolha se a caixa que contém o seu número já é conhecido)

Eu não sei o que é o exato possibilidade de ti dependes em quantas escolhas que eles têm para fazer, mas eu diria que é bastante elevado.

EDITAR:Relendo, se o prissioner não tem que parar quando ele obtém o seu número, em seguida, a probabilidade para todo o grupo está muito melhorado, exatamente 50%.

EDIT2:@OysterD vê-lo desta forma.Se a primeira prisioneira pode abrir 50 caixas, em seguida, a segunda saber se o seu número é em qualquer de caixas.Se for, então ele pode abrir outros 49 (e por isso, aprender a caixa/número comination de 100 caixas) e, finalmente, abrir o seu.Portanto, se a primeira prissioner succeds, em seguida, todos succeds.Lembre-se de que cada prisioneira fornece uma maneira para os outros para saber exatamente o/caixas de combinação para cada caixa que ele abre.

Talvez eu não esteja lendo isso direito, mas a questão parece ser mal construído ou falta de informação.

Se ele descobre o número que foi atribuído a ele em uma dessas 50 caixas, o prisioneiro começa a andar em um quarto C e todas as caixas são fechadas novamente antes da próxima anda em sala B sala A.Caso contrário, todas as prisioneiros (em salas A, B e C) receber o mortos.

A última frase não significa que todos os prisioneiros são mortos a primeira vez que um prisioneiro não conseguir localizar o seu número?Se não, o que acontece com os prisioneiros que não encontrar o seu número?

Se nenhuma comunicação é possível, e sempre que um prisioneiro entra na sala B é sempre de um modo idêntico estado, não existe a possibilidade de uma estratégia.

Os prisioneiros pudessem dizer antes de deixar espaço a Um número de caixa que vai abrir.Mas, sem posterior prisioneiros saber se eles foram bem sucedidos ou não (supondo que a falha de um não falha para todos) quando o próximo prisioneiro entra na sala B que ainda têm as mesmas probabilidades de escolher o seu número como o antigo prisioneiro (sempre 1:100).

Se o fracasso de um é o fracasso de todos e, em seguida, sabendo que a caixa anterior os prisioneiros aberto, e por força do fato de que eles não foram todos mortos, a cada uma das sucessivas prisioneiro poderia reduzir as probabilidades de escolher o errado caixa por caixa.i.e.1:100 para o primeiro prisioneiro, 1:99 para a segunda, até a 1:1 para a última.

Os prisioneiros poderiam concordar que o prisioneiro 1 abra caixas de 1-50.

Se eles são todos ainda vivos, eles concordam que a próxima prisioneiro abre caixas 2-51.(o 2 é arbitrário, mas simples para lembrar esta regra) Suas chances de sobreviver dado que sobreviveu P1 agora são 50/99.Deseja eliminar a abertura de uma caixa quando você sabe que o cara encontrou a sua.

Eu não sei se é o ideal, mas é muito melhor do que o acaso.

A probabilidade de sobreviver do que parece

50/100 * 50/99 * 50/98 *. . .50/51 * 1

Acho que nenhuma comunicação é possível, a melhor estratégia envolveria

a distribuição de probabilidade de cada prisioneiros tão uniformemente quanto possível

Estou no caminho certo ou não?

Informações disponíveis para cada prisioneiro:

O número de survivied prisioneiros, por isso, se você tem um eficiente caixa de picking sistema que utiliza a ordem de qualquer prisioneiro entra na sala B, então uma estratégia é definitivamente possível

Que caixas anterior prisioneiros escolhidos.É claro, nenhuma comunicação é possível durante a executar e que não seria possível se lembrar de qualquer 100s caixa de colheita de permutação. Mas você poderia usar esta informação para calcular em um sistema de antes de a execução é iniciada.

A minha opinião:

Desenhar uma tabela de números com 2 colunas, a primeira coluna contém o número da caixa (caixa de #1 para caixa de#100).Cada prisioneiro, em seguida, começa a pegar 50 caixas e qualquer caixa de eles pegam, eles devem colocar 1 ponto na linha correspondente na segunda coluna.

Todos os presos são, porém, necessários para nunca escolher qualquer caixa duas vezes.E nenhuma caixa pode ser marcada mais de 50.Alguns presos podem ter menos opções do que os outros, pois de alguma caixa pode ficar cheio até 50 marcas de primeira.

Quando um prisioneiro, mudou-se para o quarto de B ele/ela abre qualquer caixas que ele tem marcado em.

Se todos os prisioneiros são mortos quando alguém não consegue encontrar o seu número, em seguida, você salvar 100 ou 0.Não há nenhuma maneira de salvar a 30 pessoas.

O mesmo conceito.

Aonther tomar:

Anote uma lista dos 100 primeiros números binários que tem cinqüenta 1s e cinqüenta 0s.

Ordenar do menor para o maior.

Prisioneiro #1 é o primeiro número, prisioneiro #2 fica com a segunda, prisioneiro #3 obtém o terceiro e assim por diante...

Cada prisioneiro relembra a sua/seu número binário.

Quando qualquer prisioneiro é movido para a sala B, ele/ela, em seguida, combinar os dígitos binários do número lembrou-se com cada uma das caixa, o bit mais alto é comparado com o caixa mais à esquerda, o próximo bit mais alto é comparado com o segundo mais à esquerda da caixa de ...o bit mais baixo é comparado com o caixa mais à direita.

Ele/ela abre tudo caixas de correspondência com 1 e deixar fechadas as caixas de correspondência com 0.

Este seria minimiza a probabilidade porque os primeiros prisioneiros terá dígitos que são diferentes de prisioneiros e prisioneiros, que tem o número juntos iria ficar dígitos juntos.Isso não garante a sobrevivência, mas se os primeiros prisioneiros fazer sobreviver, as chances são de o, mais tarde, os presos teriam maior probabilidade de sobreviver bem.

Eu não pensei que os números exatos e fundamentação embora, mas esta é uma solução rápida que eu posso pensar no momento.

Não há qualquer limite de tempo em questão, então eu sugiro que os presos devem decidir tomar 1 hora por caixa e abri-los na ordem apresentada.Se o segundo prisioneiro é permitido dentro da sala, depois de 2 horas, em seguida, ele sabe que o primeiro prisioneiro encontrado o seu próprio número de caixa 2.Portanto, ele sabe para ignorar a caixa 2 em sua seqüência e abre caixas 1, 3, 4...51 Primeiros prisioneiros chances de perder são 50/100 Dar o primeiro prisioneiro sobreviveu, em seguida, a segunda prisioneiros chance de ganhar são 50/99 Assim, a resposta parece ser ((50 ^51)*49!)/100!que de acordo com o google faz 2.89*10^-9 o que é muito nil Assim, mesmo se os prisioneiros sabiam que as caixas anteriormente sortudos encontraram o seu número não haveria esperança

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow