Zanimljivi zadaci - elegantna resenja

Zanimljivi zadaci - elegantna resenja 17.07.2008. u 00:24 · pre 222 meseci #1

Posto ima dosta ljudi na forumu mogli bi se i resavati zadaci! Da vidimo neka originalna resenja,ideje...

Evo jednog zadatka sa republickog takmicenja iz matematike za 4. razred gimnazije iz 1976. godine.

ZAD
Dokazati da je za svaki prirodan broj $n$

$\sum^{n}_{k=0}\frac{1}{2^k}(^{n+k}_{ k })=2^n$

Potpis

http://www.svijetfizike.com/

Re: Zanimljivi zadaci - elegantna resenja 17.07.2008. u 11:27 · pre 222 meseci #2

Moze matematickom indukcijom lako da se rjesi.

Re: Zanimljivi zadaci - elegantna resenja 17.07.2008. u 12:35 · pre 222 meseci #3

Dokazati da je prvih $n$ cifara iza decimalne tacke u zapisu broja $(6+\sqrt{35})^n$ jednako 9.

Resenje je elegantno i dokumentovano na ovom forumu.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Zanimljivi zadaci - elegantna resenja 17.07.2008. u 17:02 · pre 222 meseci #4

Citat:

h4su: Moze matematickom indukcijom lako da se rjesi.

To je jasno! Moze li bez nje? Neko originalno resenje?!

Citat:

Nedeljko: Dokazati da je prvih $n$ cifara iza decimalne tacke u zapisu broja $(6+\sqrt{35})^n$ jednako 9.

Resenje je elegantno i dokumentovano na ovom forumu.

Ovakve stvari su nepotrebne za bilo sta u nekoj praksi i zivotu pa se ne bih udubljivao! Ko ovo voli da radi iz hobija super!

Potpis

http://www.svijetfizike.com/

Re: Zanimljivi zadaci - elegantna resenja 18.07.2008. u 15:55 · pre 222 meseci #5

Hajde da probam Petrov zadatak (ovaj koji je Nedeljko izneo sam upravo ja svojevremeno postavio na forum, pa nema smisla da opet pišem isto rešenje

).

Pođimo od identiteta $\sum_{k=0}^n{r\choose k}(-1)^k2^{n-k}=\sum_{k=0}^n{n-r\choose k}$ , za koji se lako vidi da važi za $0\leq r\leq n$ (tada su obe strane jednake $2^{n-r}$ ), ali kako obe strane predstavljaju polinom po $r$ stepena najviše $n$ , i kako se poklapaju u $n+1$ tački, sledi da identitet važi uvek. Stavljajući sada $r=-(n+1)$ ostaje $\sum_{k=0}^n{-(n+1)\choose k}(-1)^k2^{n-k}=\sum_{k=0}^n{2n+1\choose k}$ . Leva strana je jednaka $\sum_{k=0}^n{n+k\choose k}2^{n-k}$ a desna predstavlja zbir prve polovine elemenata $2n+1$ -og reda Paskalovog trougla, a kako su oni (zbog simetričnosti Paskalovog trougla) jednaki drugoj polovini, zbir na desnoj strani iznosi $\frac 1 22^{2n+1}=2^{2n}$ Deljenjem obeju strana sa $2^n$ imamo identitet koji je trebalo dokazati.

Pao mi je na pamet i neki kombinatorni argument, ali o tom potom, kad proverim koliko to ima smisla. Naravno, bilo bi lepo zabeležiti i rešenje indukcijom, ali to bih prepustio nekom drugom.

_{[Ovu poruku je menjao Bojan Basic dana 11.03.2009. u 15:41 GMT+1]}

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Zanimljivi zadaci - elegantna resenja 19.07.2008. u 00:15 · pre 222 meseci #6

Hajmo indukciju!

1.) $n=0$
1=1

2.) $n=m$

$\mathcal{IH}:\sum^{m}_{k=0}\frac{1}{2^k}{{m+k}\choose k}=2^m$

3.) $n=m+1$

