Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ100

Юбилейная задача представляет собой по сути целый букет задач, связанных общей тематикой и общими идеями. Часть подзадач - известные (но, с учетом их красоты, на мой взгляд, недостаточно известные) утверждения. Другие - новые (хотелось бы надеяться не только для меня).

Конкурсная задача №100 (17 баллов)

Пусть Sn множество всех перестановок множества Mn = {1,2,3…,n}

1. Найти и обосновать рекуррентное выражение количества перестановок g из Sn таких, что для всех k из Mn g(k) может отличаться от k:
a) не более, чем на 1;
b) не более, чем на 2.

2. Рассмотрим произвольный элемент из Sn и произвольное a из Mn. Найти вероятность того, что a входит в цикл длины k.

3. Для произвольного элемента g из Sn найти:
a) математическое ожидание количества циклов длины k;
b) математическое ожидание количества циклов;
c) моду циклового вида (учитываются количество и длина циклов);
d) полагая k > n/5, найти вероятность того, что в g будет хотя бы один цикл длины k.

4. Вспомним, что Sn является группой относительно композиции перестановок.
Обозначим s(n,k) = | {gk | g ∈ Sn} |, q(n,k) = s(n,k)/n!:
a) найти 20 наименьших значений s(n,k);
b) возможно ли равенство q(n,k) = 1/2 для нечетных k.

Решение

1.a.

Этот пункт совсем легкий.
Перестановки, удовлетворяющие условию пункта 1.a будем называть подходящими. Обозначим искомое количество подходящих перестановок через F(n).
Ясно, что F(1) = 1 и F(2) = 2.
Требуемые перестановки, очевидно, представляют собой произведение транзпозиций соседних элементов и «циклов» длины 1. Т. е. их можно получить, приписывая транспозицию (n-1 n) к F(n-2) подходящим перестановкам множества Mn-2 и петли (n) к F(n-1) подходящим перестановкам множества Mn-1.
Поэтому F(n) = F(n-1) + F(n-2), и мы получаем ряд Фибоначчи.

1.b.

Здесь ситуация похитрее.
Теперь подходящими будем называть перестановки, удовлетворяющие условию пункта 1.b. Обозначим искомое количество подходящих перестановок через G(n).
Первые значения G: G(1) = 1, G(2) = 2, G(3) = 6, G(4) = 14. Учитывая, что 0! = 1, положим G(0) = 1.
Пусть теперь n не меньше 5.
i) Из каждой подходящей перестановки множества Mn-1 можно получить подходящую перестановку множества Mn, добавив петлю (n).

Для того чтобы выяснить, как можно продолжить подходящую перестановку, не добавляя новых циклов, рассмотрим возможные «хвосты» подходящих перестановок.

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] встречаются одинаково часто (по одному разу).
Пусть n > 2.
Из предыдущих пунктов следует, что ровно (n-1)! перестановок представляют собой цикл длины n. Аналогично, цикловой вид [n-1]-[1] имеют n!/(n-1) перестановок. Т.е. их больше, чем длинных циклов. Покажем, что [n-1]-[1] и есть мода циклового вида.
В самом деле, легко видеть, что престановок циклового вида [n-1]-[1] больше, чем престановок циклового вида [n-k]-[k] при k и n-k, бОльших 1.
Пусть теперь n = a + b + c, где a >= b >= c. Тривиально показывается, перестановок вида [a+b]-[c] больше чем перестановок вида [a]-[b]-[c]. И т.д.

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)
2 (при 2 = 1, k = 1)
3 (при n = 3, k = 2)
4 (при n = 3, k = 3)
6 (при n = 3, k = 1)
9 (при n = 4, k = 4)
12 (при n = 4, k = 2)
16 (при n = 4, k = 3)
21 (при n = 5, k = 20)
24 (при n = 4, k = 1)
25 (при n = 5, k = 12)
36 (при n = 5, k = 10)
40 (при n = 5, k = 6)
45 (при n = 5, k = 4)
46 (при n = 6, k = 30)
56 (при n = 5, k = 15)
60 (при n = 5, k = 2)
80 (при n = 5, k = 3)
81 (при n = 6, k = 20)
96 (при n = 5, k = 5)

Обоснование того, что приведены наименьшие возможные значения можно посмотреть в :решении Влада Франка.

4.b.

Покажем, что q(9,3) = 1/2.
Для этого заметим, что в s(9,3), в отличие от S9, нет перестановок с циклами, длины которых кратны 3, за исключением перестановок вида [3]-[3]-[3]. В S9 Имеется:
девятиэлементных циклов - 8!;
перестановок, содержащих шестиэлементный цикл, - 9!/6;
перестановок с ровно двумя трехэлементными циклами, - C(9,3)*C(6,3)*22*|s(3,3)|/2;
перестановок с ровно одним трехэлементным циклом, - C(9,3)*2*|s(6,3)|.
Учитывая, что |s(6,3)| = 400, |s(3,3)| = 4, и суммируя, получим 181440 = 9!/2.

Обсуждение

Любопытно, что большинство участников Марафона, получив рекуррентное соотношение для F(n), никоим образом не отреагировали, что это числа Фибоначчи.

Последовательность G(n) (как, разумеется, и F(n)) есть в онлайн-энциклопедии целочисленных последовательностей. Её номер A002524.

Применяя метод включения и исключения, можно получить общую формулу, выражающую вероятность наличия цикла длины k в Sn -
sum{i=1}{[n/k]}{(-1)^{i+1}/(k^i*i!)}.

Любопытно, 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.
Справедливо и более общее утверждение: q(n,k) ≤ q(n+1,k), причем это неравенство трансформируется в равенство всякий раз, когда (k,n+1) = 1.

Вызывает интерес доказательство (или опровержение) следующей гипотезы:
Для любых натурального k и положительного e найдется n такое, что q(n,k) < e.

Награды

За правильное решение большинства пунктов задачи 100 участники получают:
Владислав Франк - 15 баллов;
Алексей Волошин - 14 баллов;
Андрей Халявин и Алексей Извалов по 12 баллов.

Эстетическая оценка задачи - 5 баллов


 

 


Страница: [[marathon:problem_100]]

marathon/problem_100.txt · Последние изменения: 2017/09/07 04:46 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006