Question

Найдите наименьшее n

Answer 1

Пусть число $r=\frac{n!}{k!(n-k)!}$ — биномиальный коэффициент, причем нечетный. Рассмотрим следующий коэффициент (примем, что он тоже нечетный): $\frac{n!}{(k+1)!(n-k-1)!}=\frac{n!(n-k)}{k!(k+1)(n-k)!}=r\frac{n-k}{k+1}$. Поэтому степень вхождения двойки в числа $n-k$ и $k+1$ одинакова. Значит, $n-k=2^{\alpha}x,\; k+1=2^{\alpha}y$, $x,y$ нечетны. Пусть число $m$ максимально и таково, что $2^{m}-1< n$ (*). Пусть $k=2^{m}-1$. Получаем: $n-2^m+1=2^{\alpha}x,\; 2^{m}=2^{\alpha}y$, откуда $m=\alpha$. $n-2^{\alpha}+1=2^{\alpha}x \Leftrightarrow n+1=2^{\alpha}(x+1)\geq 2^{\alpha+1}$. То есть $m=\alpha+1$ противоречит (*), если $x>1$, значит, $x=1$ и число $n$ можно записать в виде $2^{t}-1$. Минимальное искомое $n$ равно $2^{11}-1=2047$.

Если $n=2^t-1$, то для всех $k$ числа $2^t-(k+1)$ и $k+1$ имеют одинаковую степень вхождения двойки.

Все это позволяет сделать вывод: условие задачи выполнено тогда и только тогда, когда $n$ представимо в виде $2^t-1$.

Примечание:

Существует свойство: $C_{n}^{k}$ нечетно тогда и только тогда, когда в двоичной записи числа $k$ нет единиц в тех разрядах, где стоят нули в двоичной записи числа $n$. Отсюда, очевидно, следует, что условие поставленной задачи выполняется тогда и только тогда, когда число $n$ состоит из одних единиц в двоичной записи.