O puzzle das 12 bolinhas e a Teoria da Informação

Neste post, usarei uma resolução do puzzle da 12 bolinhas para mostrar como nós, intuitivamente, utilizamos os conceitos da Teoria da Informação para resolver este tipo de problema.


O problema das 12 bolinhas

“Há doze bolinhas, extremamente idênticas. Têm pesos iguais exceto uma delas que tem um peso um pouco diferente. Não se sabe a priori se é mais leve ou mais pesada. Com uma balança de dois pratos, encontre a bola diferente fazendo apenas três pesagens, dizendo também se é mais leve ou mais pesada”.

Sugiro que o leitor perca pelo menos 1 hora tentando resolver por si só, antes de retornar ao post.

Nota: o “culpado” por este post é o meu amigo Marcos Melo, que me enviou este puzzle.

 


Resolução

Imagine que temos 12 bolinhas. Podemos colocar a entropia desta situação inicial numa tabela:

Inform01.png

Pesagem 1: Coloco 4 no primeiro prato, e 4 no segundo, deixando 4 de fora.
Bal01.png

Há duas situações possíveis:

1.1 A balança fica equilibrada
1.2 A balança pende para um dos lados

Situação 1.1 – A balança fica equilibrada

É a situação mais simples. Teremos a certeza de que as 8 bolinhas são neutras, portanto, vamos pintar de cinza.
Bal02.png

 

A bolinha diferente está entre as quatro que ficaram de fora. Vamos colocar 2 bolinhas em um dos pratos, 1 no outro, e deixar 1 de fora. Para equilibrar a balança, vamos colocar uma bolinha neutra no lado que ficou sozinho.

Bal03.png
De novo, temos duas situações:
1.1.1 A balança fica equilibrada
1.1.2 A balança pende para um dos lados

Situação 1.1.1 – A balança fica equilibrada

Bal04.png
Se a balança ficar equilibrada, a bolinha que ficou de fora é o intruso. Uso a terceira e última pesagem somente para decidir se ela é mais leve ou mais pesada. Fim deste ramo da árvore.

Situação 1.1.2 A balança pende para um dos lados

Bal05.png
Vamos pintar as bolinhas do lado mais leve de verde, e do lado mais pesado de vermelho, exceto a bolinha neutra.
Observe que são três bolinhas incógnitas, duas da mesma cor e uma de outra. Vamos chamar este ponto de “Procedimento das três incógnitas“.

Peso as duas bolinhas que eram do mesmo prato.

Bal06.png

1.1.2.1 A balança fica equilibrada: quer dizer que a bolinha que ficou de fora é o intruso, e é mais pesada.
1.1.2.2 A balança pende para um dos lados: o intruso é a bolinha mais leve.

Para o caso em que há duas bolinhas vermelhas e uma verde, a resolução é análoga. Fim deste ramo da árvore.

Este é o caso fácil. Vamos para a outra situação.


Situação 1.2 A balança pende para um dos lados.
Vamos pintar as bolinhas.

 

Bal12.png

Para a segunda pesagem, retirar duas bolas de um prato e uma do outro. Completo com uma neutra.
Também inverto de prato duas das bolinhas que estavam inalteradas. Vou pesar assim:

Bal08.png
Tenho três situações:
1.2.1 A balança fica equilibrada
1.2.2 A balança pende para o lado contrário
1.2.3 A balança continua pendendo para o mesmo lado

Situação 1.2.1 – A balança fica equilibrada
Se a balança fica equilibrada, pinto as bolinhas dos pratos de cinza. Fico com três incógnitas, duas da mesma cor e uma de outra.

Bal09.png
Posso usar o mesmo “Procedimento das três incógnitas” do item 1.1.2 para encontrar o intruso e o seu peso relativo.

1.2.2 A balança pende para o lado contrário
Se a balança pender para o lado contrário à primeira pesagem, quer dizer que uma das duas bolinhas que mudaram de posição é o intruso. Posso pintar as demais de cinza.

Bal10.png
Uso a terceira pesagem, de uma das bolinhas do prato contra um peso neutro. Se der igual, sei que o intruso ficou fora, e se é mais leve ou não. Se der diferente, o intruso é a bolinha pesada, e sei o peso relativo.

