Задачка с биномиальными коэффициентами

[-ЭР-]

Вот знакомый подкинул задачку. У меня с ходу "не схватилось" [img:813c1e1d7d]images/smiles/icon_smile.gif[/img:813c1e1d7d]

Для k >=3 найти наименьшее n для которого выполняется условие

C(n, 1) + C(n, 2) + C(n, 3) + ... + C(n, k) > n^(k-1)

где C(n, k) - обычный биномиальный коэффициент.

[Bravomail]

ну вы даете. тут у людей с простой арифметикой проблемы - не могут плюс с минусом правильно применить (см "де рупь"), а вы тут с биномиальными лезете. будьте проще - и люди к вам потянутся!

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by -ЭР-:
<strong>Вот знакомый подкинул задачку. У меня с ходу "не схватилось" [img:66bb16fb64]images/smiles/icon_smile.gif[/img:66bb16fb64]

Для k >=3 найти наименьшее n для которого выполняется условие

C(n, 1) + C(n, 2) + C(n, 3) + ... + C(n, k) > n^(k-1)

где C(n, k) - обычный биномиальный коэффициент.</strong><hr></blockquote>

[Vladislav_P]

Ну типа, сумма биноминальных коэффициентов - 2^k
=> 2^k > n^(k-1)
дальше не уверен [img:392e20c727]images/smiles/icon_smile.gif[/img:392e20c727]
кажется n >= 3

[-ЭР-]

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by Vladislav P:
<strong>Ну типа, сумма биноминальных коэффициентов - 2^k
=> 2^k > n^(k-1)
дальше не уверен [img:a2ccba42c9]images/smiles/icon_smile.gif[/img:a2ccba42c9]
кажется n >= 3</strong><hr></blockquote>

Вот такая сумма биномиальных коээфициентов равна 2^k

C(k, 0) + C(k, 1) + C(k, 2) + ... + C(k, k)

а нам нужна такая:

C(n, 1) + C(n, 2) + C(n, 3) + ... + C(n, k)

[AK70]

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by -ЭР-:
<strong>

Вот такая сумма биномиальных коээфициентов равна 2^k

C(k, 0) + C(k, 1) + C(k, 2) + ... + C(k, k)

а нам нужна такая:

C(n, 1) + C(n, 2) + C(n, 3) + ... + C(n, k)</strong><hr></blockquote>

Well, couldn't crash this problem in half hour. Which means that it's a little tricky, or I'd say 99% that it's unsolvable [img:68ea036f54]images/smiles/icon_smile.gif[/img:68ea036f54]

This was my attempt:
C(n,i) - is a coefficient at i term of Taylor's serie of F(x)=(1+x)^n, at x=1. The same way you, actually, get Sum[C(m,i), i=0..infinity] = 2^n, because it's F(1) and because higher than n terms are 0.

If the sum which we are looking at is S(k) = Sum[C(m,i), i=1..k]

Then we get an equation:
1+S(k) + R(k+1) = 2^k,
here R(k+1) - is a residual of Taylor's serie. Then we have a theorem of Maclauren (if I'm not mistaken), which gives as the upper limit for R(k+1), it's n derivative of F(t), where 0<=t<=1.
So, I've got R(k+1), meaning I've got an equation for k and n. The problem is that I can't solve it analythically [img:68ea036f54]images/smiles/icon_smile.gif[/img:68ea036f54]

here it is:
1- { C(n,k+1) / 2^(k+1) } > {n^(k-1)-1} / 2^n

[AK70]

double click

[ 12-11-2001: Message edited by: AK70 ]</p>

[Chapaev]

повтор

[ 12-11-2001: Message edited by: Chapaev ]</p>

[Chapaev]

Если теорема, на которую ссылается АК70 верна, то там идет речь о the upper limit for R(k+1).

А насколько он отличается от точного выражения?
По-моему, тут отбрасывается некий бесконечный ряд. А он тоже может к чему-то сходится.

[ 12-11-2001: Message edited by: Chapaev ]</p>

[AK70]

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by Chapaev:
<strong>
А насколько он отличается от точного выражения?

[ 12-11-2001: Message edited by: Chapaev ]</strong><hr></blockquote>

not too much [img:55776e24c0]images/smiles/icon_smile.gif[/img:55776e24c0] there's no infinite serie, because it's a polynomial