O problema das Moedas

Desde minha adolescência este problema me intrigou. Foi-me apresentado como desafio pelo meu irmão mais velho e, como se espera entre irmãos, tornou-se uma disputa. Depois, uma fascinação. Este problema, um desafio do ponto de vista lógico e algoritmico, é bastante discutido por matemáticos e cientistas da computação. Aqui vou apresentar uma versão muito particular, adaptando a história às  diferentes versões deste problema.

Num país distante, numa época remota, um Rei decidiu cunhar 9 moedas de ouro, em comemoração por uma vitória bélica qualquer. O seu ourives, porém, desonestamente cunhou uma moeda de prata e apenas oito de ouro. Adequadamente tingida, esta moeda falsa não era percebível a olho nu, mas naturalmente pesava um pouco mais que uma moeda verdadeira. Quando descobriu a falcatrua, o Rei condenou o ourives à forca. Ante seu pedido de clemência, o monarca resolveu dar-lhe uma chance. Pediu uma balança de pratos e, entregando-a junto com as 9 moedas visualmente idênticas, determinou.

"Tu serás perdoado se mostrares uma forma infalível de se encontrar a moeda falsa entre as nove, tendo à mão apenas as moedas e esta balança, que não poderá ser usada mais do que duas vezes.".

O problema, portanto, é encontrar um algoritmo de “pesagens” que encontre a moeda falsa usando a balança apenas duas vezes. Talvez, caro leitor, valha à pena investir um pouco de seu tempo antes de prosseguir com a leitura, e resolver o problema por si só.

O algoritmo. Para simplificar, nomeemos as 9 moedas em m1, m2, m3, m4, m5, m6, m7, m8 e m9, e os pratos da balança em “prato A” e “prato B”. Qualquer uma das moedas pode ser falsa, com igual probabilidade. O algoritmo, então, considera as pesagens da seguinte maneira.

Ponha m1, m2, m3 no prato A e m4, m5, m6 no prato B. Três estados possíveis podem ocorrer na balança, e cada um deles nos permitirá obter conclusões.

E1: Os dois pratos se equilibram. Neste caso, as moedas m1 a m6 são verdadeiras e a moeda falsa está entre m7 e m9.

E2: O prato A pesa mais. Neste caso as moedas m4 a m9 são verdadeiras, e a moeda falsa está entre m1 e m3.

E3: O prato B pesa mais. Neste caso, as moedas m1, m2, m3, m7, m8 e m9 são verdadeiras e a moeda falsa está entre m4 e m6.

Para cada estado acima, uma nova pesagem será suficiente para identificar a moeda falsa.

Se E1: (pratos equilibrados) então ponha m7 no prato A e m8 no prato B. Se o prato A pesar mais, a moeda falsa será m7. Se o prato B pesar mais, a moeda falsa será m8. Se houver equilíbrio, a moeda falsa será m9.

Se E2: (prato A pesou mais) então ponha m1 no prato A e m2 no prato B. Se o prato A pesar mais, a moeda falsa será m1. Se o prato B pesar mais, a moeda falsa será m2. Se houver equilíbrio, a moeda falsa será m3.

Se E3: (prato B pesou mais) então ponha m4 no prato A e m5 o prato B. Se o prato A pesar mais, a moeda falsa será m4. Se o prato B pesar mais a moeda falsa será m5. Se houver equilíbrio, a moeda falsa será m6.

Esquematicamente podemos ver este algoritmo na tabela baixo. A primeira coluna indica a primeira pesagem e a segunda coluna indica a segunda. Abaixo do possível resultado da pesagem está a conclusão; por exemplo, se o peso das moedas m1, m2 e m3 for maior que o peso das moedas m4, m5 e m6 então podemos concluir que a moeda falsa está no grupo m1, m2, m3.

