Пусть число — биномиальный коэффициент, причем нечетный. Рассмотрим следующий коэффициент (примем, что он тоже нечетный): . Поэтому степень вхождения двойки в числа и одинакова. Значит, , нечетны. Пусть число максимально и таково, что (*). Пусть . Получаем: , откуда . . То есть противоречит (*), если , значит, и число можно записать в виде . Минимальное искомое равно .
Если , то для всех числа и имеют одинаковую степень вхождения двойки.
Все это позволяет сделать вывод: условие задачи выполнено тогда и только тогда, когда представимо в виде .
Примечание:
Существует свойство: нечетно тогда и только тогда, когда в двоичной записи числа нет единиц в тех разрядах, где стоят нули в двоичной записи числа . Отсюда, очевидно, следует, что условие поставленной задачи выполняется тогда и только тогда, когда число состоит из одних единиц в двоичной записи.
2 votes Thanks 0
Guerrino
доказательство было проведено в одну сторону, но в обратную очевидно: степень вх. 2 в 2^t-(k+1) и (k+1) одинакова
Answers & Comments
Пусть число
— биномиальный коэффициент, причем нечетный. Рассмотрим следующий коэффициент (примем, что он тоже нечетный):
. Поэтому степень вхождения двойки в числа
и
одинакова. Значит,
,
нечетны. Пусть число
максимально и таково, что
(*). Пусть
. Получаем:
, откуда
.
. То есть
противоречит (*), если
, значит,
и число
можно записать в виде
. Минимальное искомое
равно
.
Если
, то для всех
числа
и
имеют одинаковую степень вхождения двойки.
Все это позволяет сделать вывод: условие задачи выполнено тогда и только тогда, когда
представимо в виде
.
Примечание:
Существует свойство:
нечетно тогда и только тогда, когда в двоичной записи числа
нет единиц в тех разрядах, где стоят нули в двоичной записи числа
. Отсюда, очевидно, следует, что условие поставленной задачи выполняется тогда и только тогда, когда число
состоит из одних единиц в двоичной записи.