Reza a lenda que há um desafio a atazanar a paciência de matemáticos (e mais recentemente de informáticos) há pelo menos dois milhares de anos. Tudo terá começado na mente de Flávio Josefo, um historiador judeu que terá inventado um problema intrincado nos tempos do Cerco Romano de Yodfaf, que no ano de 67 resultou no bloqueio e saque da cidade por tropas romanas lideradas por Vespasiano durante 47 dias.

Vivia-se então a primeira guerra judaico-romana e os judeus sabiam que estavam em desvantagem perante um exército de romanos sedentos de riqueza. O futuro de Yodfaf parecia evidente para todos: Vespasiano iria roubar todas as propriedades, matar a maior parte dos habitantes e escravizar os sobreviventes.

Flávio Josefo relatou toda a história depois de se ter tornado romano e ter acompanhado as tropas de Tito, filho de Vespasiano, durante a destruição de Jerusalém. Nos seus documentos, alguns dos quais se tornaram em importantes fontes de informação para conhecer o judaísmo nos inícios de uma nova era, surgiu o dito problema.

Conta-se que Flávio Josefo estava sentado com quarenta soldados judeus. Cientes da morte iminente, decidiram fazer um pacto fatal: cada um iria esfaquear a pessoa à sua esquerda. Os assassinatos consentidos teriam de acontecer no sentido dos ponteiros do relógio até que sobrasse apenas uma pessoa viva. A pergunta que Flávio Josefo terá colocado foi:

“Onde é que me devo sentar para garantir que sou o único sobrevivente?”.

Que a morte pode ser um assunto delicado, todos nós sabemos por natureza. Mas esta pergunta tem deixado um rasto de matemáticos frustrados e informáticos desanimados. Alguns deles conseguiram chegar a uma resposta, embora tenham recorrido a equações inatingíveis aos comuns dos mortais – com aqueles símbolos e operações que só eles sabem o significado. Mas não tema mais: houve um matemático da Universidade de Wisconsin-Madison, Daniel Erman, que conseguiu explicar tudo de forma muito mais simples. E partilhou as suas explicações no YouTube, através do canal Numberphile. E agora o mundo promete ser um lugar muito mais pacífico.

Vamos então ao que interessa. Imaginemos um grupo mais pequeno, com sete soldados, e cada um dos participantes no pacto recebe um número entre 1 e 7 no sentido dos ponteiros do relógio. A pessoa número um vai matar a pessoa número dois. Depois a número três vai matar a número quatro e a pessoa número cinco mata a número seis. Aqui é que as coisas complicam: como não há um número oito, a pessoa número sete tem de matar a pessoa número um, porque esta é a que se encontra à sua esquerda. Do mesmo modo, a pessoa número três tem de matar a pessoa número cinco, porque está à sua esquerda. Sobram então duas pessoas vivas: a número sete e a número três. A próxima pessoa obrigada a matar é a sete, portanto terá de assassinar a número três. E assim descobrimos que o sobrevivente será o soldado número sete, que inicialmente estava sentado à direita da primeira pessoa a matar.

Parece simples assim, mas a lenda diz que havia 41 pessoas no corredor da morte e que Flávio Josefo queria descobrir onde se sentar para sobreviver. Os matemáticos colocaram o problema da seguinte maneira: se houver “n” pessoas (sendo “n” um número natural – ou seja 1, 2, 3 e por aí adiante), qual é o número do lugar do sobrevivente se as mortes acontecerem no sentido dos ponteiros do relógio? Há uma maneira de saber: tentar encontrar o padrão. Como? A sugestão do matemático Daniel Erman é que tomemos vários valores para “n” de forma a descobrir qual é, para cada um deles, o lugar sobrevivente – que vamos chamar de S(n). Para n=7 – ou seja, para um conjunto de 7 soldados -, sabemos que S(n)= 7 – ou seja, que o lugar do sobrevivente é 7.

Repetindo o esquema acima percebemos que, para um conjunto de 5 soldados (n=5) por exemplo, o lugar sobrevivente é 3 – porque o número 1 mata o número 2, o número 3 mata o número 4, o número 5 mata o número 2 e assim sobra quem se senta no lugar 3. Vamos tentar com n=6: o número 1 mata o número 2, o número 3 para o número 4, o número 5 mata o número 6, o número 1 mata o número 3 e sobra assim o número 5 – portanto para um conjunto de seis soldados – n=6 – o lugar sobrevivente é 5 – S(n)=5. Na tabela aqui em baixo pode consultar os resultados para os números de 1 até 12.