$\sum^{m+1}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=\sum^{m}_{k=0}\frac{1}{2^k}{{m+k}\choose k}+\frac{1}{2^{m+1}}{{2m+2}\choose {m+1}}=*$

${{2m+2}\choose {m+1}}=\frac{(2m+2)!}{(m+1)!(m+1)!}=2^{2m+1}$ - ovo treba da se dobije nisam uspeo da ispetljam!

$*=2^m+2^m=2\cdot 2^m=2^{m+1}$

Potpis

http://www.svijetfizike.com/

Re: Zanimljivi zadaci - elegantna resenja 19.07.2008. u 01:55 · pre 222 meseci #7

Citat:

petarm:
3.) $n=m+1$

$\sum^{m+1}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=\sum^{m}_{k=0}\frac{1}{2^k}{{m+k}\choose k}+\frac{1}{2^{m+1}}{{2m+2}\choose {m+1}}=*$

Kud se dede $+1$ u binomnom koeficijentu?

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Zanimljivi zadaci - elegantna resenja 19.07.2008. u 02:26 · pre 222 meseci #8

Greska! Ne treba da se dene!

$\sum^{m+1}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=\sum^{m}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}+\frac{1}{2^{m+1}}{{2m+2}\choose {m+1}}$

Potpis

http://www.svijetfizike.com/

Re: Zanimljivi zadaci - elegantna resenja 19.07.2008. u 12:55 · pre 222 meseci #9

Dobro, ali sad ne možeš primeniti indukcijsku hipotezu.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Zanimljivi zadaci - elegantna resenja 19.07.2008. u 21:08 · pre 222 meseci #10

Dokaz prvog zadatka preko verovatnoće:

Bacajmo novčić $n+k$ puta. Tada izraz $\frac{{n+k\choose k}}{2^{n+k}}$ predstavlja verovatnoću da u eksperimentu dobijemo $n$ ishoda jedne vrste i $k$ ishoda druge vrste. Eksperiment smatramo uspešnim ako se pojavilo $n$ ishoda jedne vrste. To će se sigurno desiti posle najviše $2n$ bacanja (a eventualno i ranije). Dakle, sumiranjem navedenih izraza po $k$ , u granicama od $0$ do $n$ , dobijamo siguran događaj, te suma iznosi $1$ . Rezultat sledi.

EDIT: Desiće se, zapravo, posle $2n-1$ bacanja, po Dirihleu. Gde mi je greščica?

Re: Zanimljivi zadaci - elegantna resenja 19.07.2008. u 23:22 · pre 222 meseci #11

Citat:

Farenhajt
...dobijemo $n$ ishoda jedne vrste i $k$ ishoda druge vrste.

Ovo je dvosmisleno: jesi li unapred fiksirao šta ti je jedna a šta druga vrsta, ili ti je pak bitno samo da odnos bude takav, bez obzira na to šta je šta? Ispravan je prvi rezon, tj. da kažemo „...dobijemo $n$ pisama i $k$ glava“, a ovo naglašavam zato što mi izgleda da si naknadno prešao na drugo tumačenje.

Svejedno, posle praviš mnogo veću grešku:

Citat:

Farenhajt:
Dakle, sumiranjem navedenih izraza po $k$

Ovo ne možeš sumirati, jer su opiti različiti (bacaš $n+k$ novčića, a $k$ je promenljivo).

_{[Ovu poruku je menjao Bojan Basic dana 20.07.2008. u 03:28 GMT+1]}

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Zanimljivi zadaci - elegantna resenja 20.07.2008. u 01:00 · pre 222 meseci #12

A ovakvo tumačenje, recimo?

Stavimo $n$ belih i $n$ crnih kuglica u kutiju, pa nasumično izvučemo $n$ kuglica. Eksperiment je "izvući sve bele kuglice", a nakon prvih $n$ izvlačimo jednu po jednu dok se eksperiment ne okonča - a sigurno će se okončati najdalje do $2n$ -te kuglice.

