(OBM-16) Uma permutação (
) dos números do conjunto 1 ,
é 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
.
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
. Suponha que o
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)
Para determinar as permutações legais com base nos números do conjunto
, 1,2, basta analisarmos a permutação dos números com mesmo resto na divisảo por 3. Como existem
maneiras de escolher os dois primeiros números e (2!)
formas de permutar os números de mesmo resto na divisão por 3 , segue que a quantidade de permutações legais de
é igual a
.
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
números cada com mesmo resto por 3 , segue que existem
permutaçōes legais.
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
a) Os restos por 3 são
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
Passo 1
O enunciado pede o número de permutações dos inteiros de
a
(e depois de
a
) tais que
- Nenhum par de termos consecutivos soma múltiplo de
. - Para qualquer termo interno, os seus dois vizinhos não diferem por múltiplo de
.
Vamos resolver agrupando os números pelos seus restos mod.
Passo 2
Classificamos os números do conjunto em três classes de restos módulo
:
A condição “nenhum par soma múltiplo de ” proíbe adjacências de restos
e
ou
.
A condição sobre os vizinhos de um termo impõe que, em qualquer tripla de restos , os valores
e
sejam distintos.
A condição “nenhum par soma múltiplo de
A condição sobre os vizinhos de um termo impõe que, em qualquer tripla de restos
Passo 3
Procuramos sequências de comprimento
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
Verifica-se que a única “forma” de restituir essas restrições (até deslocamentos cíclicos) é o padrão
e suas
rotações cíclicas:
Passo 4
Para cada uma das
sequências de restos, podemos permutar livremente os dois elementos de
, os dois de
e os dois de
. Isso dá
atribuições de valores concretos por padrão de restos.
Portanto, o total para é
Portanto, o total para
Passo 5
No caso
, temos 3 classes de restos de tamanho
. A estrutura das restrições força novamente um único padrão de restos (até
rotações cíclicas). Para cada padrão, permutamos dentro de cada classe em
maneiras. Logo,