Лемма Бернсайда

[noooob]

Сколькими способами можно составить бусы из 87 бусинок 4 различных цветов ( с точностью до поворотов и осевых симметрий)

Решение:

Расставим 87 точек, пронумеруем от 1 до 87. Образуется 87 угольник, назовем угол одинарного поворота за a.

Повороты (86 штук по 1 циклу):

$ R(a) = (1 \ 87 \ 86 \ 85 ... 2) $
$ R(2a) = (1 \ 86 \ 84 ... 2 \ 87 \ 85 ... 3) $
...
$ R(86a) = (1 \ 2 \ 3 \ 4 ... 87) $

$ R(87a) = id = (1)(2) ... (87) $ - 1 тождественное преобразование, 87 циклов.

Симметрии (относительно линии, проведенной из вершины и проходящей через середину противоположной стороны) :

$ Sl(1) = (1)(2 \ 87) ... (43 \ 44) $
...
$ Sl(87) = (87)(1 \ 86) ... (42 \ 43)$

- таких симметрий 87 штук, по 44 цикла.

следовательно

$ |G| = 86 + 1 + 87 $

следовательно,

$r = (1/174) \cdot ( 86 \cdot 4^1 + 1\cdot4^{87} + 87\cdot4^{44}) $

Но это число не является натуральным.

Где я не прав? Или что-то не так при подстановке в формулу?

Формула: $r(Gx) = (1 / |G|) \sum ( k \cdot g^d) $
где $k$ - количество преобразований
$g$ - количество цветов
$d$ - количество циклов

[sopor]

У Вас в поворотах ошибка.

-- 08.05.2013, 19:41 --

По вашей формуле, для поворота на $3\alpha$ существует всего 4 раскраски, которые сохраняются. Это не так.

[noooob]

Мои рассуждения:

Понятно, что для 87 выписывать все в лоб невозможно. Я выписал для 7 точек.

$ R(\varphi) : (1 \ 7 \ 6 \ 5 \ 4 \ 3 \ 2 )$
$ R(2\varphi) : (1 \ 6 \ 4 \ 2 \ 7 \ 5 \ 3 )$
$ R(3\varphi) : (1 \ 5 \ 2 \ 6 \ 3 \ 7 \ 4 )$
$ R(4\varphi) : (1 \ 4 \ 7 \ 3 \ 6 \ 2 \ 5 )$
$ R(5\varphi) : (1 \ 3 \ 5 \ 7 \ 2 \ 4 \ 6 )$
$ R(6\varphi) : (1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 )$
$ R(7\varphi) : (1)(2)(3)(4)(5)(6)(7)$

и посчитал, что для 87 будет так же. В этих рассуждениях есть ошибки?

-- 08.05.2013, 21:06 --

Кажется, что-то понял.

$ R(3\alpha) : (1 \ 85 \ 82 \ 79 \ 76 \ 73 ... 4)(2 \ 86 \ 83 \ 80 ... 5)(3 \ 87 \ 84 \ 81 ... 6) $

так?

-- 08.05.2013, 21:36 --

для $ 6a $ тоже 3 цикла. Для $ 9a$ тоже.

Можно ли предположить, что для всех $\{3 \ 9 \ 12 \ 15 \ 18 ... 81 \ 84\}$ будет это выполняться? не знаю, как проверить.. Для 6 и 9 проверял вручную.

[lena7]

С точки зрения любви к себе, можно не выписывать перестановки, а заметить, что поворот на угол $k\alpha$ оставляет неподвижными $4^{\text{НОД}(87,k)}$ раскрасок (докажите это).

[noooob]

Если это действительно так, то

$r = (1/174) \cdot ( 58 \cdot 4^1 + 28\cdot4^3 + 1\cdot4^{87} + 87\cdot4^{44}) $

Wolfram говорит, что число натуральное.

[lena7]

Почему 58? И ещё слагаемого не хватает.

[noooob]

28 поворотов, содержащих 3 цикла.
Номерами 3 6 9 12 и так далее до 84

Следовательно, 58 поворотов, содержащих 1 цикл.

-- 08.05.2013, 22:14 --

видимо, не прав..пойду думать дальше..

[lena7]

Советую всё же доказать утверждение, которое я привела выше. Затем останется найти кол-во чисел для каждого возможного НОДа. Кстати, $87=3\cdot 29$.

Для отражений и $\mathrm {id}$ число неподвижных раскрасок вы нашли верно.

[Nacuott]

А если только три бусинки разного цвета, а остальные одинакового, что тогда?

[lena7]

(Оффтоп)

Nacuott
Полностью вопрос сформулируйте. Если это не имеет прямого отношения к задаче, то лучше в другой теме.

[Nacuott]

lena7 в сообщении #721719 писал(а):

(Оффтоп)

Nacuott
Полностью вопрос сформулируйте. Если это не имеет прямого отношения к задаче, то лучше в другой теме.

Сколько существует способов составить бусы в этом случае?

[lena7]

Как вы думаете?

Кстати, ответ зависит от того, как понять это:

Nacuott в сообщении #721717 писал(а):

а остальные одинакового

Связан ли цвет "остальных" с первыми тремя? Например, подходит ли такая раскраска: одна бусина красная, другая зеленая, остальные синие?

[Nacuott]

Я имел ввиду- одна бусинка красная, одна-зеленая, одна-синяя, а остальные 84 шт. желтые.

[lena7]

Nacuott
Подход такой же, как в исходной задаче -- лемма Бернсайда. Ваша задача намного проще, ибо почти для всех преобразований неподвижных раскрасок не существует.

[noooob]

Как доказать, понятия не имею. Подскажите, каким методом доказываются подобные вещи?

Количество циклов посчитал:

НОД$(87, 3k) = 3$, таких будет (целая часть от деления 87 на 3) - 28 штук по 3 цикла.
далее
НОД$(87, 29k) = 29 $ - еще 2 штуки по 29 циклов.

В итоге:

$ r = (1/174)(28\cdot4^3 + 2\cdot4^{29} + 1\cdot4^{87} + 56\cdot4^1 + 87\cdot4^{44})$

преобразуем

$ = (7\cdot2^7 + 2^{58} + 2^{173} +7\cdot2^4 87\cdot2^{87})/87$

находим остатки от деления
$ 7\cdot2^7 \mod 87 = 26 $
$ 7\cdot2^4 \mod 87 = 25 $

$ 2^{58} \mod 87 = ? $

Рассуждения: т.к. 2 в любой степени и 87 взаимно просто,
$ (2^{56} \cdot 2^2) \mod 87 = 4 $
т.к. 56 - ф-ция Эйлера от 87 $\Rightarrow$ $ 2^{56}\mod 87 = 1 $

Для 173 аналогичные рассуждения.
$ (2^{56} \cdot 2^{56} \cdot 2^{56} \cdot 2^{5}) \mod 87 = 2^5 = 32 $

Суммируем остатки, $26+25+4+32 = 87$. То есть делиться на 87 без остатка.
Получилось натуральное число. Это конечно не говорит о правильности.. Но если бы не поделилось нацело, то уж точно не правильно.