===== 149 =====

**Конкурсная задача ММ149** (8 баллов) 

При каком наименьшем n в группе перестановок S<sub>n</sub> существует подгруппа порядка 253? Привести пример такой подгруппы.


**Решение**

Приведу решение Андрея Халявина, замечательное своей краткостью.
253=23⋅11. Поэтому по теореме Силова в подгруппе должен быть элемент порядка 23. Значит, n≥23.
Пусть g - первообразный корень по модулю 23. Тогда подгруппа группы S<sub>23</sub>, состоящая из перестановок x -> g<sup>2s</sup>x+t (mod 23),  0≤s<11,  0≤t<23, имеет порядок 253.
Ответ: n=23

**Обсуждение**

Приведу более лобовой (если хотите, более тупой) способ построения требуемой подгруппы группы S<sub>23</sub>.
Возьмем цикл a=(1 2 3 ... 22 23) и будем строить перестановку b такую, что bab<sup>-1</sup>=a<sup>2</sup>.\\
Заметим, что a<sup>2</sup>=(1 3 5 7 9 11 13 15 17 19 21 23 2 4 6 8 10 12 14 16 18 20 22).\\
Пусть b(1)=2. Тогда при bab<sup>-1</sup>имеем: 1 -> 2 -> 3 -> 3. Значит, b<sup>-1</sup>(3)=3 и b(3)=3.\\
Тогда 3 -> 3 -> 4 -> 5. Значит, b<sup>-1</sup>(4)=5 и b(5)=4.\\
Тогда 5 -> 4 -> 5 -> 7. Значит, b<sup>-1</sup>(5)=7 и b(7)=5.\\
Тогда 7 -> 5 -> 6 -> 9. Значит, b<sup>-1</sup>(6)=9 и b(9)=6.\\
Продолжая в том же духе, получим b=(1 2 14 20 23 13 8 17 10 18 22)(4 15 9 6 16 21 12 19 11 7 5).\\
Непосредственно проверяется, что подгруппа, порожденная a и b, имеет порядок 253. 

Пусть p<q - простые числа. С помощью теоремы Силова легко доказывается, что, если q не сравнимо с 1 по модулю p, то группа порядка pq циклическая. Такая группа может быть реализована перестановками множества, состоящего не менее, чем из p+q элементов.
Если же q сравнимо с 1 по модулю p, то обязательно найдется группа порядка pq типа нашей, реализуемая перестановками из S_q. Подробности можно найти, например, в книжке М.Каргаполов, Ю.Мерзляков. "Основы теории групп"  
 

**Награды**

За правильное решение и обобщение задачи ММ149 Алексей Волошин получает 9 призовых баллов. Анатолий Казмерчук, Виктор Филимоненков, Sirion и Андрей Халявин получают по 8 призовых баллов. Сергей Половинкин и Дмитрий Пашуткин (нашедшие нужные подгруппы лишь в S<sub>34</sub>) получают по 2 призовых балла. 

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

//Разбор задачи ММ149 подготовил Владимир Лецко//
----