1.2.3 A balança pende para o mesmo lado
Neste caso, sei que as bolinhas que ficaram de fora são neutras. E as que mudaram de lado também são neutras.

Bal11.png
Fico com três bolinhas de incógnita. Posso usar o mesmo  “Procedimento das três incógnitas” do item 1.1.2 para encontrar o intruso e o seu peso relativo.

Portanto, está resolvido o puzzle.

De forma geral, em cada passo procurou-se ganhar o máximo possível de informação nova. A distribuição do conjunto incógnitas no prato 1 x incógnitas no prato 2 x incógnitas fora do prato ficou o mais igual possível. E isto tem relação total com Informação.


Qual é a lógica da resolução do puzzle, sob a ótica da Teoria da Informação?

A Teoria da Informação de Claude Shannon, publicada em 1948, é importante para definir limites na transmissão de dados, número de bits para compressão de dados. Tem muita relação com entropia, que é mais ou menos a medida de desorganização do sistema.
A cada passo, tentamos diminuir ao máximo a entropia do sistema.

Início: Entropia máxima.

Inform01.png

Intuitivamente, sabemos que se eu usar a primeira pesagem para pesar uma bolinha em cada prato, e deixar 10 de fora, vou estar ganhando pouca informação. Se, por sorte, uma das duas bolinhas pesadas for mais leve ou mais pesada, resolvo de cara a situação, mas esta é uma possibilidade remota. A medida de entropia retira esta intuição por probabilidades.

Vejamos.

Após pesar 4 e 4 bolinhas, deixando 4 de fora, temos duas possibilidades: ou a balança dá igual, ou dá diferente.
Se a balança der diferente, saberemos que as 4 de fora são neutras, e que algumas bolinhas não poderão ser a mais leve e outras não poderão ser a mais pesada.
Se a balança der igual, saberemos que as oito serão neutras, mas não temos nenhuma informação sobre as quatro que ficaram de fora.
Inform02.png
Temos 16 incógnitas para primeira situação, e 12 na segunda.
Temos 2/3 de chance ocorrer a primeira situação (probabilidade da bolinha diferente estar entre as 8 pesadas) e 1/3 da segunda situação.
Portanto, o valor esperado do número de incógnitas é de 16*2/3 + 12 *1/3 = 14.6

Se eu pesar 5 e 5, deixando duas de fora?

Teremos o seguinte quadro.
Inform03.png
Valor esperado: 20*10/12 + 6*2/12 = 17.6 (terei mais incógnitas que pesando 4 x 4 x 4)

Se eu pesar 3 e 3, deixando 6 de fora?

Teremos o seguinte quadro.

inform04.png

Valor esperado: 12*6/12 + 18*6/12 = 15 (terei mais incógnitas que pesando 4 x 4 x 4)

Se eu pesar 1 e 1, deixando 10 de fora?

Teremos o seguinte quadro.
Inform05.png

Valor esperado: 4*2/12 + 30*10/12 = 25.6 (terei mais incógnitas que pesando 4 x 4 x 4 ou 5 x 5 x 2 ou 3 x 3 x 6)

E isto confere com a intuição. Pesar 1 e 1 deixando 10 de fora é pior do que pesar 2 x 2 x 8. E a melhor situação é a mais simétrica, 4 x 4 x 4.

Em machine learning, existe até um algoritmo de classificação que usa exatamente este mesmo princípio. O nome do algoritmo é  C4.5, e ele faz o seguinte: em cada passo, calcula a entropia se aplicar um critério, e escolhe o critério que mais reduz a entropia. Depois, escolhe o segundo critério da mesma forma, e assim sucessivamente.

O C4.5 é simples computacionalmente, e na prática chega a bons resultados. E é mais ou menos como aplicar o problema de separar bolinhas com uma balança, porém com milhares de bolinhas, e com uma balança de várias dimensões!

Bom, duvido que a pessoa que inventou o puzzle tivesse pensado em Claude Shannon e o algoritmo C4.5. Só mesmo este blog maluco para fazer este tipo de correlação!

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s