Na tabela se ilustra de que forma os conjuntos de moedas são pesados, e por simplieifcação definimos algumas operações de comparação aqui. Quando o prato A pesa mais, dizemos que o primeiro conjunto é “maior”. Quando o prato B pesa mais, o segundo conjunto é “maior” e quando há equilíbrio, os conjuntos são “iguais”.

Este algoritmo resolve infalivelmente o problema, e livra o pescoço do ourives. Mas o mundo sempre pode ficar mais complicado: o Rei pega a moeda falsa e a lança fora. Em seguida junta mais 4 moedas e determina.

"Agora tu tens um moeda falsa entre 12, e não sabes se ela é de Prata (que pesa mais que uma de ouro) ou de Alumínio (que pesa menos). Toma a mesma balança e determina infalivelmente a moeda falsa, bem como de qual metal ela foi cunhada. Generosamente, dou-te o direito de usar balança não duas, mas três vezes!".

Agora precisamos de um procedimento mais sofisticado. O Leitor é convidado a divertir-se com ele por algumas horas antes de prosseguir com a leitura. A solução segue abaixo.

O algoritmo. Chamemos as moedas de m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11 e m12. Este processo todo pode ser resumido na tabela a abaixo.

Note que há observações que aparecem sob os possíveis resultados das pesagens. Estas observações consideram que, diante dos resultados obtidos na balança, algumas moedas são candidatas a serem falsas. Todavia, em alguns casos uma ou mais moedas são candidatas a serem falsas apenas se a moeda falsa for mais pesada (P). Em outros casos, apenas de for mais leve (L), ou não se pode concluir nada sobre isto (?).

Por exemplo, se o peso das moedas m1, m2, m3 e m4 for maior que o peso das moedas m5, m6, m7 e m8, então as moedas m1, m2, m3 e m4 podem ser falsas, bem como as moedas m5, m6, m7 e m8. A diferença é que se a moeda falsa estiver no grupo de m1 a m4, então ela será mais pesada (ou seja, uma moeda deste grupo só será falsa se pesar mais), porque o lado delas na balança pesou mais. Da mesma forma, se a moeda falsa estiver no grupo de m5 a m8, então ela será mais leve (ou seja, uma moeda deste grupo só será falsa se pesar menos).

Caso a pesagem dos grupos m1 a m4 e m5 a m8 aponte um equilíbrio, então a moeda falsa está entre m9, m10, m11 e m12, mas neste caso não há nenhuma informação sobre ser a moeda falsa mais leve ou mais pesada que uma moeda real, já que elas ainda não foram à balança.

Abaixo está o algoritmo em forma de tabela. Após cada pesagem se indica que uma moeda pode (caso se revelar falsa) ser mais leve que uma moeda de ouro (L), ou mais pesada (P) ou isso é indeterminado (?).

Este algoritmo pode ser implementado em computador com relativa facilidade. Mas é importante observar que ele só pode ser executado em série, já que a definição de cada pesagem (exceto a primeira) depende do resultado pesagem anterior.

O Rei, então, lançou um desafio derradeiro ao ourives desonesto.

"Está deveras simples este problema para ti. Não vale mais o teu pescoço? Agora tu vais ordenar três de meus escravos que levem as moedas e façam, cada um deles, uma pesagem. Depois que o último deles cumprir sua tarefa, e apenas então, eles te dirão os resultados obtidos. E ainda assim tu terás que encontrar infalivelmente a moeda falsa!".

Agora o problema das moedas precisa ganhar uma implementação paralela, e sem memória compartilhada. Três processos de pesagem distintos devem ser conduzidos sem que um conheça o resultado dos outros, e é necessário que, de posse dos resultados dos três, se encontre infalivelmente uma resposta satisfatória.

