Variação dos nomes de 100 prisioneiros nas caixas

Question

100 nomes de prisioneiros em caixas

O seguinte quebra-cabeça é uma variação do quebra-cabeça acima.

Nomes em caixas

• Os nomes de 4 prisioneiros são colocados em 4 caixas de madeira, um nome por caixa, e as caixas são alinhadas em uma mesa em uma sala. As caixas são numeradas 1,2,3 e 4.

• Os nomes são colocados aleatoriamente. Portanto, é igualmente provável que a caixa 1 contenha o nome de qualquer um dos 4 prisioneiros. O mesmo é o caso para as outras caixas.

• Um por um, os prisioneiros são conduzidos para a sala; cada um pode olhar no máximo 2 caixas, mas deve deixar a sala exatamente como a encontrou e não é permitida nenhuma comunicação posterior com os outros.

• Cada prisioneiro, antes de entrar na sala, precisa dizer quais são as 2 caixas que irá abrir. Eles podem então abrir apenas essas 2 caixas.

• Os prisioneiros têm uma chance de traçar sua estratégia com antecedência, e eles vão precisar disso, porque a menos que cada prisioneiro encontre seu próprio nome, todos serão posteriormente executados.

• Que estratégia eles podem usar para maximizar sua sobrevivência?

Answer 1

Eu acho que a resposta é

Os primeiros dois prisioneiros escolhem as duas primeiras caixas e os dois últimos prisioneiros escolhem as duas últimas caixas. A chance de sobrevivência é$1/6 \approx 16.7\%$.

Raciocínio:

Vamos imaginar um grafo de quatro nós e quatro arestas, onde cada nó representa uma caixa e cada aresta conecta as duas caixas escolhidas por um prisioneiro. Então, haverá quatro nós e quatro arestas, e uma aresta não pode ser um loop automático.

Dado tal gráfico, observe que um ciclo de qualquer tamanho no gráfico permitirá duas possibilidades. Por exemplo, se três prisioneiros A, B, C escolherem as casas 1-2, 2-3, 3-1 respectivamente, haverá dois casos em que todos os três encontrarão seus próprios nomes: ABC e CAB.

Além disso, se esse ciclo tiver quaisquer ramificações, eles não aumentam os casos gerais de sobrevivência: além do último exemplo, se D escolher 1-4, D está essencialmente abrindo mão da chance de ver seu nome na caixa 1 (uma vez que um dos ABC nunca encontrará seu nome de outra forma).

Além disso, se um componente conectado tiver mais arestas do que nós (por exemplo, D escolhe 1-2 em vez), a chance de sobrevivência cai para zero, uma vez que eles não têm caixas distintas suficientes para encontrar todos os seus nomes.

Portanto, para maximizar a chance de sobrevivência, os prisioneiros precisam maximizar o número de ciclos disjuntos no gráfico, o que dá dois ciclos de dois nós cada. Então eles vão sobreviver em quatro casos de$4!=24$ casos totais, dando $1/6$ chance de sobrevivência.