zanimljiva matematika

[kurdi]

e sad ono sto ja sda mislim da je pravo resenje za 100 koverata....

jebes sekvencijalni pristup i uslovne verovatnoce, sustina je (kad smo razumeli cikluse iz non-spoiler posta) da se skup od 100, iliti 2N brojeva deli na neki broj disjunktnih zatvorenih ciklusa razlicite duzine.brojka koja je na svom mestu cini ciklus duzine 1.dva broja koja su samo zamenila mesta cine ciklus duzine 2.itd.bitno je ponovo naglasiti i shvatiti da je nemoguce da broj pripada ciklusu kracem od N+1, a da igrac sa tim brojem ne uspe da se nadje.tacnije uvek ce se naci iz tacno onog pokusaja koji je jednak duzini ciklusa kojem njegov broj pripada.e sad kljucni korak je daklem da je jedino bitno da li u toj podeli na cikluse postoji jedan ciklus koji je duzi od 50 (iliti N).a ocigledno moze postojati ujedno i najvise jedan takav ciklus.elem, imamo ukupno (2N)! permutacija, kolko njih su lose?one koje sadrze ciklus duzine N+1, ili N+2, ili.... 2N.ok, aj uzmemo ciklus duzine P.koliko ima permutacija unutar ciklusa? (P-1)!poanta je da u ciklusu svi brojevi moraju biti na pogresnom mestu, i ova razlika izmedju (P-1)! i standardnih P! (gde smeju da budu na svojim mestima) je osnova rezultata.znaci uzmimo brojeve 1, 2... P1 mozemo da stavimo na P-1 mesta (svugde osim na prvo)recimo da ga stavimo na meto 7.onda sedmicu mozemo da stavimo na sva mesta osim 7 (iz ociglednih razloga) i 1 (jer bi to zatvorlo ciklus), znaci P-2 mogucnosti. itd.na kraju koja god brojka da je stavljena pslednja stavljena je na jedino preostalo, mesto br. 1, i time je ciklus zatvoren.e znaci kolko ima ukupno permutacija koje sadrze jedan veliki ciklus duzine P >N, a za osale brojeve nas zabole (mogu svi biti na svojim mestima, ili svi u jednom ciklusu duzine 2N-P, ili stagod)odaberemo P od 2N, sto je (2N)!/[P!*(2N-P)!]2N-P brojeva poredjamo na svih mogucih (2N-P)! nacina i to se skrati u formuli iznad.P brojeva unutar ciklusa poredjamo na (P-1)! nacina i to s ene skrati bas skroz u formuli iznad, istane jedno 1/P.znaci za dato P je broj (losih) permutacija (2N)!/Pa ukupan broj dobrih i losih permutacija je (2N)!daklem,verovatnoca da igra ne uspe je suma 1/P, gde P ide od N+1 do 2Ni.e. 1/(N+1) + 1/(N+2) +..... 1/(2N)opet za N=2 (4 igrac) mozemo da proverimo 1/4+1/3 = 7/12 verovatnoca da izgube, kao sto je ona i pokazala.za veliko N je ova suma jednaka integralu 1/x od 1/N do 1/(2N) sto ce reci ln(2N/N) = ln(2) = 0.69verovatnoca da pobede je:1 - ln(2) = 0.31

[MayDay]

Hm... a da je bilo 1000 ćerki? Ili milion? Kapiram da je opet u pitanju neki red (moraću da se nateram da malo obnovim to gradivo, ne bih li mogao da prepoznam "sumnjive" sume... <_< ), pa što je broj manji to je aproksimacija lošija, pa i odstupanje veće.Btw, i pozicija je bila 37 (100/e, za n=100). Slučajnost? Hm...

hahhahha, al koji trip!! u pozadini mi ide tvin piks na televiziji, a ti uocavas curiosities kao dejl kuper himself..ja vise nisam u stanju da citam ni dijagonalno. nastavljam sutra. laku noc. jbt, zvucim ko NCC

