zanimljiva matematika

[Ajant23]

Još jedan srednjoškolski, prilično lagan:U nekoj dalekoj zemlji tradicionalno se koriste školjke kao sredstvo plaćanja. Ništa ne košta ispod 10 školjki. Vlada je donela odluku da se uvede i papirna valuta, koja bi se za početak sastojala od samo dve novčanice u vrednosti od m i n školjki.Koje su moguće vrednosti m i n?edit: tako da bude moguće sve platiti papirnim novcem, naravno...

Važno je da m i n budu uzajamno prosti, i to je to...

[kurdi]

...

Drugo rešenje:

mislim da ne moze nesto brze da se svede od ovog ajantovog.malo je simetricnije mada ne i nesto krace ako gledamo da eksponent razlozimo na cinioce:2^7 = 128 je kongruentno sa 12 (sto deluje gore nego 2^5 kongruentno sa 3, ali lepse posle ide)pa je 2^14 kongruentno sa 144, tj sa -1pa je 2^28 kongruentno sa 1.

[kurdi]

Mislis, sve moguce parove (m,n) treba navesti?Inace, stigao upravo domaci iz P&S sa 5 zadataka. Prva dva su sa cerkom Marijom a peti je varijacija na zadatak sa ponudom da promenis izbor koverte nakon sto si od tri odabrao pogresnu..

i posle kazu da forum nije koristan.

[kurdi]

za skoljke - meni izgleda nije bas jasno sta se pita...cime je iskljuceno resenje m=1, n= bilo sta?da li se trazi da ti mozes da platis bez kusura ili je dovoljno da je moguce da ti on vrati tacan kusur?@ kudravi - 10 i 20 ti ne omogucava da platis 15

[Kudravi Gaucos]

@ kudravi - 10 i 20 ti ne omogucava da platis 15

Fuck, uvek nesto zaboravim :)

[Ajant23]

za skoljke - meni izgleda nije bas jasno sta se pita...cime je iskljuceno resenje m=1, n= bilo sta?

Pa, ničim i 1 je "uzajamno prost" sa svakim drugim brojem. Država ima liberalnu vlast.EDIT: zaboravio navodnike. Edited September 9, 2008 by Ajant23

[kurdi]

Važno je da m i n budu uzajamno prosti, i to je to...

mene buni to sto ako ima kusura onda je ovo dovoljno i bez uslova da nista ne kosta manje 10.a taj uslov je iz nekog razloga dat.dokaz ajantove tvrdnje (i bez ogranicenja cene na 10+) ako ima kusura:

dovoljno je da a*m + b*n = 1 ima celobrojna (ne pozitivna) resenja za a i b. kad mozes da platis 1 onda mozes da platis bilo sta.daklem m i n su uzajamno prosti i recimo m < nrazmotrimo n brojeva oblika a*m gde je a =1, 2... n-1, n.pri deljenju sa n ima n mogucih ostataka (od 0 do n-1)m pri deljenju sa n daje ostatak m, a n*m daje ostatak 0.poanta je da ovih n brojeva (m, 2m, 3m... n*m) svi daju razlicite ostatke.dokaz: pretpostavimo da to nije tako, tj da postoje razliciti x i y zmedju 1 i n takvi da x*m i y*m daju isti ostatak pri deljenju sa n.onda bi (x-y)m bilo deljivo sa n.posto su m i n uzajamno prosti, moralo bi x-y da bude deljivo sa n sto je ocigledno nemoguce posto su x i y razliciti i oba manja od n.elem posto svih n brojeva daje razlicite ostatke pri deljenju sa n, (tacno) jedan od njih daje ostatak 1.znaci postoji neko 0<a<n z akoje je a*m - 1 deljivo sa n, sto je ono sto smo hteli da doakzmeo.

edit: nesto sma sjebao u formatiranju spoilera.

Edited September 9, 2008 by kurdi

[kurdi]

Pa, ničim i 1 je "uzajamno prost" sa svakim drugim brojem. Država ima liberalnu vlast.EDIT: zaboravio navodnike.

ma ok, pitanje nije bilo upuceno tebi.nego ako nema tog ogranicenja onda svako moze da da to trivijalno resenje.

[Ajant23]

mene buni to sto ako ima kusura onda je ovo dovoljno i bez uslova da nista ne kosta manje 10.a taj uslov je iz nekog razloga dat.

Ma, blesav zadatak. Sam je Al-Khwarizmi rekao da je lak. A, poenta 10 školjki je da se shvati da takva informacija ne može imati nikakvu težinu dakle da se odbaci. (To rešavaju uredbom.)

[Al-Khwarizmi]

Naravno da je to 2²⁸-1, to je čovek implicitno rekao i u postavci zadatka.

A jbg, implicitno je jasno tebi, kurdiju i možda još 2-3 forumaša. Ostali, ako uopšte zalaze ovde, moraju malo da mućnu glavom i sami izvedu neke stvari koje vi već imate u svom arsenalu i prepoznajete na prvu loptu. Valjda to i jeste (jedna od) poenti ovog topika.edit: preciznije Edited September 9, 2008 by Al-Khwarizmi

[Al-Khwarizmi]

