zanimljiva matematika

[kgmr]

je l' bila ovde ona pitalica o n zatvorenika koji su dobili mogucnost da zarade slobodu jednosatnim dogovorom? prekidac, samica, jedna prostorija?

[Al-Khwarizmi]

\sqrt{n}to je ocekivana vrednost koraka, a worst case scenarion prosto dva puta tolko.

Kako si došao do ovoga? Ako si prvo jaje bacio sa sredine zgrade, onda ćes u najboljen slucaju zaista dobiti sqrt(n), ali u najgorem slučaju si opet na n/2. Ili si koristio neki drugi način?

[kurdi]

je l' bila ovde ona pitalica o n zatvorenika koji su dobili mogucnost da zarade slobodu jednosatnim dogovorom? prekidac, samica, jedna prostorija?

moguce, ima vise varijanti, pa nisam siguran ni koje su bile ni na koju ti mislis.

Kako si došao do ovoga? Ako si prvo jaje bacio sa sredine zgrade, onda ćes u najboljen slucaju zaista dobiti sqrt(n), ali u najgorem slučaju si opet na n/2. Ili si koristio neki drugi način?

pa drugi nacin, rekao sam odmah da ocigledno moze bolje nego da pocne od n/2 (jer su vrlo razliciti slucajevi ako se razbije i ako se ne razbije, sto nikada nije dobra ideja).1 zesci hint, zapravo nije eksplicitni hint ali mi deluje da mnogo povecava sanse da sine opsta ideja:

resiti prvo za konkretno n=100

i 1 konkretniji hint:

zasto nije dobro n/2 u prvom koraku je jasno... za pocetak malo je i komplikovano razmisljati sta dalje biva.recimo zasto ne n/3, odmah se vidi da je bolje. ako se razbije ograniceni smo na n/3.ako se ne razbije vec u sledecem koraku mozemo da podleimo interval bacanjem na 2n/3 i opet u najgorem slucaju imamo n/3.ali onda isto tako mozemo da krenemo i od n/4, sigurno nece biti vise od n/4 mogucnosti za drugo jaje (samo treba da razmislimo jedan korak vise unapred nego u n/3 slucaju).a sto onda ne n/5...uvek je logicno, dokle god razmisljamo o velikom n i malom m u n/m. i znaci smao je pitanje kada ta logika prestaje.

[Al-Khwarizmi]

Da, skapirao sam u medjuvremenu i sam da je sqrt(n) ono sa cim treba prvo probati...Ali zasto ostatak intervala delis opet na sqrt(n)? Zar ne bi bolje bilo da ides rekurzivno, tj. delis na sqrt(n-sqrt(n))? Tako dobijas bolje resenje od 2*sqrt(n) u najgorem slucaju.

[Al-Khwarizmi]

Verovatno sam bio konfuzan... hoću reći - ako imamo 16 spratova, treba krenuti od četvrtog (t.j. sqrt(16))... Ali ako se jaje tamo ne razbije, ostaje nam opet dva jajeta, a 12 spratova za proveriti. U prevodu, imamo analognu situaciju, samo ovog puta sa 12 spratova... dakle sledeće što treba ciljati nije 4+sqrt(16), nego 4+sqrt(12)...

[kurdi]

u pravu si.u mom resenju je bilo jasno da se sistem rusi ako se prvo jaje ne razbije ni iz poslednjeg planiranog pokusaja (*), ali sam odlucio da je to zanemarljivo za veliko n.sto i jeste u smislu da za moju strategiju ne menja mnogo ocekivanu vrednost.al sad moram ipak da razmislim da li to ukazuje na sustinski bolju strategiju.mislim ne intersuje me toliko prefactor da li ej tacno 2, ali bi bilo mnogo bolje ako moze da se uzvuce drugaciji scaling - ili manji power law ili cak logaritamsko...ja sam se kao polu uverio da ne moze sustinski bolje argumentom da:ako prvo jaje ima a ishoda (kada ce se razbiti) i drugo b ishoda, onda mora biti a*b = n (ili vece), u kom slucaju je tacno da je minimalno a+b = 2 \sqrt(n), za a=b.ali ipak je to malo rupicasto zbog (*)edit: razumeo sam. svakako je malo bolje, smao ne znam jos da li menja da je odgovor proporcijalan \sqrt(n)

