Найдите наименьшее n. Created by vandriichuk. matematika-ru

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

July 2022 1 11 Report

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

Answers & Comments

Guerrino

Пусть число $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$ состоит из одних единиц в двоичной записи.

2 votes Thanks 0

Guerrino доказательство было проведено в одну сторону, но в обратную очевидно: степень вх. 2 в 2^t-(k+1) и (k+1) одинакова

Guerrino ^комм. не актуален

Answers & Comments

Helpful Links

Helpful Social