kms - fórum o príkladoch

14. príklad 3. letnej série 2007/2008

Zadanie:
Každá podmnožina množiny prirodzených čísel $\{x_1,x_2,\dots,x_n\}$ má iný súčet prvkov. Aký najmenší môže byť výraz (v závislosti od $n$ ) $x_1^2+x_2^2+\dots+x_n^2$ ?

Naspäť na príklady | Napíš príspevok

siJqR4oLhI9 <hofs1dle~outlook~com> - 21. 10. 2015 - 12:38:36 z 221.178.182.41

I was seliousry at DefCon 5 until I saw this post.

cituj ma

Kubo - 12. 05. 2008 - 13:26:44 z 193.87.160.132

Tak teraz si ma dostal

cituj ma

Ondráč - 11. 05. 2008 - 22:42:13 z 158.195.169.241

Máš kačku :P Aké vedomosti? Všetky som dnes rano predal na jarmoku...

cituj ma

Kubo - 11. 05. 2008 - 17:26:29 z adsl-dyn166.78-98-70.t-com.sk

Vies cO?
Mal by si sa hambit za svoje vedomosti

cituj ma

Ondráč - 11. 05. 2008 - 10:54:22 z adsl-dyn126.78-99-82.t-com.sk

Tú $n$ -ticu tam máš, ale nemáš tam jej súčet ani... tak keď sa ti to nepodarilo ani sčítať, nemal som ti prečo dať nejaký bod ;)

cituj ma

Kubo - 11. 05. 2008 - 07:06:42 z adsl-dyn166.78-98-70.t-com.sk

A prco mam potom iba 0 bodov?
ved tu n ticu tam mam. nemam sice ze je to nejaky dolny odhad ale nieco som sa snazil ukazovat ze to menej nebude a ze ani viac. hmm.

cituj ma

Ondráč - 10. 05. 2008 - 22:46:41 z adsl-dyn126.78-99-82.t-com.sk

A to ešte budeš kukať, keď uvidíš ako sa to dalo vyriešiť... Stačilo sa pozrieť na
$\sum (\pm x_1 \pm x_2 \pm \cdots \pm x_n)^2,$

kde suma ide cez všetkých $2^n$ kombinácií znamienok. Využitím toho, že každá podmnožina $\{x_1,x_2,\ldots{},x_n\}$ má iný súčet sa dá dokázať
$\sum (\pm x_1 \pm x_2 \pm \cdots \pm x_n)^2\geq \frac{2^{3n}-2^n}{3}$

a jednoduchým roznásobením sumy dostávame

$\sum (\pm x_1 \pm x_2 \pm \cdots \pm x_n)^2=2^n(x_1^2+x_2^2+\cdots+x_n^2).$

Spojením tejto rovnosti a odhadu získame

$x_1^2+x_2^2+\cdots+x_n^2\geq\frac{4^n-1}{4-1}=1^2+2^2+4^2+8^2+\cdots+(2^{n-1})^2.$

Keďže $n$ -tica $\{1,2,4,8,\ldots{},2^{n-1}\}$ spĺňa podmienku o rôznych súčtoch, máme najlepší dolný odhad.

cituj ma

Kubo - 10. 05. 2008 - 17:25:01 z adsl-dyn166.78-98-70.t-com.sk

COOOOOOOOO to je jake huste. a jaky som bol rad ked som videl ze len dvaja poslali 14.tku...

cituj ma

Ondráč - 10. 05. 2008 - 14:00:57 z adsl-dyn126.78-99-82.t-com.sk

Tento príklad zvádza na to, aby ste dokázali, že ak $x_1<x_2<\cdots<x_n$ , tak $x_i\geq 2^{i-1}$ . To ale neplatí. Nespĺňa to napr. množina $\{7,11,13,14,15\}$ , v ktorej $15<2^4$ .

cituj ma