Enunciado: Tenho 9 bolas e uma dessas 9 bolas é mais pesada que as outras, que são todas iguais. Tem-se uma balança de comparação. Pode colocar quantas bolas quiser de cada lado, porém a balacça só pode ser utilizada duas vezes.

Notações Importantes:

• Bolas: $b_i \in B | B \equiv \N \cap [1,9]$
• Bola escolhida: $b^* | b^* \in B$
• Balança: $\underline{\Omega} = (L, R) | L \cup R = B \ \& \ L \cap R = \empty \ \& \ |L| = |R|$
• Situação da Bola:
  • 0 se tem o peso padrão
  • 1 se é a bola mais pesada
  • 2 se não sabe
• Mapa m: array onde para toda posição i apresenta a situação da bola $b_i$

Estados:

$s_i = m_i$ , onde m é um array de comprimento 9 fomrado por 0’s, 2’s e no máximo com um único 1, com os dados identificados no status i

Estado Inicial:

$s_o = [2, 2, 2, 2, 2, 2, 2, 2, 2,]$

Estado aceitos:

$s_i | 1 \in m_i$

Ações:

$a = \underline{\Omega}_i$

Resultado:

$Balance(s_i, a) = \\ = \ if \ b^* \in L \ from \ a \ then -1 \\ = \ if \ b^* \in R \ from \ a \ then +1 \\ = \ else \ 0$

$Result(s_i, a) = \\ = \ if \ Balance(s_i,a) = -1 \ then \ m_i = 0 \ \forall b_i \in L \ || \ b_i \not \in a \\ = \ if \ Balance(s_i, a) = 1 \ then \ m_i = 0 \ \forall b_i \in R || \ b_i \not \in a\\ = \ if \ Balance(s_i, a) = 0 \ then \ m_i = 0 \ \forall \ b_i \in a \\ = \ if \ \exists ! 2 \in m_i \ then \ m_i = 1$