EDIT: Tu je možda problem nezavisnost daljih izvlačenja. U tom slučaju, možda može ovako: Izvučemo $n+k$ kuglica i konstatujemo jesu li među njima zastupljene sve bele. Ako nisu, vraćamo kuglice u kutiju i ponovo vadimo izvestan broj.

Re: Zanimljivi zadaci - elegantna resenja 20.07.2008. u 02:44 · pre 222 meseci #13

Citat:

Bojan Basic: Dobro, ali sad ne možeš primeniti indukcijsku hipotezu.

$\sum^{m}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=\sum^{\rho-1}_{k=0}\frac{1}{2^k}{{\rho+k}\choose k}=2^\rho-\frac{1}{2^\rho}{{2\rho}\choose \rho}=2^{m+1}-{{2m+2}\choose {m+1}}$

$m+1=\rho$
$m=\rho-1$

$\sum^{m+1}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=\sum^{m}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}+\frac{1}{2^{m+1}}{{2m+2}\choose {m+1}}=2^{m+1}-{{2m+2}\choose {m+1}}+{{2m+2}\choose {m+1}}=2^{m+1}$

Valjda ovako!

Potpis

http://www.svijetfizike.com/

Re: Zanimljivi zadaci - elegantna resenja 20.07.2008. u 03:33 · pre 222 meseci #14

ZAD
Neka su $f(x)$ i $g(x)$ neprekidne periodicne fje sa zajednickim periodom $T$ , definisane na skupu realnih brojeva i neka je $lim_{x\rightarrow+\infty}(f(x)-g(x))=0$ . Dokazati da je $f(x)=g(x)$ za svako $x\in\mathcal{R}$ .

Potpis

http://www.svijetfizike.com/

Re: Zanimljivi zadaci - elegantna resenja 20.07.2008. u 12:39 · pre 222 meseci #15

Mozel ovako kontrapozicijom:

Neka je f(t) razlicito od g(t) za neko t iz R.Tada je posto f i g imaju zajednicki period f(x+k*T) != g(x+k*T), k iz Z.Sada

$lim_{x\rightarrow+\infty}(f(x)-g(x))=lim_{k\rightarrow+\infty}(f(t+k*T)-g(t+k*T)) != 0$ .

P.S
Nisam siguran bas da je ona smjena korektna Petre.
Nemogu da nadjem link za 2 zadatak jel mozete okaciti ovdje.

Re: Zanimljivi zadaci - elegantna resenja 20.07.2008. u 14:27 · pre 222 meseci #16

Citat:

Farenhajt:
Stavimo $n$ belih i $n$ crnih kuglica u kutiju, pa nasumično izvučemo $n$ kuglica. Eksperiment je "izvući sve bele kuglice", a nakon prvih $n$ izvlačimo jednu po jednu dok se eksperiment ne okonča - a sigurno će se okončati najdalje do $2n$ -te kuglice.

Ajd za nezavisnost, ali pri ovakvom eksperimentu nemaš $2^{n+k}$ mogućih događaja.

Citat:

petarm:
$\sum^{m}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=\sum^{\rho-1}_{k=0}\frac{1}{2^k}{{\rho+k}\choose k}=2^\rho-\frac{1}{2^\rho}{{2\rho}\choose \rho}=2^{m+1}-{{2m+2}\choose {m+1}}$

$m+1=\rho$
$m=\rho-1$

Ne, naravno. Kada radiš nešto indukcijom, bitno je da prilikom pozivanja na indukcijsku hipotezu vrednost za koju je primenjuješ zaista bude manja od one s kojom tog momenta radiš — a ne samo da uvedeš smenu kako bi to tako izgledalo. :) U citiranom delu primenjuješ indukcijsku hipotezu za $m+1$ (kako god ti to zvao, a nazvao si $\rho$ ), što ne možeš.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Zanimljivi zadaci - elegantna resenja 20.07.2008. u 15:22 · pre 222 meseci #17

$\sum^{m}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=2\sum^{m}_{k=1}\frac{1}{2^k}{{m+k}\choose {k-1}}$

