Вентилятор

[Профессор Снэйп]

Задача известная, но здесь её вроде не постили. По крайней мере, мне найти не удалось.

Имеется вентилятор с $k$ лопастями ($k$ натуральное, больше единицы). Одна лопасть отломилась. Техник хочет отломить ещё часть лопастей (но не все оставшиеся!) так, чтобы вентилятор мог работать (то есть чтобы центр масс оставшихся лопастей находился на оси вентилятора).

Доказать, что он сможет это сделать тогда и только тогда, когда число $k$ составное.

[maxal]

Каждую лопать можно представлять как корень $k$-й степени из 1. Неотломанные лопасти соответственно представляют собой некоторое собственное подмножество корней, и нахождение их центра масс на оси вентилятора соответствует равенству элементов этого подмножества нулю.

Покажем, что для простого $k$ никакое собственное подмножество корней $k$-й степени из 1 не имеет нулевую сумму. Пусть $r$ - примитивный корень, так что все корни представляются степенями $1, r^1, \dots, r^{k-1}$. Как хорошо известно, для простого $k$ минимальный многочлен, корнем которого является $r$, - это $1+x+\dots+x^{k-1}$. Если же сумма элементов некоторого собственного подмножества корней равна 0, то мы немедленно найдем многочлен степени меньшей $k-1$, корнем которого является $r$. Противоречие.

Для составного $k=m\cdot n$, где $m,n>1$, собственное подмножество корней $k$-й степени из 1 с нулевой суммой легко находится - например, это $\{ 1, r^m, r^{2m}, \dots, r^{(n-1)m}\}$ (которое по сути является множеством всех корней $n$-й степени из 1).

[Батороев]

"Будем рассуждать логически" (цитата из фильма):
Если $ k $ - простое, то отламывать придется $ k $ лопаток

[maxal]

Кстати, нулевые суммы корней из 1 мы обсуждали в этой теме:
http://dxdy.ru/viewtopic.php?t=8939
Там же есть ссылка на доказательство неприводимости кругового многочлена $1+x+\dots+x^{k-1}$ (для простого $k$).

[Профессор Снэйп]

maxal писал(а):

Кстати, нулевые суммы корней из 1 мы обсуждали в этой теме:

http://dxdy.ru/viewtopic.php?t=8939

Да, интересно. Для составного $k$ можно посчитать количество способов, которыми можно отламывать лопасти

[Батороев]

Профессор Снэйп писал(а):

Для составного $k$ можно посчитать количество способов, которыми можно отламывать лопасти

Вроде бы, $ k - \varphi(k) - 1 $, где $ \varphi(k) $ -функция Эйлера

[Профессор Снэйп]

Батороев писал(а):

Профессор Снэйп писал(а):

Для составного $k$ можно посчитать количество способов, которыми можно отламывать лопасти

Вроде бы, $ k - \varphi(k) - 1 $, где $ \varphi(k) $ -функция Эйлера

Нет, там более сложное выражение.

[Батороев]

Профессор Снэйп писал(а):

Нет, там более сложное выражение.

Не могли бы Вы подсчитать и сказать, сколько вариантов получается по "более сложным выражениям", например, при $ k = 12 $?

[Профессор Снэйп]

Батороев писал(а):

Не могли бы Вы подсчитать и сказать, сколько вариантов получается по "более сложным выражениям", например, при $ k = 12 $?

Судя по тем суровым зарубонам, которые можно прочесть по приведённой maxal'ом ссылке, подсчёт подобных количеств --- дело весьма нетривиальное. Нужно крепко врубаться в тему, чего делать совсем не хочется.

Не уверен, что там какие-то выражения в явном виде вообще возможны.

Для $k=12$ можно, конечно, и програмку быстро накатать, которая нужное количество подсчитает. Если Вы умеете программировать --- сделайте это самостоятельно. Если нет, то я, так и быть, сделаю это для Вас.

Добавлено спустя 2 часа 2 минуты 50 секунд:

