Question

(Combinatória: Relações binárias e contagem)

Sejam a, b, c inteiros quaisquer. Considere sobre ℤ as relações binárias de igualdade = e não-igualdade ≠ definidas de maneira usual.

Com as relações = e ≠, de quantas formas é possível relacionar a, b e c, dois a dois, de modo que as sentenças obtidas possam ser simultaneamente verdadeiras?

Obs.: Considere que os casos a R b e b R a são equivalentes, com R ∈ {=, ≠}.​

Answer 1

Há 3 relações: (a, b), (b, c) e (c, a). Posso escolher como são dadas as relações (a, b) e (b, c) de qualquer modo, já que estas são independentes. Já a relação (c, a) depende das anteriores. Se todas as anteriores são iguais, $c = a$. Se há uma diferente antes, $c \neq a$. Se há mais do que uma diferente, c pode ser tanto igual quanto diferente de a.

Já que (a, b) e (b, c) podem ser escolhidos de 2 modos cada, há 4 modos de se escolherem ambos. Somarei todas as posteriores possibilidades de (c, a) dependendo das relações anteriores:

$== 1\\=\neq1\\\neq=1\\\neq\neq2$

Totalizando 5 possibilidades.