I sad mozda iskoristiti Paskalovo pravilo

${{m+k}\choose{k-1}}+{{m+k}\choose{k}}={{m+k+1}\choose k}$

odnosno

$2\sum^{m}_{k=1}\frac{1}{2^k}{{m+k}\choose {k-1}}=2\sum^{m}_{k=1}\frac{1}{2^k}{{m+k+1}\choose {k}}-2\sum^{m}_{k=1}\frac{1}{2^k}{{m+k}\choose {k}}=2\sum^{m}_{k=1}\frac{1}{2^k}{{m+k+1}\choose {k}}-2(2^m-1)$

$\sum^{m+1}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=\sum^{m}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}+\frac{1}{2^{m+1}}{{2m+2}\choose {m+1}}$

$\sum^{m+1}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=2\sum^{m}_{k=1}\frac{1}{2^k}{{m+k+1}\choose {k}}-2(2^m-1)+\frac{1}{2^{m+1}}{{2m+2}\choose {m+1}}$

i ovo opet ne mogu da ispetljam:(

Potpis

http://www.svijetfizike.com/

Re: Zanimljivi zadaci - elegantna resenja 20.07.2008. u 20:03 · pre 222 meseci #18

$\sum^{n}_{l=0}(2l+1)$

$n$ - fiksno

$n=2N+l$

$n,N,l\in\mathcal{N}_0$

Ako je $n$ parno ocigledno je i $l$ parno i ako je $n$ neparno onda je i $l$ neparno! Pretpostavljam da je jedini nacin da pokazem kolko iznosi gornja suma je da pokazem kolko iznosi za $n$ parno, $n$ neparno i da pokazem da nema razlike? Voleo bih u svakom slucaju da vidim moze li se ovo ikako resiti drugacije?

$n$ - parno
$l=2q\in\mathcal{N}_0$

$\sum^{n}_{l=0}(2l+1)=\sum^{\frac{n}{2}}_{q=0}(2\cdot2q+1)=\sum^{\frac{n}{2}}_{q=0}(4q+1)=4\sum^{\frac{n}{2}}_{q=0}q+\sum^{\frac{n}{2}}_{q=0}1=\frac{(n+1)(n+2)}{2}$

$n$ - neparno
$l=2p+1$

$\sum^{n}_{l=1}(2l+1)=\sum^{\frac{n-1}{2}}_{p=0}(4p+3)=4\sum^{\frac{n-1}{2}}_{p=0}p+3\sum^{\frac{n-1}{2}}_{p=0}1=\frac{(n+1)(n+2)}{2}$

$\frac{(n+1)(n+2)}{2}={{n+2}\choose 2}$

_{[Ovu poruku je menjao petarm dana 21.07.2008. u 13:30 GMT+1]}

Potpis

http://www.svijetfizike.com/

Re: Zanimljivi zadaci - elegantna resenja 21.07.2008. u 00:28 · pre 222 meseci #19

Zao mi je sto nisam uspeo da isteram ovo sa indukcijom do kraja. Voleo bih da neko drugi istera ako ima vremena da vidim gde sam gresio. A ja bih se iskupio na sledeci nacin
Ja sam dokazao upravo jednu matematicku relaciju koja se cesto koristi u fizici pa sam resio da je okacim ovde racunajuci da ce se nekom svideti.Uz to bice i prica uz ovaj dokaz!
To je operatorska relacija. U fizici se operatori pisu sa kapicom iznad slova ^ npr. $\hat{A}$ . To je uveo Landau (Nobelovac) kada je stigao u Moskvu. Stampari su u to vreme imali problema sa brojnim oznakama pa da bi im olaksao Landau je uveo da se operatori pisu na ovaj nacin.Fizicari tako pisu operatore i danas

. Bitni operatori za fiziku su linearni (za njih vazi princip superpozicije) i ermitski (predstavljeni su ermitskim matricama). Za takve operatore vazi identitet
$[\hat{A},\hat{B}^n]=\sum^{n-1}_{k=0}\hat{B}^k[\hat{A},\hat{B}]\hat{B}^{n-k-1}$
Gde je $[,]$ komutator (operatori su nekomutativne strukture) sa sledecim osobinama
http://www.elitesecurity.org/t330663-Osobine-komutatora

Ja cu pokusati da ovaj identitet dokazem matematickom indukcijom:

1.) $n=1$
$[\hat{A},\hat{B}]=[\hat{A},\hat{B}]$

