Matematické Fórum

Anonymystik

Nedávno jsem sem dal zajímavou úlohu o součtových pyramidách. Dám sem ještě jednu trochu podobnou, která mi ale připadá ještě těžší než ty dvě předchozí.
Tentokrát se jedná o rozdílové pyramidy, tj. do každého políčka mimo podstavu vepíšu kladný rozdíl čísel v políčkách pod ním. Uvažme, že máme pyramidu o délce podstavy n+1. Do spodních políček vepíšeme čísla 1^n, 2^n, ..., (n+1)^n. Dokažte, že na vrcholu pyramidy bude číslo n! .

check_drummer · 06. 04. 2012 18:54

↑ Anonymystik:
Ahoj, kam jsem zatím dospěl:

Autor skryl část textu. Zobrazit/skrýt!

Anonymystik · 06. 04. 2012 20:41

↑ check_drummer:

Autor skryl část textu. Zobrazit/skrýt!

vanok · 06. 04. 2012 23:01 — Editoval vanok (07. 04. 2012 11:21)

mala poznamka:

O tomto som uz hovorilna tomto fore v kontexte hladania suctov $1^i+2^i+3^i+....$ ( prispevok #21)

Tie moje schema boli napisane tak ze posledny riadok bol prvy atd...

A volaju sa schema konecnych rozdielov.

Jedna ich zaujimava vlasnost je, ze ma riadok $i$ konstantny a riadok $i+1$ nulovy ( plati to aj keby islo v prvom riadku o polynomy stupna i)

Zaujimava je v takychto schemach lava "strana" trojuholnika ....

Maly priklad co som odkopiroval z mojho davneho prispevku ( tvoj druhy priklad)

1; 8; 27; 64;
7; 19; 37
12; 18
6
0; od piateho riadku budu len nuly ....

co nam LAHKO da
$S(n;4) =1* n + 7*\frac{n(n-1)}{2!} + 12* \frac{n(n-1)(n-2)}{3!}+ 6* \frac{n(n-1)(n-2)(n-4)}{4!}$

Ak vas to zaujima, ako i dokazy, i ked to zacina vychadzat mimo kadru strednej skoly, mozem tu napisat viac o tom.

edit: oprava preklepov

Anonymystik

↑ vanok: Hm, tak jestli jsem tvůj příspěvek pochopil, tak jsi tu úlohu zabil, protože kombinační číslo (n nad 4) = n*(n-1)*(n-2)*(n-3)/4! násobíš číslem 6=3!, tudíž ti vyjde číslo 1/4. Protože člen n^4 se nevyskytuje nikde jinde v celém dlouhém výrazu, tak koeficient u čísla n^4 bude 1/4. To ale není náhoda, protože je známo, že součet 1^3 + 2^3 + ... + n^3 se dal pro velká n aproximovat integrálem funkce f(x)=x^3, což jak známo výjde F(X) = (1/4) * x^4, což odpovídá tomu, že koeficienty u nejvyšší mocniny se nesmí lišit. A protože se tvůj postup dá zobecnit pro součet nejen 3. mocnin, ale obecně k-tých mocnin, tak vlastně není co řešit.
------
Zajímala by mě nicméně ta teorie tvrdící, že součet 1^k + 2^k + ... + n^k = a(1)*(n nad 1) + a(2)*(n nad 2) + ... + a(k)*(n nad k), kde čísla a(1), a(2), ..., a(k) vezmu z levé diagonály naší pyramidy (myslím, že se tomu odborně říká diference n-tého řádu, ale nechci do toho zabíhat, přece jen jsem pořád ještě středoškolák).
------
Jinak moje řešení využívá kombinatorické interpretace, zkuste na to někdo přijít bez složité teorie (-;

vanok · 07. 04. 2012 11:20

↑ Anonymystik:
dalsie poznamky:
Ak pouzivam slovenske nazvy na pojmy ( a nie pseudo odborne) tak je to umyselne.
Za to ze povies "diference" miesto "rozdiel" na teorii nic nezmenis... ale tvojmu vyjadreniu mozno viac stredoskolakov bude rozumiet A takych prikladov je kopa, myslis, ze budes lepsi matematik, ked misto slavneho "per partes", povies " po castiach"?

Tvoj problem zaujimavy uz sam o sebe ... som vobec "nezabil" ako pises, ale skor som ti otvoril, dvere na to aby si videl jeho okolie.... a este je zaujimave vediet, ze taketo problemy sa uz riesili v Starej Cine. A tak ti otvorim este jedny dvere: Tvoje trojuholniky, ci pyramidy podla smeru ako ich pozeras, su suctove alebo rozdielove...

Co pises o znamych faktoch

není náhoda, protože je známo, že součet 1^3 + 2^3 + ... + n^3 se dal pro velká n aproximovat integrálem funkce f(x)=x^3, což jak známo výjde F(X) = (1/4) * x^4,

nemusis ani vediet, lebo prave taketo kombinatoricke metody mozu dokazat vela vlasnosti.

A teraz akoze si celkom dobre formalizoval problem (posledny koeficient je a(k+1) )
$1^k + 2^k + ... + n^k = a(1)*{n \choose 1} + a(2)*{n \chose 2} + ... + a(k+1)*{n \choose k+1}$
Tak skus bez jakejkolvek zlozitej teorie dokazat tento NOVY problem najprv pre male k (=1; 2; 3...)

check_drummer · 19. 04. 2012 22:20

↑ Anonymystik:
Zatím jsem neměl moc času se nad dokončením důkazu zamyslet, ale myslím, že indukcí by to mohlo jít.

Kondr · 19. 04. 2012 23:21 — Editoval Kondr (19. 04. 2012 23:22)

Zdravím, taky se dá říct toto:

Autor skryl část textu. Zobrazit/skrýt!

check_drummer · 22. 04. 2012 10:09

↑ Kondr:
Zdravím,

Autor skryl část textu. Zobrazit/skrýt!

Anonymystik

Zdravím. Pročítal jsem si některé své staré příspěvky a koukám, že tu mám nějaké resty. Slíbil jsem, že zveřejním svoje trikové řešení, ale neudělal jsem to. Takže pokus o nápravu:
Uvažme tedy pyramidu, jejíž spodní řádek tvoří k-té mocniny. Já si ji v rámci přehlednějšího indexování otočím zleva doprava - viz. obrázek pro k=3 :

Označme $C_{k}(r, p)$ číslo, které leží na r-tém řádku, přičemž je p-té zleva (číslujeme od nuly). Pyramidě z prvního obrázku by odpovídala pyramida na tomto obrázku:

Uvažme množinu všech k-ciferných čísel, jejichž cifry vybíráme z množiny $\{1, 2, ..., k+1\}$ . Uvažme dále nějakou její podmnožinu, na jejíž prvky budeme klást následující dva požadavky:
1) vybraných n cifer se v čísle musí aspoň jednou vyskytnout
2) jiných vybraných q cifer se v čísle nesmí ani jednou vyskytnout.
Ukážeme, že počet prvků takovéto podmnožiny je roven $C_{k}(n, q)$ . Použijeme důkaz indukcí:

Všimněme si nejprve 0. tého řádku. Jsou zde čísla $(k+1)^{k}, k^{k}, ..., 2^{k}, 1^{k}$ . Formálně by měl tento řádek odpovídat číslům $C_{k}(0,0), C_{k}(0,1), C_{k}(0,2), ..., C_{k}(0,k)$ . Je tomu tak? Vezměme si kombinatorický význam m-tého čísla zleva $C_{k}(0,m)$ . Je to počet všech k-ciferných čísel, u nichž nekladu žádné požadavky na cifry, které zde musejí být tj. n=0. Naproti tomu ale zakážu některých q=m cifer. Normálně bych každou cifru vybíral z $k+1$ možností, takto se mi výběr zůžil na $k+1-m$ možností. Celkem takových čísel tedy bude $(k+1-m)^{k}$ . Když si uvědomíme, že spodní řádek jsou čísla $(k+1)^{k}, k^{k}, ..., 2^{k}, 1^{k}$ , vidíme, že naše hypotéza je minimálně pro 0. řádek splněna.

Uvažme nyní, že hypotéza platí pro r-tý řádek a ukážeme, že platí i pro (r+1)-vý řádek. Formálně platí v tomto řádku pro každé přípustné m toto: $C_{k}(r+1, m) = C_{k}(r, m) - C_{k}(r, m+1)$ . Co to znamená kombinatoricky?

Uvažme, že se zaobíráme třeba ciframi $1, 2, 3, 4, 5$ a číslem $C_{5}(2,2)$ .
$C_{5}(2,2)$ ... počet těch čísel, které obsahují musí obsahovat cifry $1, 2$ a nesmí obsahovat cifry $4, 5$ .
$C_{5}(1,2)$ ... počet těch čísel, které obsahují cifru $1$ , přitom ale nesmí obsahovat cifry $4, 5$ .
$C_{5}(1,3)$ ... počet těch čísel, které obsahují cifru $1$ , ale neobsahují cifry $2, 4, 5$ .
Jak lze zjistit počet čísel, které obsahují cifry $1, 2$ a přitom neobsahují cifry $4, 5$ ? No třeba tak, že zjistím počet čísel obsahující cifru $1$ a neobsahující cifry $4, 5$ a odečtu od něj počet čísel obsahující $1$ a neobsahující $2, 4, 5$ . Tj. $C_{5}(2,2) = C_{5}(1,2) - C_{5}(1,3)$ . No ale to přesně odpovídá našemu formálnímu požadavku $C_{k}(r+1, m) = C_{k}(r, m) - C_{k}(r, m+1)$ (pro r=1, m=2, k=5), přičemž zobecnění je nasnadě. Je teda jasné, jak kombinatorická interpretace souvisí s tím, že číslo v (r+1)-vém řádku vyrobíme jako rozdíl dvou čísel pod ním. Tím je indukční krok dokončen.

Jaké číslo bude na vrcholu pyramidy? Číslo $C_{k}(k,0)$ . Je to počet k-ciferných čísel, u nichž vyžadujeme, aby bylo použito zvolených k (různých) cifer. No, počet takových čísel je roven počtu permutací těch zvolených cifer, tj. $k!$ . Tím je důkaz hotov.