Jump to content

zanimljiva matematika

Featured Replies

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

  • Replies 1.4k
  • Views 157.1k
  • Created
  • Last Reply

Top Posters In This Topic

Most Popular Posts

Posted Images

  kurdi said:
\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?
  • Author
  kingmaker said:
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.
  Al-Khwarizmi said:
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:
Reveal hidden contents

i 1 konkretniji hint:

Reveal hidden contents

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.

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)...

  • Author

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 by kurdi

  MayDay said:
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.
Reveal hidden contents

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

  kurdi said:
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...
Reveal hidden contents

Edited by Yossarian

  MayDay said:
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.
Reveal hidden contents

  • Author

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)

  • Author

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)

  • Author
  kurdi said:
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.
  • Author

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 by kurdi

  • Author

: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 by kurdi

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

Create an account or sign in to comment

Background Picker
Customize Layout