O problema do raptor

O Problema do raptor

O Dr. Ecco era conhecido por resolver problemas que aparentemente mais ninguém conseguia. Numa fase da sua carreira em que se encontrava quase em reclusão, aceitou ainda o seguinte caso posto por uma senhora, acerca do seu talentoso filho que se dava com más companhias.
Diz a senhora: Um dia o meu filho simplesmente desapareceu. Fiquei sem notícias durante um mês, até receber um telefonema de um homem chamado Baskerhound. Deixou-me um enigma na seguinte mensagem

Estou a pensar num número entre 1 e 2000. Se conseguir determiná-lo em 15 perguntas ou menos, libertarei o seu filho. Caso contrário, ele será morto. Responderei às perguntas apenas com "sim" ou "não", mas cuidado, pois poderei mentir uma vez. Além disso, só responderei às questões apenas no fim, depois de as ter colocado todas.

Ou seja, será preciso fazer as 15 perguntas de uma vez, só depois o raptor dá as 15 respostas sim/não (e poderá mentir uma vez) e de seguida teremos de ser capazes de adivinhar o número.

(Problema retirado e adaptado de The Puzzling Adventures of Doctor Ecco, Dennis Shasha, Dover Publications.)

Nesta cadeira de CTC, iremos ver que a resposta a este problema é um exemplo de um Código de Hamming. As respostas sim/não vão corresponder naturalmente a bits (i.e., aos dígitos 0 e 1, que formam o alfabeto do código) o número de perguntas, 15 neste caso, será o comprimento das palavras de código, e a mentira ou resposta errada dada pelo raptor será considerada como um "erro de transmissão" que o código deverá corrigir. A solução ao problema do raptor é portanto um código binário corrector de um erro.

No seguimento do problema do raptor, o livro referido acima propõe também as seguintes questões, mais simples de resolver.

Considere o problema das moedas: há uma fila de onze moedas sobre uma mesa, numeradas de 1 a 11, cada uma tem o lado "cara" virado para cima ou para baixo. Apenas uma pessoa consegue ver as moedas e outra pessoa tenta adivinhar a sequência de caras e coroas das moedas. Tal como no problema do raptor, só são permitidas perguntas de resposta "sim" ou "não", todas feitas de seguida e respondidas apenas no fim, depois da última pergunta ser colocada.

1. Se não forem permitidas respostas erradas (ou mentiras), o problema das moedas resolve-se em 11 perguntas. Como?

2. Como podemos usar a solução anterior para adivinhar um número entre 1 e 2000 em 11 perguntas de resposta "sim" ou "não", obtendo as respostas apenas depois de todas as perguntas serem feitas (tal como no problema do raptor), mas desta vez sem mentiras?

3. Como resolver o problema das moedas em 33 perguntas, se for permitido mentir uma vez?

E agora de volta ao problema do raptor (ou quase):

4. Como resolver o problema das moedas em 15 perguntas, se for permitido mentir uma vez?

Se conseguiu responder à pergunta 4, deixa-se como último desafio reformular as perguntas do problema das moedas de modo a adivinhar o número em que o raptor está a pensar.