MathDB

In each vertex of a regular

n

-gon, there is a fortress. At the same moment, each fortress shoots one of the two nearest fortresses and hits it. The result of the shooting is the set of the hit fortresses; we do not distinguish whether a fortress was hit once or twice. Let

P(n)

be the number of possible results of the shooting. Prove that for every positive integer

k\geqslant 3

P(k)

and

P(k+1)

are relatively prime.
(4th Middle European Mathematical Olympiad, Team Competition, Problem 3)

Problem Statement