[Al-Khwarizmi]

Čovek treba da zna svoje mogućnosti - pošto moram i da spavam, ja se predao i proguglao za one sultanijice...

O, da... duh magičnog e i te kako sa razlogom provejava... ;)

Edited June 4, 2008 by Al-Khwarizmi

[kurdi]

picko sad me mamim, a krenuo sma da dokazujem 1/e... valjda cu se uzdrzati da ne procitam spiler.jel jasno ovo moje sa kovertima?

[Al-Khwarizmi]

picko sad me mamim, a krenuo sma da dokazujem 1/e... valjda cu se uzdrzati da ne procitam spiler.

Voleo bih da vidim izraz lica ako ipak ne uspeš da odoliš i pročitaš spoiler pre nego što dokažeš... ^_^

jel jasno ovo moje sa kovertima?

Uvod je jasan (ne-matematička priča), a spoilere sam ostavio za sutra, koncentracija mi je trenutno u crvenoj zoni.

[kurdi]

otvorio sam sada :lol:ok, imma izraz (implicitam odlazem aproksimacije) za verovatnocu da M-ti broj od ukupno N bude najveci do tada, i uslovnu verovatnocu da ako vidimo da M-ti broj jeste najveci do sada on zaista jeste najveci i ukupno.e sad jebiga ne mogu dalje da s eskoncentrisem sta kako dakrenem da oduzimam... treba mi verovatnoca da M-ti bude najvecio do sada iako nije stvarno naveci, iloi vec tako nesto.. al sutra, il kad stignem.

[kurdi]

pa jeste, jeste, ne gresis, ali to je isto. mislim ako prihvatimo da je 50 veliki broj.u svakom slucaju za veliko N je [(N/2)!]^2/N! = (1/2)^N. (uz neku malu polinomijalnu korekciju).al da, moja nepaznja u izrazavanju.

ajoj, sta napisah.mislim ovo je tacno al totalno izbrkah sta je N a sta N/2.ovo samo govori da je tacan rezultat za malo manje glupe koji je dala mayday zapravo blizu (1/2)^100, a ne (1/2)^50 ko sto ja tragicno aproksimirah.i ona mala polinomijalna korekcija, od \sqrt{n} nije zanemarljiva nego je to zapravo jedina dobrobit toga sto nisu skroz glupi.danas sam ovo sa kovertima pitao jednog fields-ovca koji trenutno i predaje verovatnocu, i ako nista drugo nije predamnom za ruckom resio (ni provalio strategiju, kad provali izracunace lako).zbog njega se i setih ove svoje gluposti, posto je on odmah rekao ok vidim kako moze za \sqrt{N} bolje od (1/2)^N... ja krenuh da mu objasnjavam kako je ta strategija vec bolja za (1/2)^(N/2) i ispadoh glup.inace ono sa sultanom mi je rekao da je poznato i kao secretary problem, ko hoce da googla.

[kurdi]

inace ono sa sultanom mi je rekao da je poznato i kao secretary problem, ko hoce da googla.

uh jebote, kako je dobro resenje.ja sam odustao od svoje komplikovane algebre uveren da bih mogao da izguram al nije zanimljivo.onda na wiki-u nadjem do jaja jednostavan izraz i resenja u dva reda, al opet mi nije bilo odmah jasno kako su uopste postavili taj izraz.sad kad shvatih, neverovatno kolko je elegantno.koga interesuje, obicnim recima...