Вот что у меня программа насчитала:

2 --- 0
3 --- 0
4 --- 1
5 --- 0
6 --- 4
7 --- 0
8 --- 7
9 --- 3
10 --- 16
11 --- 0
12 --- 49
13 --- 0
14 --- 64
15 --- 18
16 --- 127
17 --- 0
18 --- 499
19 --- 0
20 --- 577
21 --- 66
22 --- 1024
23 --- 0
24 --- 4999
25 --- 15
26 --- 4096
27 --- 363

Слева --- число $k$, справа --- количество способов, которыми техник может отломать оставшиеся лопасти вентилятора. Алгоритм самый тупой (полнопереборный), так что дождаться значения при $k = 28$ уже терпения не хватило

[Macavity]

Профессор Снэйп писал(а):

....

6 --- 4

......

12 --- 49

....

18 --- 499

.....

24 --- 4999

Значит ли это, что
30 --- 49999
36 --- 499999
и т.д.?

[Батороев]

Похоже, я что-то не допонимаю
Например, для $ k = 6 $, на мой взгляд, возможны только три варианта:
1-2
2-3
3-4,
где слева номер варианта, а справа количество отломленных лопастей.
Есть, конечно, четвертый - отломить все 6, но это будет уже не вентилятор, а какое-то точило для карандашиков.

[Профессор Снэйп]

Macavity писал(а):

Значит ли это, что
30 --- 49999
36 --- 499999
и т.д.?

Мне кажется, что вряд ли. Число способов, насколько я понял, сильно зависит от разложения $k$ на простые множители. Имеем

$6 = 2 \cdot 3$
$12 = 2^2 \cdot 3$
$18 = 2 \cdot 3^2$
$24 = 2^3 \cdot 3$

Все простые делители этих чисел --- двойки и тройки. Что начнёт происходить, когда появятся новые простые делители, сказать трудно.

Добавлено спустя 4 минуты 9 секунд:

Батороев писал(а):

Похоже, я что-то не допонимаю
Например, для $ k = 6 $, на мой взгляд, возможны только три варианта:
1-2
2-3
3-4,
где слева номер варианта, а справа количество отломленных лопастей.
Есть, конечно, четвертый - отломить все 6, но это будет уже не вентилятор, а какое-то точило для карандашиков.

Представим, что лопастей всего 6 и лопасть номер 1 уже отломана. Пусть они нумеруются "по кругу". Тогда варианты таковы: $\{ 4 \}$, $\{ 2,4,5 \}$, $\{ 3,4,6 \}$, $\{ 3,5 \}$. Всего 4 варианта

[Руст]

Можно посчитать так. Пусть d делитель k. Тогда все множества которые содержать с каждым элементом и любой, отличающийся на корень d -ой степени имеется ровно $2^{k/d -1}-1$. Поэтому надо вычислить сумму

$$\sum_{d|k} c(d)(2^{k/d -1}-1)$$

. Здесь c(d) поправка для того чтобы не считать многократно эту позицию по собственным делителям d.
Соответственно $c(d)=-\mu(d)$, т.е. искомое значение

$$\sum_{d|k,d>1} \mu(d)(1-2^{k/d -1}).$$

[maxal]

Что-то я не совсем понял, что конкретно вы считаете. Количество подмножеств корней с нулевой суммой различных с точностью до поворота?

Но как бы там ни было, формула Рустема и программка Профессора Снэйпа дают разные значения при $k=12$: соответственно 37 и 49. Кто наврал?

[Профессор Снэйп]

Я считаю количество способов, которыми техник может отламывать лопасти, как и было заявлено. То есть количество подмножеств корней с нулевой суммой, содержащих один заранее фиксированный корень (уже отломанную лопасть) и не равных всему множеству корней (как и требовалось в исходной задаче). И не с точностью до поворота, а просто количество.

Что именно я считаю, хорошо видно из моего примера для $k = 6$, который я приводил Батороеву.