IMO 2019, Problem 4

[nnosipov]

Найдите все пары $(k,n)$ целых положительных чисел такие, что

$$k!=(2^n-1)(2^n-2)(2^n-4)\ldots(2^n-2^{n-1}).$$

Замечание. По-моему, на уровне идеи (решения) задача совершенно очевидная. Ее решили все участники команды России, кроме одного, который за нее, скорее всего, не брался.

[maxal]

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$ и т.д.

[nnosipov]

maxal в сообщении #1406630 писал(а):

Очевидная идея - сравнить степени 2-ки.

Да, первое, о чем подумалось. Да и реализация этой идеи не слишком хлопотная, вроде бы.

maxal в сообщении #1406630 писал(а):

А вот чуть менее очевидная - сравнить степени 3-ки

Это уже не для совсем ленивых, тут напрягаться надо :)

[maxal]

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

[12d3]

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$ неравенства одновременно выполняться не могут, остается только проверить небольшие значения.

[maxal]

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

[12d3]

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

[nnosipov]

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

[Shadow]

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$ и т.д. но это ненужно

[nnosipov]

Небольшое уточнение по поводу формулы для показателя $\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$ формулу следует модифицировать.

[maxal]

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!).$$

[vlad239]

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

[nnosipov]

vlad239 в сообщении #1407960 писал(а):

Как наблюдатель на этом самом межнаре могу сказать, что тот самый один участник брался.

Тогда очень жаль.