|
||||||||||||||||||
|
СодержаниеММ100Юбилейная задача представляет собой по сути целый букет задач, связанных общей тематикой и общими идеями. Часть подзадач - известные (но, с учетом их красоты, на мой взгляд, недостаточно известные) утверждения. Другие - новые (хотелось бы надеяться не только для меня). Конкурсная задача №100 (17 баллов) Пусть Sn множество всех перестановок множества Mn = {1,2,3…,n}
1. Найти и обосновать рекуррентное выражение количества перестановок g из
Sn таких, что для всех k из Mn g(k) может отличаться от k: 2. Рассмотрим произвольный элемент из Sn и произвольное a из Mn. Найти вероятность того, что a входит в цикл длины k.
3. Для произвольного элемента g из Sn найти:
4. Вспомним, что Sn является группой относительно композиции перестановок. Решение 1.a.
Этот пункт совсем легкий. 1.b.
Здесь ситуация похитрее. Для того чтобы выяснить, как можно продолжить подходящую перестановку, не добавляя новых циклов, рассмотрим возможные «хвосты» подходящих перестановок. ii) Заметим, что, если в цикловую запись подходящей перестановки на множестве Mn-1 входит цикл, содержащий (n-1), длина которого больше двух, то в такой цикл можно добавить элемент n единственным способом. iii) Если цикловая запись перестановки заканчивается петлей (n-1), перед которой идет цикл, содержащий более одного элемента, то такую перестановку также можно продолжить до подходящей, не добавляя новых циклов, единственным способом, заменив петлю (n-1) на транспозицию (n-1 n). iv) Если цикловая запись перестановки заканчивается двумя петлями (n-2)(n-1), то в каждую из них можно добавить n. v) Если цикловая запись перестановки заканчивается транспозицией (n-2 n-1), то оба возможных способа добавления элемента n в эту транспозицию ведут к получению подходящих перестановок множества Mn. vi) Если цикловая запись подходящей перестановки заканчивается выражением (n-3 n-1)(n-2), то элемент n нельзя «впихнуть» в транспозицию (n-3 n-1), но можно добавить в одноэлементный цикл (n-2). vii) Наконец, если цикловая запись подходящей перестановки заканчивается выражением (n-4 n-2)(n-3 n-1), то добавить элемент n в уже имеющиеся циклы невозможно. Поэтому G(n) = 2G(n-1) + 2G(n-3) - G(n-5). (Большинстово подходящих перестановок можно продолжить не менее чем двумя способами. Второе слагаемое учитывает дополнительные подходящие перестановки, возникающие в случаях iv и v, а последнее слагаемое обусловлено случаем vii.) 2. Ответ к этому пункту: 1/n для всек k ≤ n и 0 при k > n. В самом деле, произвольный элемент a множества Mn при произвольной перестановке с вероятностью 1/n переходит в себя и образует цикл длины 1. Вероятность его вхождения в цикл длины 2 равна произведению (n-1)/n (вероятности того, что a не перешел в себя) на 1/(n-1) (верояности того, что образ a перешел в a). Итого, вновь имеем верояность 1/n. И т.д. 3.a. Запишем все n! перестановок в цикловом виде (не опуская одноэлементных циклов). В этой записи будет участвовать ровно n*n! элементов, разбитых на циклы длин 1, 2, … n. Из пункта 2 следует что для каждого k из {1,2,…,n} в этой записи будет ровно n! элементов, входящих в циклы длины k и, значит, n!/k циклов длины k. (Например, для n = 3 имеем: (1)(2)(3),(12)(3),(13)(2),(1)(23),(123),(132).) Но тогда искомое математическое ожидание равно (n!/k)/n! = 1/k. 3.b. Для получения ответа к этому пункту достаточно просто просуммировать математические ожидания числа циклов длины k по всем возможным k. Таким образом, математическое ожидание количества циклов в произвольной перестановке n-элементного множества равно 1 + 1/2 +…+ 1/n, т.е. n-му гармоническому числу. 3.c.
При n = 1 в единственной перестановке множества Mn есть единственный цикл
длины 1. При n = 2 возможные цикловые виды [1]-[1] и [2] встречаются одинаково
часто (по одному разу). 3.d. i. Со случаем n/2 < k ≤ n мы разобрались в предыдущих пунктах. Искомая вероятность равна 1/k ii. При n/3 < k ≤ n/2, разобрав случаи одного и двух циклов, получим искомую вероятность (2*k-1)/(2*k2). iii. Для остальных случаев удобно воспользоваться формулой включения и исключения. При n/4 < k ≤ n/3 имеем (6*k2-3*k+1)/(6*k3). iv. При n/5 < k ≤ n/4 имеем (24*k3-12*k2+4*k-1)/(24*k4). 4.a. При возведении в степень k цикл длины m распадается на (k,m) циклов длины m/(k,m). Учитывая это соображение и количество подстановок каждого циклового вида в группах Sn при малых n можно получить следующие 20 значений s(n,k) (если значение получается при разных наборах значений n и k, указан один из таких наборов):
1 (при n = 1, k = 1) Обоснование того, что приведены наименьшие возможные значения можно посмотреть в :решении Влада Франка. 4.b.
Покажем, что q(9,3) = 1/2. Обсуждение Любопытно, что большинство участников Марафона, получив рекуррентное соотношение для F(n), никоим образом не отреагировали, что это числа Фибоначчи. Последовательность G(n) (как, разумеется, и F(n)) есть в онлайн-энциклопедии целочисленных последовательностей. Её номер A002524.
Применяя метод включения и исключения, можно получить общую формулу,
выражающую вероятность наличия цикла длины k в Sn - Любопытно, 21-е по величине значение |s(n,k)| получается при n = 8. Это |s(8,420)| = 106 (|s(7,210)| тоже равно 106).
С пунктом 4.b. не справился ни один участник. Это оказалось для меня
неожиданным. Ведь подходящий пример возникает при совсем не запредельных n и k.
Кстати, q(10,3) и q(11,3) тоже равны по 1/2.
Вызывает интерес доказательство (или опровержение) следующей гипотезы: Награды
За правильное решение большинства пунктов задачи 100 участники получают: Эстетическая оценка задачи - 5 баллов
|
|||||||||||||||||
|
||||||||||||||||||
|