Outro atentado da rainha vizinha contra o rei malvado (ver problema Degustadores Facínoras). Novamente, uma única garrafa da adega real foi comprometida, e novamente não se sabe exatamente qual… Desta vez, porém, os tempos estão mais difíceis, e o rei possui apenas 240 garrafas e cinco prisioneiros (os quais estão disponíveis para sacrifício). Sabendo que o veneno pode levar até um mês para se manifestar, como o rei deve proceder para identificar a bebida envenenada em até dois meses (*)?
(*) Despreze gastos de tempo com “logística”. Considere relevante apenas o tempo necessário para o veneno fazer efeito.
O problema foi proposto pelo brunoargento no twitter (aqui e aqui).
André
javendo
aaronalb
Pietro
ynotx
Luís Guilherme Fernandes Pereira
mariogen
abgrilo
Como ninguém se manifestou, vou lançar uma dica aqui. O fato numérico que vamos usar é 240 < 243 = 3^5.
Numere cada garrafa com cinco dígitos em base 3, isto é, 00000,00001,00002,00010,00011,00012,00020,…,22212. O número de dígitos é o mesmo de prisioneiros, então é natural associar cada dígito a um prisioneiro.
Agora, para cada garrafa com dígitos ijklm, distribua-a entre os prisioneiros, de algum modo ditado pelos dígitos, que permita pelo menos três resultados diferentes para cada prisioneiro.
Pietro, conseguiu matar o problema?
De fato, a dica do pietro é muito esclarecedora…
Usando a numeracao das garrafas dadas por ele e numerando os prisioneiros de 1 a 5 podemos tomar a seguinte estratégia:Se o i-ésimo digito da numeraçao base 3 de uma garrafa for
1 -> O i-ésimo prisioneiro toma o vinho dessa garrafa no inicio do primeiro mes.
2 -> O i-ésimo prisioneiro toma o vinho dessa garrafa no inicio do segundo mes.
continuando…
0 -> O i-ésimo prisioneiro nao toma o vinho dessa garrafa
Agora basta criar uma maneira de analisar a disposiçao das mortes de modo a chegar aa garrafa envenenada! Podemos fazer assim:
-> O i-ésimo digito da garrafa envenenada serah 1, 2 ou 0 respectivamente se o i-ésimo prisioneiro morreu ao fim do primeiro mes, ao fim do segundo ou ele nao morreu.
.Curiosamente o numero de mortes vai depender tao somente do numero de zeros na numeracao da garrafa envenenada: para cada 0, um prisioneiro se salva da morte! =0