2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Вентилятор
Сообщение08.01.2008, 10:10 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Задача известная, но здесь её вроде не постили. По крайней мере, мне найти не удалось.

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

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

 Профиль  
                  
 
 
Сообщение08.01.2008, 11:09 
Модератор
Аватара пользователя


11/01/06
5660
Каждую лопать можно представлять как корень $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).

 Профиль  
                  
 
 
Сообщение08.01.2008, 11:11 


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

 Профиль  
                  
 
 
Сообщение08.01.2008, 11:24 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение08.01.2008, 11:36 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
maxal писал(а):
Кстати, нулевые суммы корней из 1 мы обсуждали в этой теме:

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


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

 Профиль  
                  
 
 
Сообщение08.01.2008, 13:53 


23/01/07
3415
Новосибирск
Профессор Снэйп писал(а):
Для составного $k$ можно посчитать количество способов, которыми можно отламывать лопасти :)

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

 Профиль  
                  
 
 
Сообщение08.01.2008, 14:04 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Батороев писал(а):
Профессор Снэйп писал(а):
Для составного $k$ можно посчитать количество способов, которыми можно отламывать лопасти :)

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


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

 Профиль  
                  
 
 
Сообщение08.01.2008, 14:50 


23/01/07
3415
Новосибирск
Профессор Снэйп писал(а):
Нет, там более сложное выражение.

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

 Профиль  
                  
 
 
Сообщение08.01.2008, 18:43 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Батороев писал(а):
Не могли бы Вы подсчитать и сказать, сколько вариантов получается по "более сложным выражениям", например, при $ 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$ уже терпения не хватило :)

 Профиль  
                  
 
 
Сообщение08.01.2008, 19:11 
Заслуженный участник


05/09/05
515
Украина, Киев
Профессор Снэйп писал(а):
....

6 --- 4

......

12 --- 49

....

18 --- 499

.....

24 --- 4999




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

 Профиль  
                  
 
 
Сообщение08.01.2008, 19:18 


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

 Профиль  
                  
 
 
Сообщение08.01.2008, 19:25 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
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 секунд:

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


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

 Профиль  
                  
 
 
Сообщение08.01.2008, 22:09 
Заслуженный участник


09/02/06
4382
Москва
Можно посчитать так. Пусть 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}).$$

 Профиль  
                  
 
 
Сообщение08.01.2008, 23:53 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение09.01.2008, 05:26 
Заморожен
Аватара пользователя


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group