В вершинах правильного $n$-угольника с центром в точке $O$ расставлены числа ($+1$) и ($-1$). За один шаг разрешается изменить знак у всех чисел, стоящих в вершинах какого-либо правильного $k$-угольника с центром $O$ (при этом мы допускаем и 2-угольники, понимая под 2-угольником отрезок с серединой в точке $O$). Докажите, что в случаях а), б), в) существует такое первоначальное расположение ($+1$) и ($-1$), что из него ни за какое число шагов нельзя получить набор из одних ($+1$):
$n=15$,
$n=30$,
$n$ — любое целое число, большее 2.
Попробуйте выяснить для произвольного $n$, сколько существует различных расстановок ($+1$) и ($-1$) таких, что никакую из них нельзя получить ни из какой другой за несколько шагов. Докажите, например, что для $n=2100$ существует $2^{480}$ таких расстановок.
С. В. Фомин
Всесоюзная математическая олимпиада школьников (1976 год, 10 класс)
Заметим, что конечная расстановка зависит от исходной расстановки и того, какие многоугольники выбирались, но не зависит от порядка, в котором это делалось. Действительно, в каждой вершине стоит то же число, что и в начальной расстановке, если эта вершина попала в чётное число многоугольников, и число, противоположное по знаку, — если в нечётное; порядок, тем самым, несуществен. Кроме того, ясно, что в одном и том же многоугольнике производить замену знаков более одного раза не имеет смысла.
Назовём две расстановки эквивалентными, если они могут быть получены друг из друга (если расстановка $N$ может быть получена из расстановки $M$, то и наоборот, $M$ может быть получена из $N$). Множество всех расстановок, эквивалентных какой‑нибудь расстановке, называется классом эквивалентности (или просто «классом»), порождённым этой расстановкой. Расстановки, попавшие в один класс эквивалентности, эквивалентны (так как от любой из них можно перейти к любой через расстановку, порождающую этот класс), а расстановки из разных классов — не эквивалентны.
Оказывается, что во всех классах эквивалентности поровну расстановок. Действительно, пусть один класс порождён расстановкой $N$, а другой — расстановкой $M$. Тогда элементу первого класса — расстановке, получающейся из $N$ в результате замен знаков в каких‑то многоугольниках, мы сопоставим элемент второго класса — расстановку, получающуюся из $M$ в результате замен знаков в тех же многоугольниках. Полученное соответствие между элементами этих двух классов даёт возможность утверждать, что в этих классах поровну элементов.
В задачах а)—в) утверждается, что не все элементы попали в один класс, а в г) спрашивается, сколько всего классов. Обозначим общее количество классов через $F(n)$, а количество элементов в (каком угодно) классе через $f(n)$. Поскольку всего расстановок $2^n$, то $F(n)=\dfrac{2^n}{f(n)}$, так что для нахождения $F(n)$ достаточно найти количество расстановок в каком‑нибудь одном классе. Подсчитаем число различных расстановок в классе, порождаемом расстановкой из одних единиц.
Заметим, что всякий $pq$-угольник ($p$ и $q$ — натуральные числа, большие 1) можно разбить на $p$ штук $q$-угольников; как это сделать, видно из рисунка 1. Мы можем ограничиться выбором многоугольников лишь с простым числом вершин: остальные многоугольники можно разбить на такие, и вместо замены знаков в вершинах «непростого» многоугольника произвести её во всех его, уже «простых», многоугольниках разбиения.
Рис. 1. 15-угольник разбит на три 5-угольника.Рис. 2. 18-угольник разбит на три 6-угольника. Любой 3-угольник содежрится в 6-угольнике.Рис. 3. В 15-угольнике 3-угольник и 5-угольник пересекаются по одной вершине
Заметим теперь, что если $p$ — простое число, то $f(p)=2$, а стало быть
$$
F(p)=2^{p-1}.\tag1
$$
Начнём с решения задачи г).
Пусть $n=bp$, где $b$ — натуральное, $p$ — простое. Попытаемся выразить $f(n)$ через $f(b)$, пользуясь разбиением $n$-угольника на $b$-угольники. Прежде всего выясним, что представляют собой пересечения $b$-угольников с выбираемыми многоугольниками. Если в выбранном многоугольнике $q$ вершин, и $b$ делится на $q$, то, очевидно, этот выбранный $q$-угольник целиком содержится в некотором $b$-угольнике (рис. 2 — напоминаем о смысле, в котором употребляется слово «многоугольник»!).
Если же $b$ не делится на (простое!) $q$, то, как нетрудно доказать, этот $q$-угольник с каждым $b$-угольником имеет ровно одну общую вершину.
Пусть сначала $b$ делится на$p$. Тогда $b$ делится на все простые делители $n$, и каждый выбираемый многоугольник целиком содержится в некотором $b$-угольнике, так что в этом случае можно считать, что операции перемены знаков происходят независимо в каждом $b$-угольнике; следовательно,
$$
f(n)=[f(b)]^p.\tag2
$$
Пусть теперь $b$ не делится на$p$. Раскрасим каждый из $b$-угольников в свой цвет, как на рисунке 3. Тогда каждый из $b$-угольников будет иметь по одной вершине каждого цвета.
Разобьём наш процесс на два этапа — на первом этапе будем выбирать $p$-угольники, на втором — остальные $q$-угольники ($q$ — простые делители $n$, $q\ne p$). На первом этапе изменение знака происходит одновременно для всех вершин одного цвета; тем самым после первого этапа во всех $b$-угольниках будет одна и та же расстановка чисел $+1$ и $-1$, причём эта расстановка может быть какой угодно. (Напомним, что начинаем мы с расстановки из одних единиц. Здесь и ниже мы считаем, что $b$-угольники совмещаются друг с другом поворотом так, что вершины одного цвета совпадают.)
На втором этапе все операции происходят уже внутри отдельных $b$-угольников (так как все простые делители $n$, отличные от $p$, являются и делителями $b$). Поэтому после второго этапа расстановки внутри $b$-угольников эквивалентны (поскольку они получаются из одной и той же), и вообще всякая расстановка, для которой расстановки внутри всех $b$-угольников эквивалентны, может быть получена из исходной расстановки. Подсчитаем число $f(n)$ таких расстановок.
Внутри первого $b$-угольника $+1$ и $-1$ можно расставить $2^b$ способами, после чего в каждом из $(p-1)$ оставшихся $b$-угольников можно изменить расстановку $f(b)$ способами. Итак,
$$
f(n)=2^b\cdot[f(b)]^{p-1}.\tag3
$$
Мы доказали, что при $b$, делящемся на $p$, имеет место формула (2), а при $b$, не делящемся на $p$, — формула (3).
При помощи формул (1), (2) и (3) можно последовательно вычислять $f(n)$ и $F(n)$ для различных $n$. Например, найдём $F(2100)$. По формуле (1) $f(5)=2$. По формулам (2) и (3) имеем:
$$\begin{gather*}
f(25)=2^5,\quad f(50)=2^{25}\cdot2^5=2^{30},\quad f(100)=(2^{30})^2=2^{60},\\
f(300)=2^{100}\cdot(2^{60})^2=2^{220},\quad f(2100)=2^{300}\cdot(2^{220})^6=2^{16320},
\end{gather*}$$
откуда $F(2100)=\dfrac{2^{2100}}{2^{1620}}=2^{480}$.
В общем случае читатель при помощи формул (1) и (3) может (по индукции) вывести формулу
$$
F(n)=2^{\phi(n)},\quad\text{где}~\phi(n)=n\left(1-\dfrac1{p_1}\right)\ldots\left(1-\dfrac1{p_k}\right),
$$
а $p_1$, $\ldots$, $p_k$ — все различные простые делители $n$. Интересно, что той же формулой $\phi(n)$ выражается количество натуральных чисел, меньших $n$ и взаимно простых с $n$ ($\phi$ называется «функцией Эйлера»). Разумеется, интересно понять, почему здесь возникают одинаковые формулы, и использовать это совпадение для поисков более красивого решения задачи М395, и, быть может, для доказательства формулы для функции Эйлера (оно тоже не слишком просто — см. статью С. Г. Гиндикина «Малая теорема Ферма», «Квант», 1972, № 10, с. 2).