neka ih ima N, i on preskoci prvih P.verovatnoca da je neka, bilo koja, recimo M-ta, najsisatija je prosto 1/N, za svako M.verovatnoca da odabere pravu je Suma_po_M[1/N * "verovatnoca da nije vec odabrao pogresnu pre nego sto je stigao do stvarno najsisatije na M-toj pozciji"]ova suma naravno ide od M=P+1 do M=N, a ako je najsisatija u prvih P onda sigurno pusi, i ti slucajevi ne doprinose ukupnoj verovatnoci da izabere pravu.kljucni korak:pogresno je razmisljati da li je recimo druga ili treca najsistaija pre ili posle M, pokusati racunati verovatnoce nekih konkretnih redosleda i slicno.poanta je da medju prvih M-1 mora postojati neka (lokalno) najsisatija.nebitno je da li je ona ukupno druga, peta ili petnaesta po sisatosti.jedino sto je bitno je da li se ta najsisatija od prvih M-1 nalazi u prvih P ili izmedju P i M.ako se nalazi u prvih P, bg ce (ispravno) propustiti sve od P+1 do M-1. ako se nalazi izmedju P i M on ce je pogresno odabrati iako nije ukupno najsisatija.a verovatnoca da se nalazi u prvih P je prosto P/(M-1)dakle konacni odgovor je Suma[(P/N)*1/(M-1)] = (P/N)*Suma[1/(M-1)], od M=P+1 do M=Nsto je (P/N)*ln(N/P)diferenciranje ovoga daje P = N/e

[MayDay]

uh jebote, kako je dobro resenje.ja sam odustao od svoje komplikovane algebre uveren da bih mogao da izguram al nije zanimljivo.onda na wiki-u nadjem do jaja jednostavan izraz i resenja u dva reda, al opet mi nije bilo odmah jasno kako su uopste postavili taj izraz.sad kad shvatih, neverovatno kolko je elegantno.koga interesuje, obicnim recima...

neka ih ima N, i on preskoci prvih P.verovatnoca da je neka, bilo koja, recimo M-ta, najsisatija je prosto 1/N, za svako M.verovatnoca da odabere pravu je Suma_po_M[1/N * "verovatnoca da nije vec odabrao pogresnu pre nego sto je stigao do stvarno najsisatije na M-toj pozciji"]ova suma naravno ide od M=P+1 do M=N, a ako je najsisatija u prvih P onda sigurno pusi, i ti slucajevi ne doprinose ukupnoj verovatnoci da izabere pravu.kljucni korak:pogresno je razmisljati da li je recimo druga ili treca najsistaija pre ili posle M, pokusati racunati verovatnoce nekih konkretnih redosleda i slicno.poanta je da medju prvih M-1 mora postojati neka (lokalno) najsisatija.nebitno je da li je ona ukupno druga, peta ili petnaesta po sisatosti.jedino sto je bitno je da li se ta najsisatija od prvih M-1 nalazi u prvih P ili izmedju P i M.ako se nalazi u prvih P, bg ce (ispravno) propustiti sve od P+1 do M-1. ako se nalazi izmedju P i M on ce je pogresno odabrati iako nije ukupno najsisatija.a verovatnoca da se nalazi u prvih P je prosto P/(M-1)dakle konacni odgovor je Suma[(P/N)*1/(M-1)] = (P/N)*Suma[1/(M-1)], od M=P+1 do M=Nsto je (P/N)*ln(N/P)diferenciranje ovoga daje P = N/e

eh zivote, ja kad sam guglala naisla sam samo na numericko resavanje. a ovo je tako lepo zatvoreno. a jesi fields-ovcu ispricao integralnu verziju sa bg-om i sisatim sultanijicama?

[kurdi]

a jesi fields-ovcu ispricao integralnu verziju sa bg-om i sisatim sultanijicama?

naravno. a kad je on na to rekao "yeah, that's actually known as the secretary problem" ja prvo pomislio da se zajebava, pa mi posle bilo malo neprijatno sto se onolko nasmejah.

[Al-Khwarizmi]

uh jebote, kako je dobro resenje.

Da, odličan zadatak. I ja sam u onom guglanju naleteo na to da je poznat kao secretary problem.

dakle konacni odgovor je Suma[(P/N)*1/(M-1)] = (P/N)*Suma[1/(M-1)], od M=P+1 do M=N

Da... što je drugi oblik onoga što sam ja dobio ovde. Jedino...