Apesar de parecer complexa, a solução desta última versão do problema das moedas é curiosamente simples. Observando a tabela acima, pode-se ver que há grupos distintos de moedas que são colocadas num mesmo prato, em cada instante. Por exemplo, na pesagem 2, qualquer comparação é sempre entre algumas moedas do grupo [m1, m2, m3, m5] contra algumas moedas do grupo [m4, m9, m10, m11]. Da mesma forma, na terceira pesagem aparece sempre uma moeda do grupo [m1, m4, m6, m9] contra uma moeda do grupo [m2, m7, m10, m12]. Isto permite definir três pesagens independentes, e inferir de que forma cada uma das moedas pode ser falsa, a depender do resultado das pesagens. Uma moeda pode ser definitivamente verdadeira (V), ou possivelmente falsa, se for mais leve (L), ou possivelmente falsa se for mais pesada (P), ou apenas possivelmente falsa, sem que se saiba se mais leve ou mais pesada (?).

Pesagem 1. Ponha m1, m2, m3 e m4 no Prato A e m5, m6, m7 e m8 no prato B. Note que se o prato A pesar mais, então teremos m1(P), m2(P), m3(P), m4(P), m5(L), m6(L), m7(L), m8(L), m9(V), m10(V), m11(V), e m12(V). Se houver equilíbrio, teremos m1(V), m2(V), m3(V), m4(V), m5(V), m6(V), m7(V), m8(V), m9(?), m10(?), m11(?), e m12(?) e se o prato B pesar mais concluiremos m1(L), m2(L), m3(L), m4(L), m5(P), m6(P), m7(P), m8(P), m9(V), m10(V), m11(V), e m12(V).

Pesagem 2: Ponha m1, m2, m3 e m5 no Prato A e m4, m9, m10 e m11 no prato B. Neste caso, se o prato A pesar mais, teremos m1(P), m2(P), m3(P), m4(L), m5(P), m6(V), m7(V), m8(V), m9(L), m10(L), m11(L), e m12(V). Caso haja equilíbrio, então m1(V), m2(V), m3(V), m4(V), m5(V), m6(?), m7(?), m8(?), m9(V), m10(V), m11(V), e m12(?). E se o prato B pesar mais, decidimos m1(L), m2(L), m3(L), m4(P), m5(L), m6(V), m7(V), m8(V), m9(P), m10(P), m11(P), e m12(V).

Pesagem 3. Ponha m1, m4, m6 e m9 no prato A e m2, m7, m10 e m12 no prato B. Aqui, se o prato A pesar mais, teremos m1(P), m2(L), m3(V), m4(P), m5(V), m6(P), m7(L), m8(V), m9(P), m10(L), m11(V), e m12(L). Em caso de equilíbrio, teremos m1(P), m2(L), m3(?), m4(P), m5(?), m6(P), m7(L), m8(?), m9(P), m10(L), m11(?), e m12(L). E caso o prato B pese mais, a conclusão será m1(L), m2(P), m3(V), m4(L), m5(V), m6(L), m7(P), m8(V), m9(L), m10(P), m11(V), e m12(P).

As pesagens são efetivamente independentes mas, de posse delas, pode-se montar uma espécie de “tabela-verdade” sobre cada uma das moedas. É muito importante o leitor observar o seguinte: caso uma moeda seja considerada candidata a falsa, sendo mais leve, numa pesagem, e depois considerada candidata a falsa, sendo mais pesada, em outra, então esta moeda não pode ser falsa. E, evidentemente, não pode ser falsa a moeda que for considerada verdadeira em alguma pesagem. Assim, pode-se estabelecer uma tabela com os possíveis resultados das pesagens 1, 2 e 3, juntamente com as conclusões decorridas de cada resultado. Isto está resumido na tabela abaixo.

A tabela acima permite formar pequenas tabelas para cada possível combinação de resultados das três pesagens independentes. Quando consideramos as possíveis conclusões resultantes das pesagens, podemos excluir candidatas e, assim, sempre é possível apontar a resposta para o problema.

Por exemplo, caso a primeira, a segunda e a terceira pesagem tenham respondido que o prato A pesou mais, teríamos

m1

m2

m3

m4

m5

m6

m7

m8

m9

m10

m11

m12

E1-1

P

P

P

P

L

L

L

L

V

V

V

V

E2-1

P

P

P

L

P

V

V

V

L

L

L

V

E3-1

P

L

V

P

V

P

L

V

P

L

V

L

Combinação

P

X

X

X

X

X

X

X

X

X

X

X

O que garante a resposta: a moeda falsa é m1, e ela é mais pesada. Caso a primeira e a segunda pesagem tenham registrado peso maior do prato A, e a terceira pesagem tenha sido equilibrada, a tabela é como segue.

m1

m2

m3

m4

m5

m6

m7

m8

m9

m10

m11

m12

E1-1

P

P

P

P

L

L

L

L

V

V

V

V

E2-1

P

P

P

L

P

V

V

V

L

L

L

V

E3-2

V

V

?

V

?

V

V

?

V

V

?

V

Combinação

X

X

P

X

X

X

X

X

X

X

X

X

Deixando como única possível candidata a moeda m3, definitivamente mais pesada. A tabela abaixo mostra as possíveis combinações de estados com as respectivas respostas. Note que há uma simetria interessante entre as posições que cada moeda ocupa na tabela.

Sucessão de Estados	Moeda falsa	Sucessão de Estados	Moeda falsa	Sucessão de Estados	Moeda falsa
E1-1 E2-1 E3-1	m1 mais pesada	E2-1 E2-1 E3-1	m10 mais leve	E3-1 E2-1 E3-1	IMPOSSÍVEL
E1-1 E2-1 E3-2	m3 mais pesada	E2-1 E2-1 E3-2	m11 mais leve	E3-1 E2-1 E3-2	m5 mais pesada
E1-1 E2-1 E3-3	m2 mais pesada	E2-1 E2-1 E3-3	m9 mais leve	E3-1 E2-1 E3-3	m4 mais leve
E1-1 E2-2 E3-1	m7 mais leve	E2-1 E2-2 E3-1	m12 mais leve	E3-1 E2-2 E3-1	m6 mais pesada
E1-1 E2-2 E3-1	m8 mais leve	E2-1 E2-2 E3-1	IMPOSSÍVEL	E3-1 E2-2 E3-1	m8 mais pesada
E1-1 E2-2 E3-3	m6 mais leve	E2-1 E2-2 E3-3	m12 mais pesada	E3-1 E2-2 E3-3	m7 mais pesada
E1-1 E2-3 E3-1	m4 mais pesada	E2-1 E2-3 E3-1	m9 mais pesada	E3-1 E2-3 E3-1	m2 mais leve
E1-1 E2-3 E3-2	m5 mais leve	E2-1 E2-3 E3-2	m11 mais pesada	E3-1 E2-3 E3-2	m3 mais leve
E1-1 E2-2 E3-3	IMPOSSÍVEL	E2-1 E2-2 E3-3	m10 mais pesada	E3-1 E2-2 E3-3	m1 mais leve

Uma conjectura interessante é sobre a possibilidade de se resolver este problema não com 12, mas com 13 moedas. É que o espaço de combinações abre um total de 27 soluções diferentes para o problema, (27 = 3³, sendo 3 pesagens e 3 possíveis resultados em cada pesagem) mas as 12 moedas ocupam apenas 24 delas (12 moedas vezes 2 possibilidades). Sobram ainda 3 combinações “impossíveis”. Se fossem 13 moedas, ainda se ocuparia apenas 26 possíveis soluções. Logo, parece possível que este problema admita solução para 13 moedas.

Encontrar a solução para o problema com 12 moedas tem sido uma tarefa de interesse bastante razoável para estudantes de Ciência da Computação e de Matemática, embora sua dificuldade esteja, principalmente, na concepção do algoritmo. De posse dele, as considerações a respeito da paralelização e as conjecturas sobre os limites da solução não são muito difíceis de serem percebidas.