А вот вообще "убойная" задача на перестановки (на мой взгляд)

Автор темы Сергей A. 
ОбъявленияПоследний пост
ОбъявлениеМГУ и Яндекс объявили об открытии на мехмате специализации по анализу данных и машинному обучению24.08.2021 00:17
ОбъявлениеПостдок позиция по математике в Гетеборге (Швеция)10.09.2021 19:11
ОбъявлениеКниги по математике и экономике в добрые руки!10.12.2021 10:59
23.01.2004 23:10
Сергей A.
А вот вообще "убойная" задача на перестановки (на мой взгляд)
Доказать, что существует перестановка порядка c^(sqrt(n*ln(n))), где c - некоторая константа (действительное число), c>1.
sqrt - квадратный корень.

Если у кого-нибудь есть какие-то идеи - буду рад.
На мой взгляд, совершенно "убойная" задача. :-)

P.S. Отдельное "спасибо" г-ну Чашкину А.В. :-)
24.01.2004 00:32
Сергей Михайлов
идеи есть
Сначала опишу саму идею. Нужно взять простые числа по порядку p_1, ..., p_r, не превосходящие некоторой границы B. Взять их нужно так, чтобы их количество не превосходило N/B (заметим, что при B = 2 это выполняется, при B = N это не выполняется, причем ясно, что где-то между 2 и N находится достаточно подходящее число B такое, чтобы и граница была побольше, но и количество не "вылезало" за рамки). Далее, рассмотреть подстановку g, состоящую из произведения циклов длин p_1, ..., p_r (такая есть, т.к. p_1 + ... + p_r <= B * N/B = N) и нескольких циклов длины 1 (чтобы дополнить ее до длины N). Ее порядок будет равен HOK(p_1, ..., p_r) = p_1*...*p_r. Далее надо показать, что этот порядок может быть сделан больше, чем число, требуемое в задаче.

Теперь о том, как эту идею реализовать. Я буду ссылаться на два факта, которые преподаются на мехмате МГУ в курсе теории чисел.
Факт 1. Пусть пи(x) - количество простых чисел, не превосходящих x. Существует число a > 1 такое что при x > 1 имеет место неравенство пи(x) <= a*x/ln(x).
Факт 2. Произведение всех простых чисел, не превосходящих x П_{p <= x} p >= 4^x.

Теперь надо взять B = sqrt(1/(2*a))*sqrt(N*ln(N)). Тогда получим, что N/B = sqrt(2*a*N)/sqrt(ln(N)). Надо проверить, что пи(B) <= N/B. Это предлагается сделать на основании факта 1. пи(B) <= a*B/ln(B) = a*sqrt(1/(2*a))*sqrt(N*ln(N))/[1/2*ln(1/(2*a)) + 1/2*ln(N) + 1/2ln(ln(N))] <= a*sqrt(1/(2*a))*sqrt(N*ln(N))/[1/2*ln(N)] = sqrt(2*a)*sqrt(N)/sqrt(ln(N)) = N/B.
Так, теперь используем факт 2 и остается лишь доказать, что существует c > 1 такая, что 4^B >= c^{sqrt(N*ln(N))}. Перейдем к основанию e. Получим e^{B*ln(4)} >= e^{sqrt(N*ln(N))*ln(c)} <=> B*ln(4) => sqrt(N*ln(N))*ln(c) или sqrt(1/(2*a))*sqrt(N*ln(N))*ln(4) => sqrt(N*ln(N)) или sqrt(1/(2*a))*ln(4) > ln(c). Заметим, что при с -> 1 (с стремится к 1) ln(c) -> 0, поэтому можно выбрать c > 1 такое, что будет выполнено нужное неравенство.
Вот и все вроде бы. По модулю двух фактов из теории чисел.

24.01.2004 00:38
Сергей Михайлов
поправка
В факте 1 нужно написать, что неравнество верно при x >= 2 для корректности (просто при x -> 1 там ln(x) уходит в ноль и не получится подобрать константу a.). Ясно, что это не существенно, просто для строгости формулировки.
24.01.2004 00:48
Сергей A.
Стоп(+)
А разве недостаточно доказать, что среди чисел вида c^sqrt(n*ln(n)) есть целые числа? А если удастся доказать, что для каждого такого целого числа (порядок перестановки) можно подобрать соответствующим образом константу c (это доказать несложно), то задача фактически решена. Но это получается как-то просто.
Поправьте меня, если я не прав.
24.01.2004 00:58
Сергей A.
Более того(+)
Пусть известно число n.

Предположим, что число N = с^sqrt(n*ln(n)) - натуральное, тогда c = exp[ln(N) / sqrt(n*ln(n))]. Очевидно, c>1. Таким образом, мы доказали, что для того, чтобы получить нужное нам натуральное число N, мы всегда можем соответствующим образом выбрать константу c>1.

Неужели так всё просто? Наверное, я что-то не допонял.

Кстати, Сергей, вы, видимо, перепутали задачи. То решение, которое вы написали здесь, я так понимаю, относится к задаче "Новая задача про группу перестановок"?
24.01.2004 01:07
Сергей A.
Факт 2 почему-то работает не для всех x
Например.

x = 3.
Произведение всех простых чисел, не превосходящих 3, равно: 2*3=6.
Однако 6 < 4^3.
24.01.2004 01:09
Сергей Михайлов
с не должно зависеть от n
Естественно, что для каждого n можно подобрать свое c, даже такое, что c^{sqrt(n*ln(n))} = 2, но только такое c зависит от n и с ростом n оно стремится к 1. А нам надо доказать, что есть c, не зависящее n и большее единицы. Т.е. требуется доказать, что с ростом n максимальный подрядок элемента растет не медленнее, чем экспонента от sqrt(n*ln(n)) (под экспонентой понимаем, что рассматривается экспоненциальная функция с основанием больше 1)
24.01.2004 01:28
Сергей Михайлов
начиная с некоторого
факт 2 работает для всех x, начиная с некоторого. Щас точно не помню с какого.
24.01.2004 02:08
Сергей A.
Сергей, я вам отправил на почту
личный вопрос. Посмотрите, пожалуйста...
24.01.2004 11:39
Сергей Михайлов
еще кое-что
Еще раз о факте 2. Я уже не уверен, что там верно для 4. Но точно могу сказать, что существует b>1 такое, что указанное произведение больше, чем b^x. Как только смогу, я дам ссылку не литературу, где есть формулировка.
25.01.2004 17:16
Сергей A.
Сергей, я вам отправил два письма
на почту. Почему не отвечаете?
25.01.2004 17:31
Сергей Михайлов
я знаю
получил я их. Писал три ответа. Все вернулись обратно. С адресом все в порядке. Не знаю, что за глюки. Возможно, спамо-фильр по каким-то причинам посчитал меня спамом. Звони 8-905-5-144-0-(xy). Чтобы получить эти две цифры, вычти два часа из времени начала того мероприятия в понедельник о котором ты мне писал. Попробуй позвонить мне, как это прочитаешь. Не получится, пиши сюда.

Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти