Решение задачи MM149 XV тура Математического марафона

главная страница сайта Приглашение в мир математики
======= 149 ========

ММ149 (8 баллов)

При каком наименьшем $n$ в группе перестановок $S_n$ существует подгруппа порядка 253? Привести пример такой подгруппы.

====================

Решение

Приведу решение Андрея Халявина, замечательное своей краткостью.
$253=23\cdot 11$. Поэтому по теореме Силова в подгруппе должен быть элемент порядка 23. Значит, $n\ge 23$.
Пусть $g$ - первообразный корень по модулю 23. Тогда подгруппа группы $S_{23}$, состоящая из перестановок $x\longrightarrow g^{2s}x+t \mod 23, \ 0\le s<11, \ 0\le t<23$, имеет порядок 253.
Ответ: $n=23$ Обсуждение

Приведу более лобовой (если хотите, более тупой) способ построения требуемой подгруппы группы $S_{23}$.
Возьмем цикл $a=(1 \ 2 \ 3 \dots \ 22 \ 23)$ и будем строить перестановку $b$ такую, что $bab^{-1}=a^2$.
Заметим, что $a^2=(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^{-1}$ имеем: $1\longrightarrow 2\longrightarrow 3 \longrightarrow 3$. Значит, $b^{-1}(3)=3$ и $b(3)=3$.
Тогда $3\longrightarrow 3\longrightarrow 4 \longrightarrow 5$. Значит, $b^{-1}(4)=5$ и $b(5)=4$.
Тогда $5\longrightarrow 4\longrightarrow 5 \longrightarrow 7$. Значит, $b^{-1}(5)=7$ и $b(7)=5$.
Тогда $7\longrightarrow 5\longrightarrow 6 \longrightarrow 9$. Значит, $b^{-1}(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_{34}$) получают по 2 призовых балла.

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

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

-- 23 окт 2011, 11:41 --

=================================

Задайте вопрос на блоге о математике