(OBM-16) Uma permutação ( a_{1}, a_{2}, a_{3} \ldots ., a_{n-1}, a_{n} ) dos números do conjunto 1 , 2,3, \ldots, 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, \ldots, 2016.

Solução:

Para facilitar o entendimento da questão, todos os números serão trocados pelos seus restos na divisão por 3 .
a) Os restos por 3 são 0,1,2,01,2. Suponha que o 1^{\circ} número da permutação é 0 . O próximo número pode ser 1 ou 2 . Se for o 1 , o próximo número não pode ser 2 , já que a soma será múltiplo de 3 , mas também não pode ser 0 , uma vez que a diferença de dois vizinhos de um termo também não pode ser divisivel por 3, logo só pode ser novamente 1 e o processo se repete. Ocorre de forma análoga se escolhermos o 2 depois do 0 . Generalizando, se os dois primeiros números são a e b, o próximo não pode ser 3 - b nem a. Assim, escolhidos os dois primeiros dígitos, só existe uma forma de termos una permutação legal, como só estamos analisando os restos na divisão por 3, então existem seis formas de escolhermos os dois primeiros digitos. Temos as seguintes possibilidades de sequências de 6 restos 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 0,1,2,0, 1,2, basta analisarmos a permutação dos números com mesmo resto na divisảo por 3. Como existem 3.2=6 maneiras de escolher os dois primeiros números e (2!) { }^{3} formas de permutar os números de mesmo resto na divisão por 3 , segue que a quantidade de permutações legais de 1,2,3,4,5,6 é igual a 6 .(2!)^{3}=48.
b) Pode-se adaptar a ideia do item anterior para qualquer quantidade de números que seja múltiplo de 6, que é o caso de 2016. Depois da decisão dos dois primeiros números, a sequência dos restos por 3 está definida, bastando permutar os números que apresentam os mesmos restos por 3. nas respectivas posições. Como existem 3 conjuntos de 2016 / 3=672 números cada com mesmo resto por 3 , segue que existem 6 \times(672!)^{3} permutaçōes legais.

Passo 1

O enunciado pede o número de permutações dos inteiros de 1 a 6 (e depois de 1 a 2016) tais que
  1. Nenhum par de termos consecutivos soma múltiplo de 3.
  2. Para qualquer termo interno, os seus dois vizinhos não diferem por múltiplo de 3.
    Vamos resolver agrupando os números pelos seus restos mod 3.

Passo 2

Classificamos os números do conjunto em três classes de restos módulo 3:
\,C_{0}=\{3,6\},\;C_{1}=\{1,4\},\;C_{2}=\{2,5\}.
A condição “nenhum par soma múltiplo de 3” proíbe adjacências de restos (0,0) e (1,2) ou (2,1).
A condição sobre os vizinhos de um termo impõe que, em qualquer tripla de restos \bigl(c_{i-1},c_{i},c_{i+1}\bigr), os valores c_{i-1} e c_{i+1} sejam distintos.

Passo 3

Procuramos sequências de comprimento 6 com exatamente dois zeros, dois uns e dois dois, obedecendo às regras acima.
Verifica-se que a única “forma” de restituir essas restrições (até deslocamentos cíclicos) é o padrão
0,1,1,0,2,2
e suas 6 rotações cíclicas:
011022,\;110220,\;102201,\;022011,\;220110,\;201102.

Passo 4

Para cada uma das 6 sequências de restos, podemos permutar livremente os dois elementos de C_{0}, os dois de C_{1} e os dois de C_{2}. Isso dá (2!)^{3}=8 atribuições de valores concretos por padrão de restos.
Portanto, o total para n=6 é
6 \times (2!)^3 = 6 \times 8 = 48.

Passo 5

No caso n=2016, temos 3 classes de restos de tamanho 2016/3=672. A estrutura das restrições força novamente um único padrão de restos (até 6 rotações cíclicas). Para cada padrão, permutamos dentro de cada classe em (672!) maneiras. Logo,
6 \times (672!)^3.

Resposta

48 (para o conjunto de 1 a 6)
6\times(672!)^3 (para o conjunto de 1 a 2016)

Exercícios de Livros Relacionados