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:

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

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.

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.

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

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

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.

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.

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:

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.

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.

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.

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.

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.

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.

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.

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.

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!

Vide também:

https://ideiasesquecidas.com/laboratorio-de-matematica/

https://ferramentasexcelvba.wordpress.com/2019/05/27/send-more-money/