Cem pessoas, cem caixas, cinquenta tentativas por participante e uma condição implacável: todos devem encontrar seu próprio número. Escolhas aleatórias quase garantem o fracasso. Mas uma regra baseada em ciclos de permutações eleva a chance de sucesso coletivo a cerca de 31,18%.
Imagine cem prisioneiros que recebem uma oportunidade de liberdade. Cada pessoa possui um número, de 1 a 100. Na sala seguinte existem cem caixas numeradas, cada uma contendo exatamente um dos cem números, distribuídos aleatoriamente e sem repetição.
Os participantes entram um de cada vez. Cada um pode abrir, no máximo, cinquenta caixas. Depois de sua saída, elas são fechadas, sem alteração dos conteúdos. Nenhuma comunicação é permitida durante o desafio. Se todos encontrarem seus próprios números, o grupo será libertado; se um único participante falhar, todos fracassam.
Antes de começar, porém, eles podem combinar uma estratégia. Qual seria a melhor escolha?
Por que a busca aleatória praticamente não funciona?
Se cada participante selecionar cinquenta caixas ao acaso, sem repetição, terá 50% de chance de encontrar seu número. Afinal, seu papel está em apenas uma das cem caixas.
Se todos escolherem conjuntos de caixas independentemente, a probabilidade de sucesso de cada pessoa será multiplicada pelas probabilidades das demais:
É aproximadamente uma chance em 1,27 × 1030. A probabilidade não é zero, mas é tão pequena que a libertação coletiva seria praticamente impossível. O desafio, portanto, não é melhorar a probabilidade individual. É fazer com que os resultados individuais deixem de ser independentes.
Uma estratégia que parece não fazer sentido
Considere o prisioneiro número 17. Em vez de escolher qualquer caixa, ele abre a caixa 17. Imagine que ela contenha o papel 42. Ele não encontrou seu número, mas agora abre a caixa 42. Se ela contiver o número 8, passa à caixa 8; se ali encontrar o 63, abre a caixa 63.
A regra é sempre a mesma: abrir a caixa cujo número apareceu no papel anterior. O participante para quando encontra seu próprio número ou atinge o limite de cinquenta caixas.
Todos os prisioneiros seguem esse procedimento, cada qual começando pela caixa do próprio número. Parece apenas uma maneira peculiar de procurar, mas as caixas escondem uma estrutura matemática.
O que as caixas têm a ver com permutações?
Uma permutação é uma reorganização dos elementos de um conjunto. Como cada número de 1 a 100 aparece exatamente uma vez nas caixas, sua distribuição define uma permutação:
O valor π(i) representa o papel encontrado na caixa i. Como a função é bijetora, seguir repetidamente o número encontrado produz um caminho que retorna à caixa inicial. Esse caminho recebe o nome de ciclo.
Uma permutação pode ser decomposta em ciclos disjuntos: cada número pertence a exatamente um ciclo. A estratégia aproveita precisamente essa decomposição.
Um exemplo com apenas oito caixas
Considere uma versão reduzida com oito participantes e limite de quatro caixas abertas por pessoa. Suponha que a distribuição corresponda aos seguintes ciclos:
O participante 1 abre a caixa 1, depois a 4 e, finalmente, a 2, na qual encontra o papel 1. Precisou de três tentativas. O participante 6 percorre as caixas 6, 8, 5 e 3, encontrando seu próprio número na quarta tentativa. O participante 7 o encontra imediatamente.
Os demais seguem os mesmos ciclos a partir de pontos diferentes. Como todos os ciclos possuem comprimento de no máximo quatro, todos encontram seus números.
Mas, se algum ciclo tivesse cinco elementos, os participantes desse ciclo precisariam de cinco aberturas para retornar ao próprio número e fracassariam. É esse o ponto-chave.
A verdadeira condição de sucesso
No desafio original, cada pessoa pode abrir cinquenta caixas. Portanto, o grupo inteiro terá sucesso se, e somente se, a permutação aleatória não contiver nenhum ciclo de comprimento maior que cinquenta.
Não precisamos conhecer previamente a posição de número algum: a estrutura da permutação determina se todos conseguirão. E como os números estão distribuídos uniformemente entre as caixas, podemos calcular exatamente a probabilidade dessa estrutura ocorrer.
De onde vêm os 31,18%?
Uma permutação de cem elementos pode conter um ciclo de comprimento 51, 52 ou até 100. Mas não pode conter dois ciclos com mais de cinquenta elementos, porque, juntos, eles exigiriam mais de cem números.
Esse fato simplifica a contagem. Para qualquer comprimento k maior que cinquenta, a probabilidade de uma permutação uniforme possuir um ciclo de comprimento k é 1/k.
Podemos demonstrar isso escolhendo os k elementos do ciclo, organizando-os circularmente em (k − 1)! maneiras e permutando os demais cem menos k números. A quantidade de permutações favoráveis será:
Como existem 100! permutações possíveis, a probabilidade procurada é (100!/k)/100! = 1/k.
Os eventos de existir um ciclo de comprimento 51, 52, …, 100 são mutuamente exclusivos. Logo, podemos somar suas probabilidades para calcular o fracasso coletivo:
A probabilidade de sucesso é o complemento:
Ou seja: uma chance próxima de uma em três, em vez de uma probabilidade praticamente nula. E isso sem comunicação, sem trocar os papéis de lugar e sem abrir mais caixas.
Cada pessoa continua tendo 50% de chance
Esse é o resultado mais contraintuitivo. A estratégia dos ciclos não aumenta a probabilidade individual de sucesso: para qualquer prisioneiro, o ciclo em que ele está tem probabilidade de ser curto o suficiente de 50%.
A melhora vem da correlação. Uma permutação em que todos os ciclos são curtos favorece simultaneamente o grupo inteiro. Uma permutação com ciclo longo faz vários participantes fracassarem juntos. A estratégia concentra os resultados ruins em certas configurações, ampliando a fração das configurações em que todos conseguem.
É por isso que o problema se distingue do problema das três portas: ambos exigem compreender a estrutura probabilística, mas aqui o objetivo é coordenar sucessos individuais.
A estratégia é ótima? E se o grupo crescer?
Em 2006, Eugene Curtin e Max Warshauer publicaram uma demonstração de que a estratégia dos ciclos é ótima sob as regras originais do desafio. Não existe outra estratégia previamente combinada que produza maior probabilidade de libertação coletiva, supondo distribuição uniforme dos papéis.
O resultado permanece surpreendente quando o tamanho do grupo cresce. Se tivermos um número par de participantes e cada pessoa puder abrir metade das caixas, a probabilidade tende ao limite:
Não é a chance exata para cem prisioneiros; é o valor para grupos cada vez maiores. Mesmo assim, mostra que a estratégia mantém uma chance coletiva considerável em escala crescente.
Sorte, informação e estrutura
Os papéis continuam aleatórios. Os prisioneiros continuam sem conhecer a distribuição antecipadamente. A Matemática não elimina a incerteza: ela permite organizar as decisões de acordo com uma estrutura que o acaso preserva.
Essa diferença lembra a solução das doze moedas em três pesagens, mas ali a informação é suficiente para garantir o resultado; aqui somente maximizamos a chance de sucesso. Também é distinta do enigma das crianças que descobrem um segredo pelo silêncio, no qual a informação compartilhada desempenha outro papel.
Uma decisão inteligente não precisa tornar cada indivíduo mais sortudo. Às vezes, basta que as escolhas individuais tenham uma relação matemática adequada.
Se cem pessoas conseguem transformar uma chance quase impossível em 31% sem receber oportunidades extras, quantas decisões que atribuímos à sorte poderiam melhorar se compreendêssemos a estrutura do problema?
Livro recomendado
O Andar do Bêbado, de Leonard Mlodinow (Zahar, edição brasileira; ISBN 9788537818107), discute acaso, probabilidade e os erros de intuição que distorcem nossas decisões. Consultar na Amazon Brasil (link afiliado de busca pela edição; preço e estoque sujeitos a alteração).
Referências
Eugene Curtin e Max Warshauer, The Locker Puzzle, The Mathematical Intelligencer, 28(1), 2006, p. 28–31; Wolfram MathWorld — 100 Prisoners Problem. A matemática das permutações e a probabilidade dos ciclos são apresentadas no corpo do texto.
Guilherme Augusto Pianezzer
Professor de Matemática, autor e criador de conteúdo. Os textos deste site são produzidos com foco em rigor conceitual, clareza didática e conexão entre Matemática, Economia, Ciência e Educação.
Deixe um comentário