Q21 Matemática  (Tournament Of Towns 2019)

No plano da grade são construídas todas as linhas quebradas possíveis com as seguintes propriedades: cada uma delas começa no ponto $(0,0)$, tem todos os seus vértices em pontos inteiros, cada segmento linear vai para cima ou para a direita ao longo do linhas de grade. Para cada linha quebrada, considere o verme correspondente, o subconjunto do plano que consiste em todas as células que compartilham pelo menos um ponto com a linha quebrada. Prove que o número de minhocas que podem ser divididas em dominós (retângulos $2\times 1$ e $1\times 2$) de maneiras exatamente diferentes $n>2$ é igual ao número de inteiros positivos menores que n e relativamente primo de $n$. (Ilke Chanakchi, Ralf Schiffler)