Бат, Великобритания, 2019 год


Найдите все пары $(k,n)$ целых положительных чисел такие, что $k!=(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1}).$
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 2   1
2021-12-25 04:44:54.0 #

Найдем пары: $(1:1) , (3:2)$.

Теперь $n>2$. Давайте переведем формулу на более приятный лад:

$$k!=(2^n-2^{n-1})(2^n-2^{n-2})...(2^n-2)(2^n-1)=2^{n-1}(2-1)2^{n-2}(2^2-1)...2^1(2^{n-1}-1)2^0(2^n-1)=2^{\frac{n(n-1)}{2}}(2-1)(2^2-1)...(2^n-1)$$

Заметим что в конце слогов после $2^{\frac{n(n-1)}{2}}$, $n$ количество(имею ввиду про слоги типа:$(2-1)(2^2-1)...(2^n-1)$) . Ну по сути $k$-тый этот слог больше или равно $k$, соответственно $2^{\frac{n(n-1)}{2}}(2-1)(2^2-1)...(2^n-1)\geq n!$. Значит $n\geq k$.

Моя цель тут объяснить что в произведении разности степеней двоек справа имеет вид $2^{\frac{n(n-1)}{2}}(2-1)(2^2-1)...(2^n-1)$, соответственно максимальная степень двойки на которую делится наше $k!$ которому это число равно равна $\frac{n(n-1)}{2}$, а $k$ кстати меньше равно $n$, значит $n!$ хотя бы должен нацело делиться на $2^{\frac{n(n-1)}{2}}$.

Дело за малым, посмотрим на $k!$, четных слогов у него максимум $\frac{k}{2}$, или же максимум $\frac{n}{2}$, но по сути каждый этот четный слог меньше чем $2^{n-1}$ (по индукции $2^{n-1}>n$ для $n>2$) и получается делиться не могут на $2^{n-1}$. Умножаем на максимальное количество четных слогов $\frac{n}{2}$(типо пройдемся по каждому четному слогу), получается произведение четных слогов вместе не смогут поделиться на степень двойки $\frac{n}{2}*n-1$ (где $\frac{n}{2}$ это количество четных слогов, а $n-1$ степень на которую они не смогут поделиться). Получается $n!$ не сможет поделиться на $2^{\frac{n(n-1)}{2}}$, но так как $n \geq k$ то и $k!$ не сможет поделиться, соответственно ответы где $n>2$ невозможны.

пред. Правка 2   0
2023-06-30 03:20:06.0 #

там же получается $$k!\geq n!$$ откуда $$k\geq n$$