Критерий нечетности бином. коэффициентов [Теория чисел]

[Whitaker]

TOTAL в сообщении #630923 писал(а):

$C_n^{k+1}/C_n^k=(n-k)/(k+1)$, поэтому $n-k$ и $k+1$ содержат одинаковую степень двойки.

Вам здесь что непонятно?[/quote]
Все непонятно!
Как показать, что они содержат одинаковую степень двойки?
Не знаю вообще как это делать.

[TOTAL]

Whitaker в сообщении #630955 писал(а):

TOTAL в сообщении #630923 писал(а):

$C_n^{k+1}/C_n^k=(n-k)/(k+1)$, поэтому $n-k$ и $k+1$ содержат одинаковую степень двойки.

Вам здесь что непонятно?

Все непонятно!
Как показать, что они содержат одинаковую степень двойки?
Не знаю вообще как это делать.
$C_n^{k+1}/C_n^k=(n-k)/(k+1)$

Это следует из того, что слева оба биномиальных коэффициента нечетные.

[Whitaker]

А они нечетны по условию да?
С этим вроде понятно.
А что дальше теперь?

[TOTAL]

Whitaker в сообщении #630960 писал(а):

А что дальше теперь?

А теперь подумайте про максимальное число вида $2^m$ среди чисел, которые не превосходят $n.$

[Whitaker]

А о чем именно надо думать?
Не совсем Вас понял

[TOTAL]

Whitaker в сообщении #630965 писал(а):

А о чем именно надо думать?
Не совсем Вас понял

Успехов в понимании!

[Whitaker]

Если применить теорему Люка.
$n=n_d2^d+\cdots+n_12+n_0$ и $k=k_d2^d+\cdots+k_12+k_0$, то

$$C_n^k \equiv C_{n_d}^{k_d}\cdots C_{n_1}^{k_1}C_{n_0}^{k_0} \pmod 2$$

Если я правильно понял, то $C_n^k$ будет нечетным если $n_i\geqslant k_i$ для $1\leqslant i \leqslant d$
Скажите пожалуйста это верно?

[Whitaker]

А то, что я написал это есть не что иное как:
$C_n^k$ нечетен тогда и только тогда, когда в двоичной записи числа $k$ единицы не стоят в тех разрядах, где в числе $n$ стоят нули.
А вот как дальше делать я пока не знаю
Помогите пожалуйста

[chessar]

Whitaker в сообщении #630976 писал(а):

Скажите пожалуйста это верно?

Всё верно!

Whitaker в сообщении #631040 писал(а):

А вот как дальше делать я пока не знаю

Ну а дальше то всё просто. Во всех разрядах двоичной записи $n$ должны стоять единицы, ибо если в каком то из разрядов $0$, то найдётся очевидно такое $k<n$, что для него в этом же разряде стоит $1$, т.е. $C_n^k$ - чётное.

[Shadow]

Whitaker в сообщении #630965 писал(а):

А о чем именно надо думать?
Не совсем Вас понял

Задаете рекурентно $C_n^k=C_n^{k-1}\times \dfrac{n-k}{1+k}$. И все они нечетные. "Почти" все числа появятся или в числителе, или в знаменателе. А среди них -максимальная степень двойки. Что будет, если она появится в числителе? А в знаменателе?

[Whitaker]

chessar
все понял за исключением только одного места.
Как понять, что такое $k$ вообще существует?
А так вообще все понятно.

[chessar]

Whitaker в сообщении #631165 писал(а):

Как понять, что такое $k$ вообще существует?

Ну вот смотрите: у Вас есть $n$, в двоичной записи которого есть $0$, т.е. $n$ записывается в виде: $(1\ldots0\ldots)_2$. $0$ скажем стоит на позиции $m$ справа (считаем для определённости разряды с номера 1, т.е. самый крайний справа - это 1-ый разряд), тогда в качестве числа $k$ возьмём число с $m$ двоичными цифрами, последний (справа) разряд которого равен $1$ (соответственно у $k$ на $m$-ой позиции будет $1$). Например возьмите число $2^{m-1}$. Очевидно, что такое $k<n$. Так понятно?

[Whitaker]

chessar
Вы хорошо написали.
Сейчас как раз разбираю.
Вы там написали "возьмите число $2^{m-1}$"
Т.е. взять $n=2^{m-1}$?

[chessar]

Whitaker в сообщении #631194 писал(а):

Т.е. взять $n=2^{m-1}$?

Нет, т.е. взять $k=2^{m-1}$. $n$ у нас зафиксировано, а мы находим такое $k<n$, что $C_n^k$ чётный. Это лишь пример, можно взять любое $k$ с $m$ разрядами, последний из которых $1$, т.е. $k$ в двоичной записи имеет вид:

\[ (\,\underbrace{1\ldots}_m\,)_2 \]

Вот в качестве иллюстрации приведу такой пример. Пусть $n=(1011)_2=11$. Возьмём $k=(100)_2=4$. Тогда $C_{11}^4=330$ - чётное. Или возьмём $k=(111)_2=7$. И т.д.