OBM 2016 - Nível 2 - P5

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.