Há uma conclusão que podemos tirar de imediato: os sobreviventes estão sempre sentados em lugares ímpares. E isso percebe-se porque, como o primeiro a matar é sempre o número 1, os soldados a serem mortos na primeira ronda são sempre os que estão sentados em lugares pares.

Muito bem, próximo passo: há mais algum padrão que possamos identificar? Vamos pensar no caso de os soldados serem 13: qual acha que é o lugar vencedor? Se apostou no número 1, bom raciocínio… mas está errado. Entende-se a lógica: olhando para os resultados entre 1 e 12 parece que a certa altura o número do lugar sobrevivente se renova, juntando em cada volta um novo número ímpar. Mas basta fazermos os cálculos à mão, para entender que o lugar sobrevivente para um conjunto de 13 soldados é 11 porque o número 1 mata o número 2, o número 3 mata o número 4, o número 5 mata o número 6, o número 7 mata o número 8, o número 9 mata o número 10, o número 11 mata o número 12, o número 13 mata o número 1, o número 3 mata o número 5, o número 7 mata o número 9, o número 11 mata o número 13, o número 3 mata o número 7 e o número 11 mata o número 3. Um raciocínio semelhante resulta em saber que, para 14 soldados, o lugar sobrevivente é 13.

Então, outro padrão encontrado: sempre que o número do lugar sobrevivente é 1, o ciclo renova-se e começa uma contagem de dois em dois ao longo dos números ímpares até que, a certa altura, um determinado número de soldados tenha, como lugar sobrevivente correspondente, outra vez o número 1. Então, o que têm em comum os números de soldados com número de lugar sobrevivente igual a 1 – S(n) = 1? Olhe para as tabelas lá em cima: os números com lugar sobrevivente igual a 1 são os números dois, quatro, oito e dezasseis. O que estes números têm em comum é que são todos… potências do número 2! O que este problema prova é que se o número de soldados for uma potência de 2, então o número do lugar sobrevivente é sempre o 1.

E há uma forma simples de justificar isto. Vamos fazer a primeira ronda de assassinatos para um número de soldados igual a 16 (n=16). Começando no número 1 e seguindo pelo sentido do relógio, o que começamos por fazer é remover todos os números pares, tal como tínhamos já entendido. O que obtemos ao fim da primeira volta de assassinatos é um número de soldados vivos igual a 8 (n=8), com o soldado 1 a ser o próximo a matar. Então agora vamos numerar os sobreviventes de novo entre 1 e 8. Tal como até agora, começando no soldado 1, eliminamos de novo todos os soldados com número par. Sobram então 4 soldados vivos, metade dos que tinham sobrevivido há pouco, e volta a ser a vez do soldado número 1 para matar. Numeramos os sobreviventes entre 1 e 4 . Depois de mais uma volta de assassinatos, sobram agora 2 soldados vivos, metade dos anteriores. Mais uma vez, é o soldado número 1 a matar. Numeramos os dois sobrevivente – o número 1 e o número 2 – e então vemos que o 1 mata o 2 e sobrevive.

Agora, como é que sabemos o que acontece entre os número de soldados que são potência de dois (e cujo número do lugar sobrevivente é sempre 1, renovando o ciclo)? Olhando mais uma vez para a tabela vemos que, entre esses números, o número do lugar sobrevivente é sempre uma contagem de dois em dois ao longo dos números ímpares, juntando sempre mais um número ímpar em relação ao ciclo anterior. Matematicamente, sabemos que qualquer número de soldados pode ser escrito como uma grande potência de dois somado com mais qualquer coisa.

Ou seja: qualquer número de soldados vai ser igual à soma da maior potência de dois possível para esse número (a potência de dois mais próximo dele por defeito) mais um determinado número, de modo que n= 2^x + y.

Agora sentiu um nó na cabeça, não foi? Vamos a um exemplo. Se o número de soldados for 77 (n=77), podemos escrever esse número como sendo a soma de 64 – 2^x = 64, o valor da potência de dois mais próxima de n=77) com 13 – y=13. Esse número 13 – que vai ser essencial – também pode ser escrito como uma série de potências de dois, portanto 77 = 64 + 8 + 4 + 1 exatamente porque 77 = 2⁶ + 2³ + 2² + 2⁰. E isto é importante porque esta soma funciona como uma impressão digital de cada número: não há nenhuma outra forma de escrever o número 77 com recurso a potências de dois. Tente com qualquer outro número e vai reparar que nenhuma das potências se repete.

