Q7 Matemática  (Middle European Mathematical Olympiad 2010)

Em cada vértice de um $n$-gon regular, existe uma fortaleza. No mesmo momento, cada fortaleza atira em uma das duas fortalezas mais próximas e a atinge. O resultado do disparo é o conjunto das fortalezas atingidas; não distinguimos se uma fortaleza foi atingida uma ou duas vezes. Seja $P(n)$ o número de resultados possíveis do tiro. Prove que para todo inteiro positivo $k⩾3$, $P(k)$ e $P(k+1)$ são relativamente primos. (4ª Olimpíada de Matemática da Europa Central, Competição por Equipes, Problema 3)