Разделы 
Дополнительно
Задача по математике - 3754
2019-06-16 
В вершинах правильного $n$-угольника с центром в точке $О$ расставлены числа (+1) и (-1). За один шаг разрешается изменить знак у всех чисел, стоящих в вершинах какого-либо правильного $k$-угольника с центром $О$ (при этом мы допускаем и 2-угольники, понимая под 2-угольником отрезок с серединой в точке $О$). Докажите, что в случаях а), б), в) существует такое первоначальное расположение (+1) и (-1), что из него ни за какое число шагов нельзя получить набор из одних (+1):
а) $n = 15$;
б) $n = 30$;
в) $n$ - любое число, большее 2;
г) Попробуйте пояснить для произвольного $n$, чему равно наибольшее число $k(n)$ различных расстановок (+1) и (-1), среди которых ни одну нельзя получить из другой за несколько шагов. Докажите, например, что $K(200) = 2^{80}$.
Решение:
Отметим сначала несколько фактов, относящихся к случаю любого натурального $n$. Существует всего $2n$ расстановок чисел +1 и -1 в вершинах правильного $n$-угольника. Будем называть две расстановки эквивалентными, если от одной из них к другой (а стало быть, и обратно) можно перейти указанными в условии операциями - изменением знаков в вершинах правильных $n$-угольников. Любые две операции такого типа «коммутируют» - результат не зависит от порядка, в котором они выполняются; повторение любой операции дважды также можно исключить - оно эквивалентно тождественной операции, не меняющей расстановки. При этом можно ограничиться лишь операциями изменения знаков в вершинах правильных $p$-угольников с простым числом вершин $p$ (назовем их «образующими»); множество вершин правильного $n$-угольника при любом $n$, делящемся на $p$, можно разбить на $n/p$ образующих $p$-угольников.
Прежде чем двигаться дальше, рассмотрим конкретные задачи.
а) При $n = 15$ существует всего 8 образующих $p$-угольников: 5 треугольников и 3 пятиугольника. Единичную (состоящую из всех +1) расстановку обозначим через $E$. Любая эквивалентная $E$ расстановка определяется указанием некоторого подмножества из 8 этих $p$-угольников; различных подмножеств (включая пустое) существует 28 - это меньше, чем общее число $2^{15}$ расстановок» Поэтому существуют расстановки, не эквивалентные $E$.
б) При $n = 30$ общее число образующих $p$-угольников равно $15 + 10 + 6 = 31$, так что для решения задачи нужны дополнительные соображения. Заметим, что можно ограничиться меньшим числом образующих: например, из каждой пары симметричных относительно центра треугольников (и пятиугольников) можно оставить лишь один - изменение знаков в нем, а также в трех (пяти) «двуугольниках», содержащих его вершины, эквивалентно изменению знаков в другом, ему симметричном. Остается $15 + 5 + 3 = 23$ образующих, таким образом, существует не более $2^{23} < 2^{30}$ расстановок, эквивалентных $E$.
в) Покажем, как для любого $n$ найти точное количество $T(n)$ расстановок, эквивалентных $E$ Заметим, что количество расстановок, эквивалентных какой-то другой расстановке $A$ из + 1 и -1, также равно $Т(n)$: все они получаются почленным умножением знаков расстановки $A$ на любую расстановку из класса эквивалентных $E$. Обозначим через $k(n)$ число «классов эквивалентности» - максимальное количество попарно неэквивалентных друг другу расстановок; тогда
$k(n) = \frac{2^{n}}{T (n)}$.
Пусть $n$ содержит $s$ разных простых множителей:
$n = p_1^{ \alpha_1} p_2^{ \alpha_2} \cdots p_s^{ \alpha_s}$ (*).
Положим $p_1p_2 \cdots p_s = q; n/q = m$. Разобьем правильный $n$-угольник на $m$ правильных $q$-угольников. Задача вычисления $T(n)$ сводится к более простой задаче вычисления $T(q) = T(p_1 \cdots p_s)$; ведь каждый из образующих $p_i$-угольников содержится лишь в одном из $q$-угольников, - другими словами, происходящие в разных $q$-угольниках изменения знаков независимы, поэтому
$T (n) = (T(q))^m, K(n) = (K(q))^m$.
Начнем со случая $s = 2$: пусть $n = p_1p_2$. Занумеруем вершины $n$-угольника числами $0, 1, \cdots, n - 1$. Запишем эти числа в таблицу $p_1 \times p_2$, так, что числа в одном столбце дают одинаковый остаток при делении на $p_1$, в одной строке - при делении на $p_2$. Это можно сделать, потому что пара остатков $(r_1, r_2)$ от деления на $p_1$ и $p_2$ однозначно определяет номер от 0 до $n$ (рис.). Расстановкам чисел +1 и -1 в точках на окружности соответствуют расстановки чисел $\sigma (r_1, r_2) = + 1$ и -1 в клетках таблицы ($r_1$ - номер строки, $r_2$ - номер столбца), изменению знаков в $P_1$ и $р_2$-угольниках - изменение знаков $\sigma$ в строках и столбцах величина произведения
$\sigma (r_1, r_2) \sigma (0, r_2) \sigma (r_1, 0) \sigma (0,0)$
сохраняется (набор таких величин для всех $r_1, r_2), 1 \leq r_1 \leq p_1 - 1, 1 \leq r_2 \leq p_2 - 1$ определяет класс эквивалентности). Поэтому
$K (p_1p_2) = 2^{(p_1 - 1)(p_2 - 1)}, T (p_1p_2) = 2^{p_1 + p_2 - 1}$.
В частности, $K (15) = 2^8, T(15) = 2^7; K(10) = 2^4$. Последнее равенство позволяет найти $K (200): n = 200 = 2^3 \cdot 5^2, q = 10, m = 20, K(200) = (K(10)^20 = 2^{4 \cdot 20} = 2^{80}$.
Аналогичные соображения позволяют найти $K(n)$ для случая любого $s$. Пусть $q = p_1p_2 \cdots p_s$; номер $k$ от 0 до $q - 1$ однозначно определяется остатками $r_1, r_2, \cdots, r_s$ от деления $q$ на $p_1, p_2, \cdots, p_s$ («китайская теорема об остатках»); с расстановками $\sigma (r_1, r_2, \cdots, r_s)$ - функциями на множестве наборов $r_i$ и $0 \leq r_i \leq p_1 - 1 (1 \leq i \leq s$, принимающими значения + 1 и -1, - разрешено проделывать операции одновременной замены знаков в одном «ряду», состоящем из $p_i$ наборов, у которых $i$-я координата $n$ произвольна - меняется от 0 до $p_i - 1$, а остальные $s - 1$ чисел $r_i$ фиксированы (для каждого $i = 1, 2, \cdots, s$); этими операциями любая расстановка сводится к такой, для которой $\sigma (r_1, r_2, \cdots, r_s) = +l$, если хоть одно $r_i$ равно 0; полученные приведенные расстановки неэквивалентны (сохраняется произведение $2^s$ значений $\sigma$ для наборов, получающихся из данного заменой некоторых координат на нули). Выпишем ответ для $q = p_1p_2 \cdots p_s$ и для любого $n = qm$ вида (*):
$K(q) - 2^{(p_1 - 1) \cdots (p_S - 1)}; K(n) = 2^{\phi (n)}$, где $\phi (n) = n \left ( 1 - \frac{1}{p_1} \right ) \cdots \left ( 1 - \frac{1}{ p_s} \right )$.
В частности, $K(30) = 2^8,T (30) = 2^{22}$.
Возникшая здесь несколько неожиданно функция $\phi(n)$ хорошо известна в теории чисел: это - функция Эйлера, выражающая количество натуральных чисел, меньших $n$ и взаимно простых с ним.
В вершинах правильного $n$-угольника с центром в точке $О$ расставлены числа (+1) и (-1). За один шаг разрешается изменить знак у всех чисел, стоящих в вершинах какого-либо правильного $k$-угольника с центром $О$ (при этом мы допускаем и 2-угольники, понимая под 2-угольником отрезок с серединой в точке $О$). Докажите, что в случаях а), б), в) существует такое первоначальное расположение (+1) и (-1), что из него ни за какое число шагов нельзя получить набор из одних (+1):
а) $n = 15$;
б) $n = 30$;
в) $n$ - любое число, большее 2;
г) Попробуйте пояснить для произвольного $n$, чему равно наибольшее число $k(n)$ различных расстановок (+1) и (-1), среди которых ни одну нельзя получить из другой за несколько шагов. Докажите, например, что $K(200) = 2^{80}$.
Решение:
Отметим сначала несколько фактов, относящихся к случаю любого натурального $n$. Существует всего $2n$ расстановок чисел +1 и -1 в вершинах правильного $n$-угольника. Будем называть две расстановки эквивалентными, если от одной из них к другой (а стало быть, и обратно) можно перейти указанными в условии операциями - изменением знаков в вершинах правильных $n$-угольников. Любые две операции такого типа «коммутируют» - результат не зависит от порядка, в котором они выполняются; повторение любой операции дважды также можно исключить - оно эквивалентно тождественной операции, не меняющей расстановки. При этом можно ограничиться лишь операциями изменения знаков в вершинах правильных $p$-угольников с простым числом вершин $p$ (назовем их «образующими»); множество вершин правильного $n$-угольника при любом $n$, делящемся на $p$, можно разбить на $n/p$ образующих $p$-угольников.
Прежде чем двигаться дальше, рассмотрим конкретные задачи.
а) При $n = 15$ существует всего 8 образующих $p$-угольников: 5 треугольников и 3 пятиугольника. Единичную (состоящую из всех +1) расстановку обозначим через $E$. Любая эквивалентная $E$ расстановка определяется указанием некоторого подмножества из 8 этих $p$-угольников; различных подмножеств (включая пустое) существует 28 - это меньше, чем общее число $2^{15}$ расстановок» Поэтому существуют расстановки, не эквивалентные $E$.
б) При $n = 30$ общее число образующих $p$-угольников равно $15 + 10 + 6 = 31$, так что для решения задачи нужны дополнительные соображения. Заметим, что можно ограничиться меньшим числом образующих: например, из каждой пары симметричных относительно центра треугольников (и пятиугольников) можно оставить лишь один - изменение знаков в нем, а также в трех (пяти) «двуугольниках», содержащих его вершины, эквивалентно изменению знаков в другом, ему симметричном. Остается $15 + 5 + 3 = 23$ образующих, таким образом, существует не более $2^{23} < 2^{30}$ расстановок, эквивалентных $E$.
в) Покажем, как для любого $n$ найти точное количество $T(n)$ расстановок, эквивалентных $E$ Заметим, что количество расстановок, эквивалентных какой-то другой расстановке $A$ из + 1 и -1, также равно $Т(n)$: все они получаются почленным умножением знаков расстановки $A$ на любую расстановку из класса эквивалентных $E$. Обозначим через $k(n)$ число «классов эквивалентности» - максимальное количество попарно неэквивалентных друг другу расстановок; тогда
$k(n) = \frac{2^{n}}{T (n)}$.
Пусть $n$ содержит $s$ разных простых множителей:
$n = p_1^{ \alpha_1} p_2^{ \alpha_2} \cdots p_s^{ \alpha_s}$ (*).
Положим $p_1p_2 \cdots p_s = q; n/q = m$. Разобьем правильный $n$-угольник на $m$ правильных $q$-угольников. Задача вычисления $T(n)$ сводится к более простой задаче вычисления $T(q) = T(p_1 \cdots p_s)$; ведь каждый из образующих $p_i$-угольников содержится лишь в одном из $q$-угольников, - другими словами, происходящие в разных $q$-угольниках изменения знаков независимы, поэтому
$T (n) = (T(q))^m, K(n) = (K(q))^m$.
Начнем со случая $s = 2$: пусть $n = p_1p_2$. Занумеруем вершины $n$-угольника числами $0, 1, \cdots, n - 1$. Запишем эти числа в таблицу $p_1 \times p_2$, так, что числа в одном столбце дают одинаковый остаток при делении на $p_1$, в одной строке - при делении на $p_2$. Это можно сделать, потому что пара остатков $(r_1, r_2)$ от деления на $p_1$ и $p_2$ однозначно определяет номер от 0 до $n$ (рис.). Расстановкам чисел +1 и -1 в точках на окружности соответствуют расстановки чисел $\sigma (r_1, r_2) = + 1$ и -1 в клетках таблицы ($r_1$ - номер строки, $r_2$ - номер столбца), изменению знаков в $P_1$ и $р_2$-угольниках - изменение знаков $\sigma$ в строках и столбцах величина произведения
$\sigma (r_1, r_2) \sigma (0, r_2) \sigma (r_1, 0) \sigma (0,0)$
сохраняется (набор таких величин для всех $r_1, r_2), 1 \leq r_1 \leq p_1 - 1, 1 \leq r_2 \leq p_2 - 1$ определяет класс эквивалентности). Поэтому
$K (p_1p_2) = 2^{(p_1 - 1)(p_2 - 1)}, T (p_1p_2) = 2^{p_1 + p_2 - 1}$.
В частности, $K (15) = 2^8, T(15) = 2^7; K(10) = 2^4$. Последнее равенство позволяет найти $K (200): n = 200 = 2^3 \cdot 5^2, q = 10, m = 20, K(200) = (K(10)^20 = 2^{4 \cdot 20} = 2^{80}$.
Аналогичные соображения позволяют найти $K(n)$ для случая любого $s$. Пусть $q = p_1p_2 \cdots p_s$; номер $k$ от 0 до $q - 1$ однозначно определяется остатками $r_1, r_2, \cdots, r_s$ от деления $q$ на $p_1, p_2, \cdots, p_s$ («китайская теорема об остатках»); с расстановками $\sigma (r_1, r_2, \cdots, r_s)$ - функциями на множестве наборов $r_i$ и $0 \leq r_i \leq p_1 - 1 (1 \leq i \leq s$, принимающими значения + 1 и -1, - разрешено проделывать операции одновременной замены знаков в одном «ряду», состоящем из $p_i$ наборов, у которых $i$-я координата $n$ произвольна - меняется от 0 до $p_i - 1$, а остальные $s - 1$ чисел $r_i$ фиксированы (для каждого $i = 1, 2, \cdots, s$); этими операциями любая расстановка сводится к такой, для которой $\sigma (r_1, r_2, \cdots, r_s) = +l$, если хоть одно $r_i$ равно 0; полученные приведенные расстановки неэквивалентны (сохраняется произведение $2^s$ значений $\sigma$ для наборов, получающихся из данного заменой некоторых координат на нули). Выпишем ответ для $q = p_1p_2 \cdots p_s$ и для любого $n = qm$ вида (*):
$K(q) - 2^{(p_1 - 1) \cdots (p_S - 1)}; K(n) = 2^{\phi (n)}$, где $\phi (n) = n \left ( 1 - \frac{1}{p_1} \right ) \cdots \left ( 1 - \frac{1}{ p_s} \right )$.
В частности, $K(30) = 2^8,T (30) = 2^{22}$.
Возникшая здесь несколько неожиданно функция $\phi(n)$ хорошо известна в теории чисел: это - функция Эйлера, выражающая количество натуральных чисел, меньших $n$ и взаимно простых с ним.