Edited July 9, 2009 by kurdi

[Lucia]

imate dva jajeta i zgradu sa n spratova. treba naci koji je to prvi po redosledu sprat odozdo sa kojeg kad bi bacili jaje da bi ono puklo. smemo da koristimo samo ova dva jajeta. zapravo, treba naci strategiju tako da broj koraka bude najmanji moguci.

Zasniva se na polovljenju intervala odonosno binarnom zapisu broja spratova. Logika je da se jaje baci sa polovine broja spratova (ukupnog broja prvi put, posle preostalog broja naviše iznad prethodnog bacanja). Ukoliko pukne onda se sa drugim jajetom krene od prvog sprata datog intervala naviše dok ne pukne – tako saznajemo koji je najniži sprat sa koga je puklo. Ako nam se ne posreći stići ćemo čak do poslednjeg sprata sa koga smo već bacali. Ukoliko je broj spratova (ukupan ili u intervalu) paran bira se niži od dva središnja. Pretpostavlja se da jaje ne mora pući ni bačeno sa najvišeg sprata kao i da može pući već sa prvog sprata.Ako je n kupan broj spratova zgrade, a k je redni broj bacanja kada je prvo jaje puklo, dobija se da je maksimalan broj bacanja oba jajeta suma:(k-1) // broj prethodnih bacanja kada prvo jaje nije puklo+( n – ∑(b[m] *2^m) m=0,(k-2) )/2^(k-1) // broj spratova u našem intervalu tj. preostalom intervalu naviše posle prethodnog neuspešnog bacanja k-1-( n – ∑( b[m] *2^m) m=0,(k-1) )/2^k // broj spratova koji bi ostao kao preostali naviše da nije jaje puklo u k-tom bacanju što kada se uprosti postaje maksimalni broj bacanja oba jajeta u slučaju da je u k-tom bacanju prvo jaje puklo a drugo ne puca nikako:k – 1 + (n / 2^k) + b[k-1]gde je b[m] ostatak pri deljenju sa 2 broja spratova (ukupnog ili intervalskog).To je ustvari odgovarajući bit u binarnom zapisu broja n.(n / 2^k) je celobrojni rezultat deljenja.Maksimalni broj k je odredjen uslovom da preostaje bar još jedan sprat odnosnon >= 2^k + ∑( b[m] *2^m) m=0,(k-1)Jednostavnije je kada se sve prati kroz binarni zapis broja n pa prethodni uslov dovodi da je max k jednako broju binarnih cifara b[m] potrebnih za zapis broja n (poslednje b[m] je uvek 1). Kako k pomeramo kroz binarne cifre na levo (tj. delimo sa 2) levi broj je celobrojni rezultat deljenja (n / 2^k) koji uvećamo za bit na poziciji (k-1) tj. b[k-1] i svemu dodamo broj (k-1).Na primeru kada je n=20 što je u binarnom zapisu 10100 sledi:Maksimalno k je 5.U slučaju da jaje puke već sa prvog bacanja sa sprata #10 idemo posle sa drugim jajetom redom po spratovima #1, #2..#9 dakle imamo maksimalnih ukupno 10 bacanja oba jajeta (ukoliko nam se ne posreći sa drugim jajetom) ili po formuli:k=1 => (1-1) + (binarno 1010) + 0 = 10k=2 => (2-1) + (binarno 101) + 0 = 6 (spratovi: #10,#15,#11,#12,#13,#14)k=3 => (3-1) + (binarno 10) + 1 = 5 (spratovi: #10,#15,#18,#16,#17)k=4 => (4-1) + (binarno 1) + 0 = 4 (spratovi: #10,#15,#18,#19)k=5 => (5-1) + (ništa) + 1 = 5 (spartovi: #10,#15,#18,#19, #20)

Nadam se da sam razumela zadatak. Izvinjavam se na preopširnosti i što više ne vladam matematičkom terminologijom.

[Yossarian]

pa drugi nacin, rekao sam odmah da ocigledno moze bolje nego da pocne od n/2 (jer su vrlo razliciti slucajevi ako se razbije i ako se ne razbije, sto nikada nije dobra ideja).

Ne valja ti ni premalo ni preveliko k, jer ako krenes od pola, dakle k=n/2, imas n/2 koraka ako si baksuz jer onim drugim jajetom moras da proversi sve spratove ispod. Isto kao i "ziheraski" sa k=2, uvek po dva sprata navise. Opet n/2I meni se sqrt(n) cini kao najbolji moguci izbor koraka kojim ides, jer...

Moze li k da se minimalizuje?ako zgrada ima n spratova, a ti ides po k spratova navise, u najgorem slucaju ces imati n/k + k - 1 koraka dok ne otkrijes koji sprat je u pitanju.Funkcija x+n/x ima minimum za x=sqrt(n) pa se valjda i broj potrebnih koraka minimalizuje ako je k=sqrt(n). Jes' da hackujem analizu za problem sa diskretnim brojevima ali stima

Edited July 17, 2009 by Yossarian

[Lucia]

jest 2/(7+3*Sqrt[5])!! necemo jos da pisemo pristup, ako neko zeli da se pozabavi.geometrija rocks!!!

Ako sam možda omašila ideju onog zadatka sa jajima (?) evo da ovde popravim utisak :)Rezultat je isti samo što sam očigledno išla nekim drugim putem.

Odnos površina velikog i malog petougla je(15*cotan(180/5)^2)/4 – 1/4 = 6.8541019662496845446137605030969...dobijeno iz početnog odnosa površina spoljnog vs unutrašnjeg:(4*Pd – Pd1) / (4*Pd1 - Pd)gde je Pd površina jednakostraničnog trougla čija su jednake stranice d ustvari stranice petougla a Pd1 isto jednakostranični trougao istih uglova ali mu je treća stranica isto d.Kako je:Pd = d^2*sin(b)*cos(b)Pd1 = d^2*sin(b) / (4*cos(b))b = (180 – a) / 2 = a / 3a = 3*180/5 tj. ugao petougladobija se prva formula sa kontangensom.

[kurdi]

lucia, cini mi se da si zadatak sa jajima shvatila, ali tvoja strategija daje ocekivane i najgore vrednosti ~ n, sto je mnogo gore od ~ \sqrt(n).yossarian, i ja sam tako inicijalno dosao do toga da mora biti k ~ \sqrt(n), ali me je onda al naterao na dodatno razmisljanje.k = \sqrt(n) sa unapred zadatim fiksnim koracima za prvo jaje daje za najgoru vrednost f(n) = 2\sqrt(n) (zanemarujuci +/- 1 i sl.)sad sam prilicno siguran da je ako ziheraski optimizujemo najgori slucaj bolje resenje, bazirano na alovom pristupu koji je ocigledno konzistentnije rekurzivan:f(n) = \sqrt(2n), ali i prvi korak mora biti k = \sqrt(2n), a ne k = \sqrt(n)(samo sam poluformalno uveren, mada deluje ocigledno, da optimiziranje najgoreg slucaja i optimiziranje ocekivane vrednosti vode istoj strategiji, i da je ocekivana uvek = 0.5 * najgora)elem...najgora vrednost za n spratova se zove f(n).poanta je da ako optimiziramo najgori slucaj onda svaki ishod (od dva moguca) prvog bacanja mora voditi istom najgorem slucaju od tog trenutka nadalje, inace je jedan bolji od toga ali drugi gori, sto ukupno vodi gorem najgorem.sto ce reci mora biti:k-1 = f(n-k) (1)[prvi slucaj ako se razbije, drugi ako se ne razbije]i mora biti:f(n) = 1 + f(n-k) = k (2)[jer smo jednom bacili i ostala nam je ili igra sa n-k i dva jaja, ili igra sa k-1 i jednim jajem, sto smo gore vec izjednacili]nasa primitivnija strategija ocigledno nije konzistenta sa ovim principom jer je k = \sqrt(n), a f(n) = 2\sqrt(n).i bez detalja se vidi da ako se jaje odmah razbije najgori slucaj je k, a ako se ne razbije onda je ~ 2k (ako se konzistentno drzimo polazne pretpostavke da je resenje za n 2\sqrt(n)).sto nije dobro; cim posledice nisu iste znaci da smo mogli u startu bolje da preraspodelimo rizik.jednacine (1) i (2) mozemo i ne pretpostavljajuci resenje da resimo (to leading order) u limitu n >> k >> 1:f(n-k) = f(n) - k*f'(n) = f(n) - f(n)*f'(n), i istovremeno f(n-k) = k - 1 = f(n) - 1sto ce reci: f(n)*f'(n) = 1iliti:(1/2) f^2 = n,f(n) = \sqrt(2n).ali i bez resavanja moze da se proveri gledajuci samo najvece clanove da je f(n) = k = \sqrt(2n) [za razliku od strategije/resenja f(n) = 2\sqrt(n) = 2k]konzistenno sa jednacinama (1) i (2) i nema problem viska faktora 2(korekcije << 1 zanemarujem)

[kurdi]

posto se pojavio i 1 fizicar evo nesto sto nije samo zanimljivo, i nije samo matematika, ali je mnogo kul rezultat...ovo je inace (navodno) srednjoskolski zadatak iz fizike iz cirka 1850.kupa mase M i visine H pluta u vodi okrenuta vrhom na dole.deo kupine visine koji je pod vodom je H/n.(sve je u ravnotezi.)onda od gore na osnovu kupe stavimo teg isto mase M.kupa krene da tone i potone taman toliko da je cela pod vodom pre nego sto se okrene i opet krene na gore.dokazati da je:n^3 + n^2 + n = 7.naravno zanemariti viskoznost vode i sl.(ne verujem da je bas zgodno ispisivati resenja, al ko resi znace da je resio/la)

[kurdi]

sad sam prilicno siguran da je ako ziheraski optimizujemo najgori slucaj bolje resenje, bazirano na alovom pristupu koji je ocigledno konzistentnije rekurzivan:f(n) = \sqrt(2n), ali i prvi korak mora biti k = \sqrt(2n), a ne k = \sqrt(n)(samo sam poluformalno uveren, mada deluje ocigledno, da optimiziranje najgoreg slucaja i optimiziranje ocekivane vrednosti vode istoj strategiji, i da je ocekivana uvek = 0.5 * najgora)

