Problema 5
Uma permutação $$(a_1, a_2, a_3,…, a_{n-1}, a_{n})$$ dos números do conjunto $${1,2,3,…,n}$$ é legal se não existem dois termos consecutivos cuja soma é um múltiplo de $$3$$ e se os dois vizinhos de um termo qualquer não diferem por um múltiplo de $$3$$. Por exemplo, $$(4,6,2,5,3,1)$$ é uma permutação legal dos números do conjunto $${1,2,3,4,5,6}$$. Entretanto, $$(1,2,5,3,4,6)$$ não é uma permutação legal do mesmo conjunto, pois os números $$1$$ e $$2$$ são vizinhos e sua soma é um múltiplo de $$3$$. Além disso, outra razão para ela não ser legal, é que os vizinhos do número $$4$$, que são o $$3$$ e o $$6$$, diferem por um múltiplo de $$3$$.
a) Determine o número de permutações legais do conjunto $${1,2,3,4,5,6}$$.
b) Determine o número de permutações legais do conjunto $${1,2,3,…,2016}$$.
Observação: Uma permutação de um conjunto é uma sequência ordenada contendo cada um de seus elementos uma única vez.
Solução por Caio Hermano:
Para resolvermos o problema vamos utilizar somente os resíduos dos números do conjunto na divisão por $$3$$. Mostraremos que é possível determinar com base nos resíduos a quantidade de permutações legais:
Se dispomos do dígito $$0$$, então o próximo dígito pode ser $$1$$ ou $$2$$, mas essa será a única escolha possível que poderemos fazer, de fato, determinado o segundo dígito a sequência está definida:
Se for o $$1$$: o próximo dígito não pode ser $$2$$, já que a soma resultará num múltiplo de $$3$$, também não pode ser $$0$$, já que a diferença de dois vizinhos de um termo também não pode ser divisível por $$3$$, logo só pode ser novamente $$1$$ e o processo se repete. Da mesma forma se escolhermos o $$2$$. Isso acontece pois, suponha que tenhamos determinado os dois últimos dígitos da sequência e esses sejam $$a$$ e $$b$$, então o próximo dígito não pode ser $$3-b$$ (que somado com $$b$$ resulta num múltiplo de $$3$$) nem $$a$$ (que difere zero de $$a$$, ou seja, temos uma diferença divisível por $$3$$), logo há dois casos a considerar:
– $$a$$ incongruente a $$3-b$$, então não temos escolha e o número está determinado, como queremos demonstrar!
– $$a$$ congruente a $$3-b$$, o que é um absurdo! Note que $$a$$ e $$b$$ já são termos definidos da sequência então sua soma não pode ser um múltiplo de $$3$$, exatamente o que acontece quando $$a\equiv 3-b (mod 3)$$.
Concluímos que, escolhidos os dois primeiros dígitos, só existe uma forma fixa de termos uma permutação legal, como só estamos analisando os resíduos na divisão por $$3$$ até agora, então existem seis formas de escolhermos os dois primeiros dígitos (não podemos escolhê-los somando um múltiplo de $$3$$, o que elimina as escolhas $$0 – 0$$, $$1 – 2$$, $$2 – 1$$) e consequentemente seis permutações legais possíveis (olhando os restos módulo $$3$$). Temos as seguintes possibilidades de sequências de 6 resíduos consecutivos: (veja que há a mesma quantidade de restos de cada tipo)
– $$011022, 110220, 102201, 022011, 220110, 201102$$.
Para determinar as permutações legais com base nos números do conjunto basta analisarmos a permutação dos números com mesmo resíduo na divisão por $$3$$. A nossa análise anterior garantiu por meio da marcação dos resíduos como determinar se uma permutação é legal, a partir disso podemos determinar a quantidade total de permutações contando as possibilidades de trocarmos todos números com resíduo $$1$$ de “lugar”, assim como os de resíduo $$2$$ e $$3$$, supondo que a quantidade de números do conjunto seja $$6k$$ a quantidade de permutações dentro das posições de um mesmo resíduo será $$2k! $$, logo determinada uma permutação legal com base nos resíduos há $$(2k!)^3$$ formas de preenchê-la com os números do conjunto, como há seis permutações legais possíveis dos resíduos, então um conjunto com $$6k$$ elementos tem um total de $$6 \times (2k!)^3$$ permutações legais.
A partir disso resolvemos ambos itens:
(a) $${1,2,3,4,5,6}$$ tem $$6$$ elementos, logo $$6 \times (2!)^3 = 48$$ permutações legais.
(b) $${1,2,3,…,2016}$$ tem $$2016$$ elementos, logo $$6 \times (672!)^3$$ permutações legais.