što se školjki tiče - da, traže se svi mogući parovi, i poenta je da se plaćanje može obaviti bez kusura (sorry, zaboravih to da navedem, mada je kurdi već naslutio iz datog ograničenja).Naravno, (1,n) je trivijalan podskup rešenja.Bitan korak jeste uvideti da moraju biti uzajamno prosti (hvala kurdiju za fin step-by-step dokaz u slučaju sa kusurom... ovde je situacija vrlo slična), posle valjda nije teško uočiti na šta dato ograničenje svodi skup rešenja.

[kurdi]

posle valjda nije teško uočiti na šta dato ograničenje svodi skup rešenja.

nije, al posto bez kusura moze i inspekcijom neka ostane nekome drugom za zabavu.ovo bi zapravo moglo biti zabavno i anagramistima.

[Al-Khwarizmi]

Ajmo onda na nastavak zadatka, možda bude zanimljiv i tebi.U opštem slučaju, ako postoje dve novčanice sa uzajamno prostim vrednostima m i n, koja je najmanja moguća cena počevši od koje se bilo šta može platiti bez kusura?edit: znači tražimo k takvo da se bilo koja cena c >= k može platiti bez kusura

Edited September 9, 2008 by Al-Khwarizmi

[kurdi]

cini mi se da je (n-1)*(m-1), al nemam dokaz.

[Ajant23]

A jbg, implicitno je jasno tebi, kurdiju i možda još 2-3 forumaša. Ostali, ako uopšte zalaze ovde, moraju malo da mućnu glavom i sami izvedu neke stvari koje vi već imate u svom arsenalu i prepoznajete na prvu loptu. Valjda to i jeste (jedna od) poenti ovog topika.

Prvi put sam zašao na ovaj topik, mada teško da je to bio moj arsenal. Pre davna, davna prošlost. Kada sam se nekad susreo sa tom teoremom, drug mi je rekao da ju je rešio na času. Ja razmišljao par dana i gledam sebe kao budalu što je ne reših. Onda mi on kaže da je prvo znao tu lemu, to je bilo neukusno. Kakav crni arsenal. Nego sam eto oslušnuo kurdia bolje nego tebe. Vidim zanimljiva matematika, a i ono kud ćeš bez kusura.Kako bilo. Evo jedno rogobatno rešenje, da barem ostanem veran što sam se mešao. Imamo odmah dva očigledna rečenja:a) (1,k) radi za svaki prirodan broj k.(1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10), (1,11), ...b) (2,k) radi za svaki neparan broj k u opsegu 3 do 11.(2,3), (2,5), (2,7), (2,9), (2,11)Uslov kusura nam kaže da nama odgovaraju takvi brojevi koji svojim sabiranjima mogu da produkuju sve proste brojeve veće od 10, kao i da pokriju stepene prostih brojeva manjih od 10. Ti prosti brojevi dalje očigledno mogu produkovati sve brojeve.Objašnjenje:Ukoliko je cena složen broj, ona se može platiti, odgovarajućim ponavljanjem nekog prostog broja. Ali, prost broj se ne može dobiti drugačije nego da se ponavlja prost broj. Takođe, kako svaki prost broj stepenovanjem izgrađuje bekonačno mnogo mogućih cena, neophodno je da se svaki od njih može dobiti kombinovanjem novčanica.Sada imamo nekoliko uslova neophodnih da se to ostvari.1. Brojevi novčanica moraju biti uzajamno prosti, inače ne bi mogli da daju nijedan prost broj veći od njih2. Kako nemamo formulu prostog broja, imamo uslov da ako su brojevi sposobni da ostvare sve brojeve 6*k+1 i 6*k-1 veće od 10, sposobni su da ostvare i sve proste brojeve i sve stepene prostih brojeva. (Stepenima 2 i tri nećemo se baviti)3. Zbog uslova veće od 10, taj uslov možemo raščlaniti na: a) 6*k+5 ili 6*k+11 b) 6*k+7 ili 6*k+13 (zato što k=0 i k=1 dovoljno pokrivaju).4. Ovaj uslov možemo suziti na to da brojevi koji mogu da izgrade a) 6 b) 5 ili 11 c) 7 ili 13,sigurno jesu rešenje problema.5. Brojeve ne mogu biti i jedan i drugi veći od 5 zato što time ne možemo dobiti ni 10, ni 11.Ostaju mogućnosti, 3, 4 i 5 u kombinaciji sa većim brojem.Nova rešenja su parovi:(3,4) (3+3=6, 3+3+4=11, 3+4=7)(3,5) (3+3=6, 5, 3+5+5=13)Svi ostali parovi otpali su po sledeća tri kriterijuma: a) nisu bili uzajamno prosti, b) nisu uspeli da izgrade 11, b) nisu uspeli da izgrade 13.Sva tri uslova su neophodna. Za uzajamno proste brojeve smo pokazali, a 11 i 13 su moguće cene pa je to neophodno po zadatak.Ostali su nam dakle boldovani parovi. (Svi, očigledno pokrivaju i stepene 2 i 3)Rogobatno, ali eto...edit: tri tačke, promena reči i zaboravio da napišem. Edited September 10, 2008 by Ajant23