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


Содержание

ММ31

Конкурсная задача ММ31 (7 баллов)

Пусть Sn - симметрическая группа (т.е. группа, образованная всеми биекциями множества {1, 2,…, n} на себя относительно операции композиции) и On - множество порядков всех элементов Sn.
1) Могут множества On совпадать при различных n? (2 балла)
2) Найти наименьшее n такое, что максимальные элементы множеств On и On+3 равны. (5 баллов)

Решение

Как известно, всякая подстановка (элемент группы Sn) может быть разложена в произведение независимых циклов. Порядок элемента Sn равен наименьшему общему кратному длин этих циклов. Учитывая этот факт, легко увидеть, что при n = 5 и n = 6 множества On совпадают. Таким образом, ответ на первый вопрос задачи - «да».

Наименьшее n такое, что максимальные элементы множеств On и On+3 равны, равно 19. Максимальный порядок элементов групп S19 и S22 равен 420 = 3*4*5*7
Убедиться в этом можно разными путями: написав программку, выполнив ручной оптимизированный перебор, etc.

Обсуждение

Приведенный выше пример совпадения множеств On при различных n - единственный. Макс Алексеев привел простое доказательство этого факта, опирающееся на гипотезу Гольдбаха. Влад Франк сначала придумал аналогичное доказательство, а затем и другое, не использующее гипотезу Гольдбаха. Приведу набросок этого доказательства.

Пусть n - натуральное число, большее 6. Нам надо представить его в виде суммы с таким НОК слагаемых, которое недостижимо для всех натуральных, меньших n. Вычтем из n самое большое простое число из промежутка [n/2]+1..n-7. Существование простых чисел на указанном промежутке для достаточно больших n вытекает из усиленного постулата Бертрана, который, в отличие от гипотезы Гольдбаха давно доказан (еще П.Л.Чебышёвым). Будем повторять этот процесс пока останется число, пока не придем к числу из диапазона 7..20. А для чисел из этого промежутка легко подобрать представления в виде суммы степеней простых чисел, меньших 11 (11 - это самое маленькое простое число, которое мы могли вычесть на предыдущих этапах). Проиллюстрирую способ получения такого представления на примере. Пусть n = 19660. Тогда для него имеем представление 19609+43+8 с НОК слагаемых недостижимых ни для каких меньших n.

Максимальный элемент множества On - это на самом деле значение функции Ландау (немецкого математика, а не советского физика) от числа n. Известно, что эта неубывающая функция имеет сколь угодно длинные стационарные участки, т.е. для любого натурального k найдется n, что Landau(n) = Landau(n+1) = … = Landau(n+k-1).

Награды

За правильное решение этой задачи Макс Алексеев получает 9 призовых баллов, Влад Франк - 11 призовых баллов. (Дополнительные баллы начислены за ответы на вопросы, обобщающие те, что сформулированы в задании).


 

 


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

marathon/problem_31.txt · Последние изменения: 2019/10/30 07:21 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006