2.) $n=m$
$\mathcal{IH}$ :
$[\hat{A},\hat{B}^m]=\sum^{m-1}_{k=0}\hat{B}^k[\hat{A},\hat{B}]\hat{B}^{m-k-1}$

3.) $n=m+1$
$[\hat{A},\hat{B}^{m+1}]=[\hat{A},\hat{B}^m\hat{B}]=[\hat{A},\hat{B}^m]\hat{B}+\hat{B}^m[\hat{A},\hat{B}]=*$
iskoristio sam jednu osobinu komutatora za koju vec postoji link u ovoj mojoj poruci

$*=\sum^{m-1}_{k=0}\hat{B}^k[\hat{A},\hat{B}]\hat{B}^{m-k}+\hat{B}^m[\hat{A},\hat{B}]$
Poslednji sabirak je $m$ -ti clan ove sume pa ga mogu uvuci pod sumu. Kada to uradim dobijam

$[\hat{A},\hat{B}^{m+1}]=\sum^{m}_{k=0}\hat{B}^k[\hat{A},\hat{B}]\hat{B}^{m-k}$

Cime je ovaj identitet dokazan. Ako nekog zanima naglasio bih jos zasto je ova relacija vazna u fizici!
Za slucaj da $[\hat{A},\hat{B}]$ komutira sa $\hat{B}$ (naravno u tom slucaju komutira i sa svakim stepenom od $\hat{B}$ ) u zapisu $[[\hat{A},\hat{B}],\hat{B}]=0$ dobija se

$[\hat{A},\hat{B}^n]=\sum^{n-1}_{k=0}\hat{B}^{n-1}[\hat{A},\hat{B}]=n\hat{B}^{n-1}[\hat{A},\hat{B}]$

Posto se u kvantnoj mehanici postulira $[\hat{x}_i,\hat{p}_i]=i\hbar$
lako se dobija

$[\hat{x}_i,\hat{p}^{n}_i]$ ili $[\hat{x}^{n}_i,\hat{p}_i]$

Nadam se da se ovo nekom svidelo!

Ne znam Bojane dal mozda imas neku ideju kako bi se i ovo moglo dokazati bez indukcije?

Potpis

http://www.svijetfizike.com/

Re: Zanimljivi zadaci - elegantna resenja 21.07.2008. u 08:30 · pre 222 meseci #20

Citat:

petarm: $\sum^{n}_{l=0}(2l+1)$

$n$ - fiksno

$n=2N+l$

$n,N,l\in\mathcal{N}_0$

Ako je $n$ parno ocigledno je i $l$ parno i ako je $n$ neparno onda je i $l$ neparno! Pretpostavljam da je jedini nacin da pokazem kolko iznosi gornja suma je da pokazem kolko iznosi za $n$ parno, $n$ neparno i da pokazem da nema razlike? Voleo bih u svakom slucaju da vidim moze li se ovo ikako resiti drugacije?

Prvo, $\sum_{l=0}^n(2l+1)=n^2$ . Račun ti nije tačan. Ne znam odakle ti $4q+1$ i $4p+3$ . A ako već znaš $\sum_{l=0}^n$ možeš ga odmah primeniti na $\sum_{l=0}^n(2l+1)$ .

Jedan način je školska formula za zbir aritmetičke progresije: prvi član plus poslednji član ima isti zbir kao drugi plus pretposlednji itd. Drugi način je da se $2l+1$ napiše kao $(l+1)^2-l^2$ i onda ti se pokrate svi unutrašnji članovi. U vezi uopštenja ove ideje vidi

http://www.elitesecurity.org/p1997028

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Srodne teme