sto je (P/N)*ln(N/P)

... što sam mnogo štošta pozaboravljao, pa nisam umeo da prepoznam ln. <_<

Edited June 6, 2008 by Al-Khwarizmi

[kurdi]

Da, odličan zadatak. I ja sam u onom guglanju naleteo na to da je poznat kao secretary problem.

Da... što je drugi oblik onoga što sam ja dobio ovde. Jedino...... što sam mnogo štošta pozaboravljao, pa nisam umeo da prepoznam ln. <_<

ajoj, pa da, ti zapravo jesi vec resio , ali ja jebiga nisam uopste procitao... inace bih ti jos onda rekao da je to to, gotov racun, samo ti fali standardan integral (nemoguce da ne znas da integralis 1/x?). mislim nisam procitao tvoj drugi pasus pazljivo posto mi se posle prvog ucinilo kao pa dobro jebiga to je ocigledno, sad muljanje recima ne pomaze, fora je kako izracunati... ali (iz perpsektive nekoga ko nije sve zaboravio :P ) zapravo je "izracunato" onog trenutka kada skapiras foru sa "lokalnom" konkurencijom. dok sam ja racunao razne druge uslovne verovatnoce (da M-ta bude odabrana, nezavisno od toga da li je stvarno najsisatija, pa da jeste najsisatija obzrom da jeste odabrana itd) koje daju zaista komplikovane redove.a jos pazi ja posle potpuno nezavisno koristim isti izraz (lokalno) i divim se sam sebi kako sam provalio taj pogled na stvari, i to posto sam na wikiju vec procitao (tvoj) izraz, samo je posto oni nisu dali objasnjenje trebalo naknadno da skapiram po kom principu je postavljen :D edit: nego jel jasno bre ono sa kovertima? to je cini mi se ipak jos jaci zadatak (i svakako sokantniji rezultat), sudeci i po reakciji ovog mog matematicara. a racun je (u onoj tacnoj verziji) na kraju zaprvo isti/podjednako (ne)tezak. Edited June 6, 2008 by kurdi

[Al-Khwarizmi]

(nemoguce da ne znas da integralis 1/x?)

Nemaš pojma kako je lako zaboraviti nešto kad se ne koristi.

Ne pamtim kad sam poslednji put morao da rešavam integral, makar i trivijalan. Pa čak i da nađem izvod ičega što nije polinom ili trigonometrijska f-ja... <_< Mislim, da sam napisao u tom obliku, i onda pokušavao da se setim šta ono beše daje 1/x kad se izdiferencira, verujem da bih se setio da je ln, ali tek posle nekog vremena. Al eto neke koristi od foruma - ako ništa drugo, sledeći put će me želja da se ne izblamiram naterati da se malo više potrudim kad bude trebalo ponovo skidati paučinu sa moždanih vijuga.

edit: nego jel jasno bre ono sa kovertima? to je cini mi se ipak jos jaci zadatak (i svakako sokantniji rezultat), sudeci i po reakciji ovog mog matematicara. a racun je (u onoj tacnoj verziji) na kraju zaprvo isti/podjednako (ne)tezak.

Našao sam konačno malo vremena da pročitam to iz spojlera. Jasno je, s tim što mi se onaj prvi zaista čini preterano nategnutim - nepreciznost tamo, aproksimacija ovamo... :P Ali zato svaka čast na sadržaju drugog spojlera!

[kurdi]

mala kurdijeva teorema - dokazati da ne postoji 400 razlicitih rukopisa.

[MayDay]

mala kurdijeva teorema - dokazati da ne postoji 400 razlicitih rukopisa.

jel to znaci da si ti dokazao?ja ne znam ni kako da definisem rukopis. sta su elementi? zakrivljenost u levo/desno, nacin na koji se pisu okrugla slova, da li se slova spajaju ili se nizu odvojeno......ili je ovo neka zajebancija? :bojazljivo: