Задача об ожерельях - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:42:17Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:28, 1 сентября 2022

2022-09-01T03:28:17Z

5.18.144.53: /* Алгоритм решения задачи про ожерелья */

2016-01-07T20:55:49Z

‎Алгоритм решения задачи про ожерелья

5.18.144.53: /* Алгоритм решения задачи про ожерелья */

2016-01-07T20:55:05Z

‎Алгоритм решения задачи про ожерелья

5.18.144.53: /* Алгоритм решения задачи про ожерелья с отражениями */

2016-01-07T20:42:45Z

‎Алгоритм решения задачи про ожерелья с отражениями

5.18.144.53 в 20:38, 7 января 2016

2016-01-07T20:38:55Z

5.18.144.53: /* Алгоритм решения задачи про ожерелья с отражениями */

2016-01-07T20:37:50Z

‎Алгоритм решения задачи про ожерелья с отражениями

5.18.144.53: /* Алгоритм решения задачи про ожерелья */

2016-01-07T20:35:16Z

‎Алгоритм решения задачи про ожерелья

5.18.144.53: /* Источники информации */

2016-01-07T20:32:53Z

‎Источники информации

5.18.144.53: /* Алгоритм решения задачи про ожерелья */

2016-01-07T20:16:27Z

‎Алгоритм решения задачи про ожерелья

← Предыдущая		Версия 16:42, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Задача		{{Задача
	\|definition=		\|definition=

← Предыдущая		Версия 03:28, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Задача		{{Задача
	\|definition=		\|definition=

← Предыдущая		Версия 20:55, 7 января 2016
Строка 28:		Строка 28:


−	Тогда <tex>\|C\| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{q\|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>	+	Тогда <tex>\|C\| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{q\|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.

	== Алгоритм решения задачи про ожерелья с отражениями==		== Алгоритм решения задачи про ожерелья с отражениями==

← Предыдущая		Версия 20:55, 7 января 2016
Строка 25:		Строка 25:


−	Если раскраски ожерелья одинаковые, то они принадлежат одной [[Орбита\|орбите]], т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа\|лемме Бёрнсайда]], число орбит равняется <tex>\dfrac{n}{p}=\operatorname{gcd}(n,i)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex>, и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum\limits_{i=1}^{n}N_i=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}</tex>. В последней сумме <tex>\varphi(n)</tex> слагаемых <tex>(\varphi(n)</tex> {{---}} [[Функция Эйлера\|функция Эйлера]]<tex>)</tex>, для которых <tex>\operatorname{gcd}(n,i)=1</tex>. Если же <tex>\operatorname{gcd}(n,i)=q</tex>, то <tex>\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=1</tex>. Чтобы определить количество таких <tex>i</tex>, меньших <tex>n</tex>, нужно перебрать числа вида <tex>i=lq,\,0\leqslant l\leqslant \dfrac{n}{q}</tex> и проверять их на условие <tex>1=\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=\operatorname{gcd}\left(\dfrac{n}{q},l\right)</tex>. Таких чисел, очевидно, <tex>\varphi\left(\dfrac{n}{q}\right)</tex>(по определению <tex>\varphi(n)</tex>). Поэтому сумму можно заменить: <tex>S=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum\limits_{q\|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.	+	Если раскраски ожерелья одинаковые, то они принадлежат одной [[Орбита\|орбите]], т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа\|лемме Бёрнсайда]], число орбит равняется <tex>\dfrac{n}{p}=\operatorname{gcd}(n,i)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex>, и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum\limits_{i=1}^{n}N_i=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}</tex>. В последней сумме <tex>\varphi(n)</tex> слагаемых <tex>(\varphi(n)</tex> {{---}} [[Функция Эйлера\|функция Эйлера]]<tex>)</tex>, для которых <tex>\operatorname{gcd}(n,i)=1</tex>. Если же <tex>\operatorname{gcd}(n,i)=q</tex>, то <tex>\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=1</tex>. Чтобы определить количество таких <tex>i</tex>, меньших <tex>n</tex>, нужно перебрать числа вида <tex>i=lq,\,0\leqslant l\leqslant \dfrac{n}{q}</tex> и проверять их на условие <tex>1=\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=\operatorname{gcd}\left(\dfrac{n}{q},l\right)</tex>. Таких чисел, очевидно, <tex>\varphi\left(\dfrac{n}{q}\right)</tex> (по определению <tex>\varphi(n)</tex>). Поэтому сумму можно заменить: <tex>S=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum\limits_{q\|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.

@@ Строка 55: / Строка 55: @@
 <tex> |G| = 2n</tex>. Первые <tex>n</tex> операций {{---}} повороты, и сумма количества их неподвижных точек, делённая на <tex>2n</tex>, принимает значение <tex>\dfrac{|C|} {2}</tex>, где <tex>|C|</tex> - количество ожерелий из <tex>n</tex> бусинок <tex>k</tex> различных цветов без отражений (задача выше) т.к. деление в задаче без отражений происходило на <tex>n</tex>, а здесь на <tex>2n</tex>. Следующие <tex>n</tex> операций {{---}} отражения. У каждой такой операции <tex>k^{\frac{n + 1}{2}}</tex> неподвижных точек. Поэтому сумма получается <tex>k^{\frac{n + 1}{2}}n</tex>.
-<tex>|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}k^{\dfrac{n + 1}{2}}n  = \dfrac{|C|}{2} + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} </tex><tex> = \dfrac{1} {2n}\sum\limits_{q|n}\varphi(\dfrac{n}{q})k^q + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} </tex>
+<tex>|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}k^{\dfrac{n + 1}{2}}n  = \dfrac{|C|}{2} + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} </tex><tex> = \dfrac{1} {2n}\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} </tex>
@@ Строка 64: / Строка 64: @@
 По Лемме Бёрнсайда:
-<tex>|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}(\dfrac{n}{2}k^{\dfrac{n}{2}} + \dfrac{n}{2}k^{\dfrac{n}{2} + 1})</tex> <tex>= \dfrac{|C|}{2} + \dfrac{1}{4}k^{\dfrac{n}{2}}(k + 1) = \dfrac{1} {2n}\sum\limits_{q|n}\varphi(\dfrac{n}{q})k^q + \dfrac{1}{4}k^{\dfrac{n}{2}}(k+1)</tex>
+<tex>|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}\left(\dfrac{n}{2}k^{\frac{n}{2}} + \dfrac{n}{2}k^{\frac{n}{2} + 1}\right)</tex> <tex>= \dfrac{|C|}{2} + \dfrac{1}{4}k^{\frac{n}{2}}(k + 1) = \dfrac{1} {2n}\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q + \dfrac{1}{4}k^{\frac{n}{2}}(k+1)</tex>
 == См. также ==

@@ Строка 69: / Строка 69: @@
 * [[Лемма Бёрнсайда и Теорема Пойа]]
 * [[Функция Эйлера]]
 == Источники информации ==
@@ Строка 74: / Строка 77: @@
 * [http://e-maxx.ru/algo/necklace_colouring MAXimal::algo::Ожерелья]
 [[Категория: Дискретная математика и алгоритмы]]
 [[Категория: Комбинаторика]]

← Предыдущая		Версия 20:35, 7 января 2016
Строка 25:		Строка 25:


−	Если раскраски ожерелья одинаковые, то они принадлежат одной [[Орбита\|орбите]] ~~(англ. orbit)~~, т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа\|лемме Бёрнсайда]], число орбит равняется <tex>\dfrac{n}{p}=\operatorname{gcd}(n,i)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex>, и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum\limits_{i=1}^{n}N_i=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}</tex>. В последней сумме <tex>\varphi(n)</tex> слагаемых <tex>(\varphi(n)</tex> {{---}} [[Функция Эйлера\|функция Эйлера]]<tex>)</tex>, для которых <tex>\operatorname{gcd}(n,i)=1</tex>. Если же <tex>\operatorname{gcd}(n,i)=q</tex>, то <tex>\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=1</tex>. Чтобы определить количество таких <tex>i</tex>, меньших <tex>n</tex>, нужно перебрать числа вида <tex>i=lq,\,0\leqslant l\leqslant \dfrac{n}{q}</tex> и проверять их на условие <tex>1=\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=\operatorname{gcd}\left(\dfrac{n}{q},l\right)</tex>. Таких чисел, очевидно, <tex>\varphi\left(\dfrac{n}{q}\right)</tex>(по определению <tex>\varphi(n)</tex>). Поэтому сумму можно заменить: <tex>S=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum\limits_{q\|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.	+	Если раскраски ожерелья одинаковые, то они принадлежат одной [[Орбита\|орбите]], т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа\|лемме Бёрнсайда]], число орбит равняется <tex>\dfrac{n}{p}=\operatorname{gcd}(n,i)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex>, и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum\limits_{i=1}^{n}N_i=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}</tex>. В последней сумме <tex>\varphi(n)</tex> слагаемых <tex>(\varphi(n)</tex> {{---}} [[Функция Эйлера\|функция Эйлера]]<tex>)</tex>, для которых <tex>\operatorname{gcd}(n,i)=1</tex>. Если же <tex>\operatorname{gcd}(n,i)=q</tex>, то <tex>\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=1</tex>. Чтобы определить количество таких <tex>i</tex>, меньших <tex>n</tex>, нужно перебрать числа вида <tex>i=lq,\,0\leqslant l\leqslant \dfrac{n}{q}</tex> и проверять их на условие <tex>1=\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=\operatorname{gcd}\left(\dfrac{n}{q},l\right)</tex>. Таких чисел, очевидно, <tex>\varphi\left(\dfrac{n}{q}\right)</tex>(по определению <tex>\varphi(n)</tex>). Поэтому сумму можно заменить: <tex>S=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum\limits_{q\|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.

@@ Строка 72: / Строка 72: @@
 == Источники информации ==
 * [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A0%D0%B5%D0%B4%D1%84%D0%B8%D0%BB%D0%B4%D0%B0_%E2%80%94_%D0%9F%D0%BE%D0%B9%D0%B0#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D0.BA.D0.BE.D0.BB.D0.B8.D1.87.D0.B5.D1.81.D1.82.D0.B2.D0.B5_.D0.BE.D0.B6.D0.B5.D1.80.D0.B5.D0.BB.D0.B8.D0.B9 Википедия {{---}} Теорема Редфилда — Пойа, Задача о количестве ожерелий]
-* [http://e-maxx.ru/algo/necklace_colouring MAXimal {{---}} Комбинаторика. Ожерелья.]
+* [http://e-maxx.ru/algo/necklace_colouring MAXimal::algo::Ожерелья]
 == Примечания ==

← Предыдущая		Версия 20:16, 7 января 2016
Строка 25:		Строка 25:


−	Если раскраски ожерелья одинаковые, то они принадлежат одной [[Орбита\|орбите]] (англ. orbit), т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа\|лемме Бёрнсайда]], число орбит равняется <tex>\dfrac{n}{p}=\operatorname{gcd}(n,i)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex>, и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum\limits_{i=1}^{n}N_i=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}</tex>. В последней сумме <tex>\varphi(n)</tex> слагаемых (<tex>\varphi(n)</tex> {{---}} [[Функция Эйлера\|функция Эйлера]], для которых <tex>\operatorname{gcd}(n,i)=1</tex>. Если же <tex>\operatorname{gcd}(n,i)=q</tex>, то <tex>\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=1</tex>. Чтобы определить количество таких <tex>i</tex>, меньших <tex>n</tex>, нужно перебрать числа вида <tex>i=lq,\,0\leqslant l\leqslant \dfrac{n}{q}</tex> и проверять их на условие <tex>1=\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=\operatorname{gcd}\left(\dfrac{n}{q},l\right)</tex>. Таких чисел, очевидно, <tex>\varphi\left(\dfrac{n}{q}\right)</tex>(по определению <tex>\varphi(n)</tex>). Поэтому сумму можно заменить: <tex>S=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum\limits_{q\|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.	+	Если раскраски ожерелья одинаковые, то они принадлежат одной [[Орбита\|орбите]] (англ. orbit), т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа\|лемме Бёрнсайда]], число орбит равняется <tex>\dfrac{n}{p}=\operatorname{gcd}(n,i)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex>, и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum\limits_{i=1}^{n}N_i=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}</tex>. В последней сумме <tex>\varphi(n)</tex> слагаемых <tex>(\varphi(n)</tex> {{---}} [[Функция Эйлера\|функция Эйлера]]<tex>)</tex>, для которых <tex>\operatorname{gcd}(n,i)=1</tex>. Если же <tex>\operatorname{gcd}(n,i)=q</tex>, то <tex>\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=1</tex>. Чтобы определить количество таких <tex>i</tex>, меньших <tex>n</tex>, нужно перебрать числа вида <tex>i=lq,\,0\leqslant l\leqslant \dfrac{n}{q}</tex> и проверять их на условие <tex>1=\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=\operatorname{gcd}\left(\dfrac{n}{q},l\right)</tex>. Таких чисел, очевидно, <tex>\varphi\left(\dfrac{n}{q}\right)</tex>(по определению <tex>\varphi(n)</tex>). Поэтому сумму можно заменить: <tex>S=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum\limits_{q\|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.