Mas a magia do exercício não está na maior potência de dois para cada número, mas antes no que sobra – ou seja, naquele y. No caso do número 77 – que é 64 + 13 – é o número 13 que tem as respostas para tudo. Imagine que o número de soldados é 13 (n=13). Neste caso, o número 1 mata o número 2, o número 3 mata o número 4, o número 5 mata o número 6, o número 7 mata o número 8 e o número 9 mata o número 10. Neste momento, estão mortas y pessoas e é a vez do número 11 matar a pessoa à sua esquerda. Agora repare: quantas pessoas sobreviveram até agora? Sobreviveram 8, que é uma potência de dois. E quem sobrevive sempre numa potência de dois? Exatamente: quem está sentado no lugar número 1, a primeira pessoa a matar. Continuemos a matança: o número 11, o próximo a assassinar, vai matar o 12, o número 13 mata o número 1, o número 3 mata o número 5 e o número 7 mata o número 9. Agora que é a vez do número 11 a matar de novo, estão quatro pessoas vivas. Então 11 vai matar 13, 3 vai matar 7 e 11, de novo, vai matar 3. E o soldado no lugar 11 sobrevive.

Este padrão é o cofre da resposta: se escrever um número como a soma de uma potência de dois (2^x) mais o restante (y), ao fim de y passos a pessoa de quem for a vez de matar vai ser a sobrevivente no final do pacto, porque quando a sua vez chegar o número de sobreviventes será precisamente uma potência de dois. Matematicamente, escrevemos que S(n)= 2y + 1. O teorema será então que: se n= 2^x + y, com y < 2x, então S(n) = 2y + 1 (se o número de soldados for igual a uma potência de dois com um determinado número que seja inferior ao dobro do expoente, então número do lugar sobrevivente será o dobro desse determinado número com 1). Então é este o mecanismo:

• Ao fim de y passos, é a vez da pessoas 2y+1 de matar. A
• Ao fim de y passos, o número de sobreviventes será sempre uma potência de dois.
• Sempre que o número é correspondente a uma potência de dois, a pessoa número 1 – a primeira a matar – é sempre a vencedora.

Deixemo-nos de rodeios matemáticos agora e voltemos ao problema do pobre Flávio Josefo. Nesse problema, há 41 pessoas envolvidas, ou seja, n=41. Escrevendo esse número usando potências de dois obtemos que 41 = 32 (a potência de dois mais anterior ao número) + 9. Como o dobro de 9 é 18 e temos sempre de somar 1, então o número do lugar sobrevivente será 19. É então aí que Flávio Josefo se tem de sentar.

Problema resolvido – embora consigamos perceber bem, ao fim de todos estes cálculos, as dores de cabeça dos matemáticos. Mas porque é que este exercício irrita tanto os informáticos. Bem, isso acontece porque a fórmula a que chegámos pode ser escrita na forma de um código binário (feito de 1 e 0), tal como os que compõem a arquitetura dos softwares. Quando se escreve um número como a soma de uma potência de dois, podemos escrevê-lo como código binário. Por exemplo, no caso do problema de Flávio Josefo, que envolve 41 participantes: 41 = 32 + 8 +1 = 2⁵ + 2³ + 2⁰ . Na notificação binária, os dígitos correspondentes a várias potências de dois podem ser expressos como sendo um 0 ou um 1. Então, para escrever 41 como potências não precisamos de 2⁴ nem de 2² ou de 2¹. Então, em código binário, o número 41 escreve-se “101001” porque:

Ora, usando o código binário, a forma de encontrar a solução é pegar na escrita binária para o número de soldados, n, é pegar no primeiro dígito (neste caso 1) e colocá-lo no fim. Ou seja, se eu escrever “010011” – tirando o primeiro 1 do início e colocando no fim – vou obter o lugar do número sobrevivente porque, visto que:

sabemos que S(n) = 2⁴+2¹+2⁰ = 16+2+1= 19! É então muito mais fácil encontrar o resultado com o teorema encontrado pelos informáticos do que o encontrado pelos matemáticos. E pronto! Ponto final. Se ainda tem algumas dúvidas, o melhor é ver o vídeo do professor, que lhe deixamos aqui em baixo.