Problema 5
Uma permutação dos números do conjunto é legal se não existem dois termos consecutivos cuja soma é um múltiplo de e se os dois vizinhos de um termo qualquer não diferem por um múltiplo de . Por exemplo, é uma permutação legal dos números do conjunto . Entretanto, não é uma permutação legal do mesmo conjunto, pois os números e são vizinhos e sua soma é um múltiplo de . Além disso, outra razão para ela não ser legal, é que os vizinhos do número , que são o e o , diferem por um múltiplo de .
a) Determine o número de permutações legais do conjunto .
b) Determine o número de permutações legais do conjunto .
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 . Mostraremos que é possível determinar com base nos resíduos a quantidade de permutações legais:
Se dispomos do dígito , então o próximo dígito pode ser ou , 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 : o próximo dígito não pode ser , já que a soma resultará num múltiplo de , também não pode ser , já que a diferença de dois vizinhos de um termo também não pode ser divisível por , logo só pode ser novamente e o processo se repete. Da mesma forma se escolhermos o . Isso acontece pois, suponha que tenhamos determinado os dois últimos dígitos da sequência e esses sejam e , então o próximo dígito não pode ser (que somado com resulta num múltiplo de ) nem (que difere zero de , ou seja, temos uma diferença divisível por ), logo há dois casos a considerar:
- incongruente a , então não temos escolha e o número está determinado, como queremos demonstrar!
- congruente a , o que é um absurdo! Note que e já são termos definidos da sequência então sua soma não pode ser um múltiplo de , exatamente o que acontece quando .
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 até agora, então existem seis formas de escolhermos os dois primeiros dígitos (não podemos escolhê-los somando um múltiplo de , o que elimina as escolhas , , ) e consequentemente seis permutações legais possíveis (olhando os restos módulo ). Temos as seguintes possibilidades de sequências de 6 resíduos 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 basta analisarmos a permutação dos números com mesmo resíduo na divisão por . 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 de “lugar”, assim como os de resíduo e , supondo que a quantidade de números do conjunto seja a quantidade de permutações dentro das posições de um mesmo resíduo será , logo determinada uma permutação legal com base nos resíduos há 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 elementos tem um total de permutações legais.
A partir disso resolvemos ambos itens:
(a) tem elementos, logo permutações legais.
(b) tem elementos, logo permutações legais.