uh, ovo je sve zanimljivije...prvo mislim da sam izracunao ocekivanu vrednost za ovu strategiju [prvo k = \sqrt(2n), a onda rekurzivno po alovom receptu], ali nije prosto ocekivana vrednost g(n) = 0.5 f(n), nego:g(n) = (2/3) * f(n) = (2/3) * \sqrt(2n) = 0.94 \sqrt(n)sto jeste (malo) manje od prostack(ij)e strategije koja daje g(n) = \sqrt(n).znaci worst case je bolji za \sqrt(2), ali ocekivana vrednost vrlo malo.drugo mislim da sam dokazao da ovo jeste najbolja strategija i za minimiziranje ocekivane vrednosti (podrazumevajuci k<<n al to znamo da je tacno za svaku razumnu strategiju).ali nije mi i dalje jasno a priori zasto minimiziranje worst case-a minimizira i ocekivanu vrednost, samo tako a posteriori ispada. tu mora da se krije neki opstiji princip.trece ovaj faktor 2/3 izmedju g(n) i f(n) nam govori da gustina verovatnoce da nabodemo iz nekog konkretnog m-tog bacanja raste linearno sa m (u ovoj strategiji).ovo mislim da razumem.ako je m = c+d, gde je c broj bacanja prvog, a d=m-c broj bacanja drugog jajeta, onda svaka kombinacija (c, m-c) odgovara tacno jednom spratu koji se trazi.i u ovoj strategiji su sve kombinacije moguce, tako da za svako m ima m-1 trazenih kombinacija/spratova koji daju to m (ovo -1 je nebitno za n>>1)recimo samo ako se trazi prvi sprat mozemo nabosti iz dva pokusaja.iz tri pokusaja cemo nabosti ako se trazi drugi ili \sqrt(2n)+1, iz 4 pokusaja ako se trazi 3, \sqrt(2n)+2 ili \sqrt(2n) + \sqrt[2n - 2\sqrt(2n)] + 1, itd.ovo nije tacno u prostackoj strategiji jer je f(n) = 2\sqrt(n), a drugo jaje nikako ne moze biti baceno toliko puta.u ovoj strategiji pak jeste moguce uvek (za svaki ishod prvoj jajeta) pogoditi iz ukupno (worst case) \sqrt(2n) pokusaja.ako se prvo razbije odmah drugo ocigledno ima \sqrt(2n)-1 ishoda, a ako se prvo razbije iz drugog pokusaja opcije za drugo su tacno \sqrt[2n - 2\sqrt(2n)] - 1 = \sqrt(2n) - 2, itd.nije tacno (suprotno mojim inicijalnim pokusajima, ne kazem da je iko drugi to mislio) da se i do minimiziranja ocekivane vrednosti dolazi tako sto svaki ishod prvog bacanja vodi istoj ocekivanoj vrednosti(*), ali to i ima smisla ako je gustina raspodele ukupnog broja bacanja neuniformna, a i nije neki opsti princip, za razliku od worst case-a gde bez obzira na verovatnoce ishoda imamo princip da nikada necemo da dalji worst case bude preveliki.(*) da je ovo tacno ko sto sam ja prvo pokusavao onda strategije koje optimiziraju ocekivanu vrednost i worst case ne bi bile iste.

[kurdi]

a sa tri jajeta?strategija, najgori slucaj, ocekivana vrednost?a sa M jaja?mislim da sada imam generalno resenje za 1 << M << N, i mnogo je dobar zadatak (ako je moje resenje tacno).sve mogu, osim da spavam -_- prostija pre-alovska strategija bi prosto dala najgori slucaj f(N, M) = M * N^(1/M) i ocekivanu vrednost g(N,M) = 0.5*f(N,M).za M=2 sam vec dao sta su po meni resenja.jel mozete da pogodite cemu sve to tezi, koji se broj pojavljuje za veliko M? :D trazio sam posle malo po netu i ima ovaj zadatak, ali samo kao kompjuteraski (google interview i slicno)... naci algoritam (bez dokaza) i onda prakticno naci resenje za konkretne brojeve, N =100 i M=2, ili eventualno za N=1000, M= 3.ovde ima elegantno resenje sa drugacijim pristupom koje se slaze sa \sqrt(2N) za N=100, M=2, i lepo pokazuje (zapravo od toga polazi) zasto verovatnoca za neki konkretni broj bacanja raste lienarno.http://classic-puzzles.blogspot.com/2006/1...gg-problem.html(a ima izgleda i dosta pogresnih resenja po netu)

Edited July 18, 2009 by kurdi

[kurdi]

:kurdi voli da se igra sam:i evo i novog zadatka koji mi je sada pao na pamet na osnovu (suboptimalnog) resenja koje mi je neko ponudio...sta ako ne znamo koliko ima spratova?samo sa dva jajeta, i samo za worst case scenario.u ovom slucaju ocigledno prvi korak ne moze zavisiti od N.ali znaci trazimo strategiju koja minimizira broj pokusaja u funkciji od N koje ne znamo, tj sta god da je N to ce biti worst case scenario, ali bacac ne zna N u napred.ovo nisam ja resio, ne znam sta je stvarno optimalno, ali vidim da resenje koje je neko predlozio radi i kada se N ne zna, a nije mnogo gore od onog kada se N zna.

Edited July 18, 2009 by kurdi

[Jean-Luc Picard]

Nisam siguran da sam dobro razumeo. U onom zadatku sa kupom n (malo en) je visina dela ispod vode??