Questão
Olimpíada Brasileira de Matemática - Nível 2
2016
permutaca-1-2-3-12717c924d52
Discursiva
Uma permutação (a₁, a₂ , a₃, . . . , aₙ₋₁, aₙ) 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) e uma permutação legal dos números do conjunto {1, 2, 3, 4, 5, 6}. Entretanto, (1, 2, 5, 3, 4, 6) não e uma permutação legal do mesmo conjunto, pois os números 1 e 2 são vizinhos e sua soma e um múltiplo de 3. Além disso, outra razão para ela não ser legal, e 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.