2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 IMO 2019, Problem 4
Сообщение23.07.2019, 17:12 
Заслуженный участник


20/12/10
8858
Найдите все пары $(k,n)$ целых положительных чисел такие, что $$k!=(2^n-1)(2^n-2)(2^n-4)\ldots(2^n-2^{n-1}).$$
Замечание. По-моему, на уровне идеи (решения) задача совершенно очевидная. Ее решили все участники команды России, кроме одного, который за нее, скорее всего, не брался.

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение23.07.2019, 17:23 
Модератор
Аватара пользователя


11/01/06
5660
nnosipov, мне тоже эта задача показалась очень простой. Очевидная идея - сравнить степени 2-ки. А вот чуть менее очевидная - сравнить степени 3-ки - дает красивое равенство: $\lfloor k/3\rfloor = \lfloor n/2\rfloor$. А степени 5-ки - соответственно: $\lfloor k/5\rfloor = \lfloor n/4\rfloor$, степени 7-ки: $\lfloor k/7\rfloor = \lfloor n/3\rfloor$ и т.д.

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение23.07.2019, 17:35 
Заслуженный участник


20/12/10
8858
maxal в сообщении #1406630 писал(а):
Очевидная идея - сравнить степени 2-ки.
Да, первое, о чем подумалось. Да и реализация этой идеи не слишком хлопотная, вроде бы.
maxal в сообщении #1406630 писал(а):
А вот чуть менее очевидная - сравнить степени 3-ки
Это уже не для совсем ленивых, тут напрягаться надо :)

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение23.07.2019, 17:47 
Модератор
Аватара пользователя


11/01/06
5660
А по мотивам 5-й задачи я добавил: A326729, A326730, A326731, A326732.

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение23.07.2019, 18:00 
Заслуженный участник


04/03/09
906
maxal в сообщении #1406630 писал(а):
А вот чуть менее очевидная - сравнить степени 3-ки - дает красивое равенство: $\lfloor k/3\rfloor = \lfloor n/2\rfloor$.

Нет ли тут ошибки? Степень тройки в факториале равна $\lfloor k/3\rfloor + \lfloor k/9\rfloor + \lfloor k/27\rfloor + \dots$ В правой части каждый второй множитель кратен 3, но он также может быть кратен и 9, и 27, и т.д.
У меня идея такая:

(Оффтоп)

если сравнить степени двойки, получим неравенство $k > \dfrac{n(n-1)}{2}$, а если сравнить значения самих выражений, получим $k! < 2^{n^2}$. При больших $n$ и $k$ неравенства одновременно выполняться не могут, остается только проверить небольшие значения.

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение23.07.2019, 18:21 
Модератор
Аватара пользователя


11/01/06
5660
12d3, не понял вашего вопроса. Степень 3-ки в левой части указана правильно, а в правой она $\lfloor n/2\rfloor + \lfloor n/6\rfloor + \dots$. Из их равенства следует, что $\lfloor k/3\rfloor = \lfloor n/2\rfloor$.

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение23.07.2019, 18:26 
Заслуженный участник


04/03/09
906
maxal, я поначалу подумал, что вы неправильно степени посчитали. )

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение23.07.2019, 18:54 
Заслуженный участник


20/12/10
8858
6-ю задачу, видимо, следует считать сложной, что обидно: ведь механическая проверка утверждения задачи не представляет вообще никакого труда (типа нарисовать картинку в geogebra, подвигать ее и убедиться, что все окей естественно, потребуется какая-нибудь CAS). По факту, максимальный балл участников из России на этой задаче --- 2 из 7 возможных.

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение24.07.2019, 09:20 


26/08/11
2057
maxal в сообщении #1406630 писал(а):
и т.д.
Именно. Я сразу взялся сравнить степень 31 и 29.
Ведь каждый пятый множитель будет делится на 31 и лишь каждый 28-ой на 29, следовательно при $n\ge 5$ решений не будет.
Если строго

$r=(2^1-1)(2^2-1)\cdots (2^n-1)$

$v_{29}(r)=\left\lfloor\dfrac{n}{28}\right\rfloor+\left\lfloor\dfrac{n}{28\cdot 29}\right\rfloor+\left\lfloor\dfrac{n}{28\cdot 29^2}\right\rfloor+\cdots<

$<\dfrac{n}{28}\left(1+\dfrac{1}{29}+\dfrac{1}{29^2}+\cdots\right)=\dfrac{n}{28}\cdot \dfrac{29}{28}$

При оценки снизу можно великодушно

$v_{31}(r)\ge \left\lfloor\dfrac{n}{5}\right\rfloor\ge \dfrac{n-4}{5}$

(Оффтоп)

причем очень великодушно, потому то в конце концов, если $n\ge 28\cdot 29$, то и $n\ge 5\cdot 31$ и т.д. но это ненужно

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение29.07.2019, 13:30 
Заслуженный участник


20/12/10
8858
Небольшое уточнение по поводу формулы для показателя $\nu_p(\cdot)$ для правой части: если $a>1$ не делится на $p$, то $$\nu_p((a-1)(a^2-1)\ldots(a^n-1))=\nu_p(a^d-1)[n/d]+[n/(dp)]+[n/(dp^2)]+\ldots,$$ где $d$ --- порядок $a$ по модулю $p$. При $a=2$ множитель $\nu_p(a^d-1)$ почти всегда равен единице (известные исключения составляют только $p=1093$ и $p=3511$).

Upd. Здесь $p>2$. Для случая $p=2$ формулу следует модифицировать.

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение29.07.2019, 17:59 
Модератор
Аватара пользователя


11/01/06
5660
nnosipov, как следствие, при $\nu_p(a^d-1)=1$ имеем:
$$\nu_p((a-1)(a^2-1)\cdots (a^n-1))=\nu_p(\lfloor\frac{np}d\rfloor!).$$

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение30.07.2019, 20:39 


06/01/09
231
Как наблюдатель на этом самом межнаре могу сказать, что тот самый один участник брался. Но к сожалению в результате досадной описки он в третьей строке получил, что $n!$ делится не просто на $2^{n/2+n/4+\ldots}$, а на 2 в степени вот все предыдущее...

 Профиль  
                  
 
 Re: IMO 2019, Problem 4
Сообщение30.07.2019, 21:11 
Заслуженный участник


20/12/10
8858
vlad239 в сообщении #1407960 писал(а):
Как наблюдатель на этом самом межнаре могу сказать, что тот самый один участник брался.
Тогда очень жаль.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group