RU-ALLRUSSIAN 1976 Problem 14

You are given a regular n- gon. Each vertex is marked $+1$ or - 1. A move consists of changing the sign of all the vertices which form a regular k- gon for some $1 < k \ll = n$ . [A regular 2- gon means two vertices which have the center of the n- gon as their midpoint.]. For example, if we label the vertices of a regular 6- gon 1, 2, 3, 4, 5, 6, then you can change the sign of {1, 4}, {2, 5}, {3, 6}, {1, 3, 5}, {2, 4, 6} or {1, 2, 3, 4, 5, 6}. Show that for (1) $n = 15$ , (2) $n = 30$ , (3) any $n > 2$ , we can find some initial marking which cannot be changed to all $+1$ by any series of

moves. Let f(n) be the largest number of markings, so that no one can be obtained from any other by any series of moves. Show that $\mathrm{f}(200) = 2^{80}$ .