Zanimljivi zadaci

Zanimljivi zadaci 11.09.2007. u 11:39 · pre 232 meseci #1

Evo nekoliko simpaticnih (barem su meni bili) zadacica.

[1] Na papiru je nacrtano srce. Dokazati da za svaku unutrasnju tacku srca $P$ , postoje dve tacke $A$ i $B$ sa ruba krive, tako da je $P$ sredina duzi $AB$ . (srce smatrati kao zatvorenu neprekidnu krivu bez samopresecanja)

[2] Na stolu se nalaze $2007$ novcica okrenutih glavom ili pismom na gore. Grupa od $2007$ osoba vrsi sledece operacije: prva osoba okrece jedan novcic, druga dva,..., poslednja okrece sve novcice. Dokazati da kako god bili postavljeni novcici na pocetku, $2007$ osoba mogu okrenuti novcice tako da na kraju budu svi okrenuti na istu stranu (na glavu ili na pismo). Takodje dokazati da je ta zadnja strana jedinstveno odredjena (pocetnom konfiguracijom).

[3] Na stolu je 100 novcica, od kojih je 10 okrenuto "na pismo"a 90 "na glavu". Vama je stavljen povez preko ociju i treba da podelite novcice u dve grupe, tako da je u grupama jednak broj novcica okrenutih "na pismo".

_{[Ovu poruku je menjao cassey dana 15.09.2007. u 10:54 GMT+1]}

Potpis

Math is like love. A simple idea but it can get complicated.

Re: Zanimljivi zadaci 11.09.2007. u 12:23 · pre 232 meseci #2

Evo na brzinu rešenja trećeg, a i ostala dva će doći na red.

Odvojimo $10$ novčića na novu gomilu i sve ih okrenemo.

Potpis

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

Re: Zanimljivi zadaci 11.09.2007. u 12:50 · pre 232 meseci #3

Za prvi bi očigledan motiv bio da se srce centralnosimetrično preslika u odnosu na P, i da se onda dokaže da se slika i original moraju presecati u dve tačke...

Re: Zanimljivi zadaci 11.09.2007. u 12:56 · pre 232 meseci #4

Citat:

Bojan Basic: Evo na brzinu rešenja trećeg, a i ostala dva će doći na red. :)
Odvojimo $10$ novčića na novu gomilu i sve ih okrenemo.

Jeste. A evo i malo uopstenje tog zadatka: pored navedenog uslova, gomile moraju da sadrze po 50 novcica.

Potpis

Math is like love. A simple idea but it can get complicated.

Re: Zanimljivi zadaci 13.09.2007. u 14:18 · pre 232 meseci #5

Evo rešenja drugog (mada mi nešto govori da sam ga malo iskomplikovao).

Za neparan broj $n$ nazovimo serijom poteza okretanje najpre $n$ , zatim $n-1$ , onda $n-2$ ... i na kraju jednog novčića. Dokazaćemo indukcijom da za svako neparno $n$ postoji postavka takva da su svi novčići na istoj strani (dakle, sva pisma ili sve glave) i serija poteza koja od nje dovodi do proizvoljne, unapred zadate kombinacije.

Za $n=1$ stvar je očigledna (novčić postavimo suprotno od onoga što nam treba, i prevrnemo u prvom i jedinom potezu). Pretpostavimo da važi za sve neparne brojeve do $n-2$ , i dokažimo za $n$ .

Recimo da zadata kombinacija sadrži dva različito okrenuta novčića. Njih „markirajmo“, i u prva $n-2$ poteza možemo postići takvu situaciju da su svi novčići sem markiranih na željenim mestima: u svakom potezu obavezno okrenemo oba markirana novčića, što nam omogućuje da preostale naštimavamo po indukcijskoj hipotezi. Štaviše, markirani novčići ostaće međusobno na istoj strani (jer smo ih sve vreme prevrtali zajedno), u pretposlednjem potezu okrenućemo oba, i u poslednjem (u kom okrećemo samo jedan novčić) možemo okrenuti odgovarajući (podsetimo se, markirani novčići su u zadatoj kombinaciji različito okrenuti).

Ukoliko je zadata kombinacija takva da su svi novčići okrenuti na istu stranu, poređamo ih ukrug i, krenuvši od proizvoljnog, novčiće okrećemo redom kako stoje po krugu, u svakom potezu nastavljajući tamo gde smo stali u prethodnom. Dokazaćemo da će tako na kraju opet svi novčići biti jednako okrenuti. Zaista, ukupan broj okretanja je $\frac{n(n+1)}2$ . Kako je $n$ neparan, broj okretanja deljiv je sa $n$ , pa kad ovako okrećemo „redom“, jasno je da ćemo se zaustaviti u pravom momentu (upravo nakon što svaki novčić okrenemo po $\frac{n+1}2$ puta.

Time je dokaz indukcijom završen. Iz toga neposredno sledi tvrđenje prvog dela zadatka: izvršićemo unazad seriju poteza kojom se od postavke s novčićima dolazi do početne postavke (koju posmatramo kao zadatu).

Ostaje još dokaz tvrđenja da je kraj jedinstveno određen. Pretpostavimo da se u jednom slučaju dobije jedna završna kombinacija, a u nekom drugom — druga. Primetimo da se tada broj okretanja svakog pojedinačnog novčića u prvom i drugom slučaju razlikuje za neparan broj, a budući da je i $n$ neparno, ukupna razlika u broju okretanja takođe je neparan broj; međutim, kako je ukupan broj okretanja konstantan (gore je izračunato i koliko iznosi), ova razlika morala bi da bude $0$ . Kontradikcija.

Potpis

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

Re: Zanimljivi zadaci 14.09.2007. u 07:12 · pre 232 meseci #6

@Bojan Basic:
Zaista elegantno rešenje

- tnx 4 sharing

Zadatak se može shvatiti i ovako:

Imamo proizvoljan binaran niz $a$ dužine 2007 (dakle, jedini članovi niza su nule i jedinice).
Na njega dejstvujemo serijom $x_1,x_2,...,x_{2007}$ binarnih nizova (svaki od njih dužine 2007) uz pomoć operacije xor.
Za svako $1\le i\le 2007$ broj jedinica u nizu $x_i$ je tačno $i$ .
Operacija xor je komutativna, asocijativna a zbog $x \,\oplus\, 0 = x$ i $x \,\oplus\, 1 = \bar x$ uz odgovarajuću "masku" može da se koristi kao invertor...

Rešenje je izuzetno jednostavno, ali je formalizacija tu činjenicu uspela da prikrije

Pokazaćemo da se svaki polazni niz $a$ može prevesti u konfiguraciju sa svim nulama/jedinicama (u zavisnosti od parnosti broja jedinica koje se pojavljuju u $a$ ). Neka je $k:=\#a$ (broj jedinica u nizu $a$ ).

Označimo sa $\sigma$ bilo koju permutaciju koja sve jedinice niza $a$ premešta na početak niza - dakle, $\sigma a =\underbrace{11\ldots 1}_k\underbrace{00\ldots 0}_{2007-k}$ .
_{zbog preglednosti neću pisati zagrade kod upotrebe f-ja}
Konstruisaćemo nizove $x_i$ čijim dejstvom invertujemo ili sve jedinice ili sve nule u $\sigma a$ i na kraju ćemo odraditi
$\sigma^{-1}$ nad tim nizovima.

Odaberimo nizove $x_i$ tako da za svako $1\le i\le 2007$ važi $x_i=\underbrace{11\ldots1}_i\underbrace{00\ldots 0}_{2007-i}$ .
Neka je $1\le p\le 1003$ proizvoljno. Sada za svako $1\le i\le 1003$ ( $i\neq p$ ) označimo sa $\sigma_i$ permutaciju za koju je $\sigma_i \,x_{2007-i}=\underbrace{00\ldots0}_i\underbrace{11\ldots 1}_{2007-i}=\bar{x_i}$

Sada vidimo da je $\displaystyle{ x_{2007} \,\oplus\sum_{\stackrel{i=1}{i\neq p}}^{1003}(x_i\,\oplus\,\sigma_i\, x_{2007-i})=\underbrace{11\ldots1}_{2007}}$ a da je $\#(x_p \,\oplus\, x_{2007-p})=2007-2p$ .

Neka je $1\le k\le 2006$

1. ako je $k$ neparno, onda možemo pronaći $1\le p\le 1003$ tako da je $k=2007-2p$ . Neka je
$\tau_p$ permutacija koja radi "neoznačeni

šift udesno" za $p$ mesta. Onda ostaje samo da odradimo $\sigma^{-1}\,\tau_p\, x_p$ , $\sigma^{-1} x_{2007-p}$ i $\sigma_i \,x_{2007-i}$ za $1\le i\le 1003$ $i\neq p$ . Tako dobijenom serijom nizova možemo invertovati datih $k$ jedinica u $a$ .

2. ako je $k$ parno, onda je $2007-k$ neparno pa menjamo cilj: želimo da invertujemo onih poslednjih $2007-k$ nula u nizu $\sigma\,a$ - dakle imamo da je $p={k\over 2}$ (setimo se - treba da važi $2007-k=2007-2p$ ) pa ostaje još samo da odradimo $\sigma^{-1}\,\tau_p\,x_p$ , $\sigma^{-1}\,\tau_p\,x_{2007-p}$ i $\sigma_i\, x_{2007-i}$ za $1\le i\le 1003$ $i\neq p$ .

Ako je $k=0$ ili $k=2007$ rešenje se dobija izvršavanjem $\sigma_i\,x_{2007-i}$ $1\le i\le 1003$ (dakle, ovog puta uključujući i $i=p$ ).

Iz konstrukcije je jasno da sledi i jedinstvenost (ako imamo neparan/paran broj jedinica u polaznom nizu - na kraju ćemo imati sve jedinice/nule).

_{Metod koji je izložen može bez poteškoća biti uopšten za svako .}

_{[Ovu poruku je menjao uranium dana 14.09.2007. u 10:00 GMT+1]}

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Zanimljivi zadaci 14.09.2007. u 19:13 · pre 232 meseci #7

@Bojan Basic:

Da, to je i moje resenje. S' tim sto ja nisam redom okretao tj. $n, n-1,...1$ vec proizvoljno, pa je resenje malo krace, ali to je to.

@uranium

Slicno nesto je i meni palo na pamet, ali nisam isao do kraja. Lepo, lepo :).

Potpis

Math is like love. A simple idea but it can get complicated.

Re: Zanimljivi zadaci 15.09.2007. u 01:23 · pre 232 meseci #8

@uranium:

Mrzim formalizaciju, ako me ikad iko pita zašto — pokazaću mu tvoju poruku.

Međutim, među programerima postoji jedna zanimljiva izreka: stil programiranja je kao ... (da ne psujem sad) — svako ima svoj, i niko ne voli tuđ. Mislim da bi se nešto slično moglo primeniti i na rešavanje matematičkog problema

(a lično bih, recimo, umesto uvođenja sigme počeo sa: „Može se bez umanjenja opštosti pretpostaviti da su sve jedinice na početku...“).

Uglavnom, bio sam siguran da tako nešto može proći (zato sam i napisao kako mi se čini da sam malo iskomplikovao), ali ona indukcija mi se prva nametnula. No, uprkos mojim osećanjima prema formalizmu, pažljivo sam, kao svaki dobar referi, proučio tvoje rešenje, i mislim da sam uhvatio nekoliko grešaka (svakako ne suštinskih):

Citat:

Neka je $\tau_p$ permutacija koja radi "neoznačeni

šift udesno" za $p$ mesta. Onda ostaje samo da odradimo
$\sigma^{-1}\,\tau_p\, x_p$ , $\sigma^{-1} x_{2007-p}$

Druga transformacija treba da bude $\sigma^{-1}\,\tau_p\,x_{2007-p}$ , ali ovo je očito samo greška u kucanju. No, čini mi se da je definicija transformacije $\tau_p$ pogrešna; naime, da bi ovo prošlo, moramo $\tau_p$ definisati kao kružni pomeraj ulevo (dakle, ne udesno). Jesam li u pravu?

Citat:

2.
...
pa ostaje još samo da odradimo $\sigma^{-1}\,\tau_p\,x_p$ , $\sigma^{-1}\,\tau_p\,x_{2007-p}$

Uz malopređašnju ispravku oko definicije $\tau_p$ , na samom startu trebalo je $\sigma$ definisati tako da na početku niza nagomila onu cifru koja se pojavljuje neparan broj puta (a ne obavezno jedinicu).

Citat:

Iz konstrukcije je jasno da sledi i jedinstvenost (ako imamo neparan/paran broj jedinica u polaznom nizu - na kraju ćemo imati sve jedinice/nule).

Hm, ovde me nisi ubedio.

Slažem se da tvoja procedura izbacuje sve jedinice ili nule u zavisnosti od parnosti broja početnih jedinica, ali trebalo bi dokazati da to važi za svaku proceduru; čini mi se da to nije očigledno iz tvog rešenja, već da bi se jedinstvenost morala zasebno dokazati.

@cassey:

Citat:

@Bojan Basic:

Da, to je i moje resenje. S' tim sto ja nisam redom okretao tj. $n, n-1,...1$ vec proizvoljno, pa je resenje malo krace, ali to je to.

Ako misliš na situaciju kada su na početku, kao i na kraju, svi novčići okrenuti na istu stranu (čini mi se da u opštem slučaju okretanje proizvoljnim redom ništa ne pomaže, čak i malo komplikuje), da, slažem se da ovo malo pojednostavljuje stvari u odnosu na ono moje obrtanje po krugu.

Uzgred, nemoj još objavljivati rešenje prvog i pojačanog trećeg, baš mi dobro dođe da se malo razgibavam ovih dana.

Potpis

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

Re: Zanimljivi zadaci 15.09.2007. u 16:19 · pre 232 meseci #9

Citat:

Bojan Basic:

Mrzim formalizaciju, ako me ikad iko pita zašto — pokazaću mu tvoju poruku.

Guilty as charged

Mada... ako smem malo da se pravdam

... nisam uvek bio toliko "bolestan"

... za to su kriva moja rana iskustva na beogradskom MATF-u... tipa: "neću da ti priznam tačno izračunat integral jer nisi dokazao da on postoji" ili "otkud znaš da postoji sveden sistem ostataka po modulu $n$ "... i da ne nabrajam još sjaset sličnih situacija nakon kojih sam bio prinuđen [ne bih li izbegao postispitne traume

] da promenim stil iz nekog krajnje filozofskog ["šta je to matematička notacija"] u stil "ja sam čitao samo Bourbakiste i Principia Mathematica"

Citat:

Bojan Basic:
Međutim, među programerima postoji jedna zanimljiva izreka: stil programiranja je kao ... (da ne psujem sad) — svako ima svoj, i niko ne voli tuđ. Mislim da bi se nešto slično moglo primeniti i na rešavanje matematičkog problema

(a lično bih, recimo, umesto uvođenja sigme počeo sa: „Može se bez umanjenja opštosti pretpostaviti da su sve jedinice na početku...“).

Potpuno se slažem, čak sam se u dva maha vraćao da to prepravim... i svaki put odustajao

...verovatno mi je, gledajući one silne jedinice i nule, proradio adrenalin pa nisam uspeo da odolim a da ne napišem i odgovarajući low-level-almost-procedural-proof [iako sam posle ovog iskustva siguran da bi functional-programming-style-proof bio daleko jasniji

]

_{Izgleda da bi trebalo opet da pročitam How to write mathematics - vrlo simpatičan esej Pola Halmoša...}

Citat:

Bojan Basic:
No, uprkos mojim osećanjima prema formalizmu, pažljivo sam, kao svaki dobar referi, proučio tvoje rešenje, i mislim da sam uhvatio nekoliko grešaka (svakako ne suštinskih):

Citat:

uranium
Neka je
$\tau_p$ permutacija koja radi "neoznačeni

šift udesno" za $p$ mesta. Onda ostaje samo da odradimo $\sigma^{-1}\,\tau_p\, x_p$ , $\sigma^{-1} x_{2007-p}$

Druga transformacija treba da bude $\sigma^{-1}\,\tau_p\,x_{2007-p}$ , ali ovo je očito samo greška u kucanju. No, čini mi se da je definicija transformacije pogrešna; naime, da bi ovo prošlo, moramo definisati kao kružni pomeraj ulevo (dakle, ne udesno). Jesam li u pravu?

U pravu si da u tom delu postoji greška ali ne baš to... Cilj mi je bio da se $x_p$ i $x_{2007-p}$ rasporede tako da njihovo xor-ovanje daje niz u kome se svih $2007-2p$ jedinica nalazi na početku. Dakle, ne želim da pomeram $x_{2007-p}$ već samo $x_p$ i to ne za $p$ mesta kako sam pogrešno napisao, već za $2007-2p$ ...znači ispravka: umesto $\sigma^{-1}\,\tau_p\, x_p$ treba da stoji $\sigma^{-1}\,\tau_{2007-2p}\, x_p$

Citat:

Bojan Basic:
...na samom startu trebalo je $\sigma$ definisati tako da na početku niza nagomila onu cifru koja se pojavljuje neparan broj puta (a ne obavezno jedinicu).

Da, to bi skratilo dokaz... mada mi je ionako prva namera bila da samo kažem "drugi slučaj se svodi na prvi..."

Citat:

Bojan Basic:

Citat:

uranium
Iz konstrukcije je jasno da sledi i jedinstvenost (ako imamo neparan/paran broj jedinica u polaznom nizu - na kraju ćemo imati sve jedinice/nule).

Hm, ovde me nisi ubedio. Slažem se da tvoja procedura izbacuje sve jedinice ili nule u zavisnosti od parnosti broja početnih jedinica, ali trebalo bi dokazati da to važi za svaku proceduru; čini mi se da to nije očigledno iz tvog rešenja, već da bi se jedinstvenost morala zasebno dokazati.

Stvar je opet užasno prosta... samo ja očito retko kad ukapiram šta treba objašnjavati a šta ne

Ako bi bilo koja procedura dobijala suprotno od one moje, ona bi morala biti u stanju da invertuje paran broj jedinica ili nula, a to nije moguće, jer u onih ključnih 2006 nizova (poslednji 2007. ne uzimam u obzir jer on invertuje sve) ima neparan broj jedinica ( $1003\cdot 2007$ ), od toga paran broj jedinica moram da potrošim da bih određene elemente ostavio u konačnom neinvertovane, dakle, ostaje mi neparan broj jedinica da potrošim... a da bih invertovao paran broj ma čega, potreban mi je paran broj "grupa" sa po neparno mnogo jedinica. Dakle, nema takve procedure

Na kraju, hvala Bojanu na konstruktivnoj kritici i otkrivenoj grešci, a svima koji su pročitali moj prethodni post se izvinjavam jer skoro da nema dela koji nije zreo za refactoring

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Zanimljivi zadaci 15.09.2007. u 22:42 · pre 232 meseci #10

Citat:

uranium:
U pravu si da u tom delu postoji greška ali ne baš to... Cilj mi je bio da se $x_p$ i $x_{2007-p}$ rasporede tako da njihovo xor-ovanje daje niz u kome se svih $2007-2p$ jedinica nalazi na početku. Dakle, ne želim da pomeram $x_{2007-p}$ već samo $x_p$ i to ne za $p$ mesta kako sam pogrešno napisao, već za $2007-2p$ ...znači ispravka: umesto $\sigma^{-1}\,\tau_p\, x_p$ treba da stoji $\sigma^{-1}\,\tau_{2007-2p}\, x_p$

Jasno mi je šta je cilj, s tim što sam ga ja postigao pomerajući oba člana (ali drugom transformacijom). Po mome — dakle, kružnim pomerajem ulevo — bilo bi:
$\tau_p\,x_p\oplus\tau_p\,x_{2007-p}=\underbrace{000...000}_{2007-p}\underbrace{1...1}_p\oplus\underbrace{11...11}_{2007-2p}\underbrace{0...0}_p\underbrace{1...1}_p=\underbrace{11...11}_{2007-2p}\underbrace{00...00}_{2p}$
No, jasno je da može i kao što si se ispravio. Princip je isti, sve su ostalo nijanse.

Potpis

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

Re: Zanimljivi zadaci 19.09.2007. u 02:23 · pre 232 meseci #11

Evo malo primenjene matematike :)
(mislim da je autor imao previse slobodnog vremena)

http://alas.matf.bg.ac.yu/~djole/kakopedija/

Potpis

Math is like love. A simple idea but it can get complicated.

Re: Zanimljivi zadaci 23.09.2007. u 20:18 · pre 232 meseci #12

Evo rešenja prvog. Zasnovano je na Farenhajtovoj ideji s centralnom simetrijom.

Povucimo kroz tačku $P$ proizvoljnu pravu, i neka je $X$ tačka najbliža tački $P$ u preseku date krive $\Gamma$ i povučene prave, a $Y$ najdalja (ukoliko se dogodi da imamo dve na jednakom rastojanju — tj. dve najbliže ili dve najdalje — one jasno moraju biti s različitih strana tačke $P$ , pa je zadatak rešen). Smemo govoriti o najbližoj tački zahvaljujući neprekidnosti krive $\Gamma$ : zaista, odaberimo infimum, s obzirom na udaljenost od $P$ , skupa presečnih tačaka posmatrane prave i $\Gamma$ , pa i on mora pripadati krivoj $\Gamma$ ; slično rezonujemo za najdalju tačku.

Neka je $\Gamma'$ , $X'$ i $Y'$ centralnosimetrična slika objekata $\Gamma$ , $X$ i $Y$ , redom, u odnosu na tačku $P$ (odmah primetimo $X',Y'\in\Gamma'$ . Želimo pokazati da se $\Gamma$ i $\Gamma'$ moraju seći, iz čega neposredno sledi zaključak zadatka. U to ime, primetimo da $X'$ pripada unutrašnjosti krive $\Gamma$ (zapravo, cela duž $PX'$ pripada unutrašnjosti krive $\Gamma$ , jer bi u suprotnom duž $PX'$ presekla krivu u tački koja je tački $P$ bliža nego tačka $X$ , što je u suprotnosti s izborom tačke $X$ ), dok $Y'$ pripada njenoj spoljašnjosti (rezon je sličan). Dakle, svaka neprekidna kriva koja ih povezuje, pa tako i kriva $\Gamma'$ (zapravo, jedan njen luk), mora preseći krivu $\Gamma$ .

_{[Ovu poruku je menjao Bojan Basic dana 21.03.2009. u 16:43 GMT+1]}

Potpis

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

Re: Zanimljivi zadaci 23.09.2007. u 20:54 · pre 232 meseci #13

Upravo tako :)

Potpis

Math is like love. A simple idea but it can get complicated.

Re: Zanimljivi zadaci 23.09.2007. u 21:23 · pre 232 meseci #14

Možda je zanimljivo spomenuti da je 1977. upravo to bio zadatak B4 na čuvenom The William Lowell Putnam Mathematical Competition

Ovde možete videti još jedan zanimljiv pristup (koji je dovoljno dobar u slučaju konveksnih krivih) a takođe i varijantu Farenhajt - Bašićeve ideje...

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Zanimljivi zadaci 24.09.2007. u 03:01 · pre 232 meseci #15

Slažem se da je gornji pristup na uraniumovom linku dovoljno dobar za konveksne krive, ali, kad je to već pomenuto, naglasio bih kako autor greši u pretpostavci da bi se greška mogla prevazići. Naime, pretpostavljam da je mislio kako bismo mogli ići „malo napred pa nazad“ tako da obe tačke zaista simultano obiđu krivu, ali mu argument pada kod nekih malo neintuitivnijih krivih, poput onih koje sadrže deo funkcije $y=\left\{\begin{array}{ll}x\sin\frac 1 x,&x\not=0\\0,&x=0\end{array}\right.$ . Jednostavno, kada dođemo u blizinu nule, samo ćemo „talasati“ do beskonačnosti, tuda nikad nećemo proći (iako kriva jeste neprekidna!). Ovo nije prvi put da neko upadne u tu zamku: Čarls Stenli Ogilvi (C. S. Ogilvy) polovinom prošlog veka verovao je da je rešio problem (i dalje otvoren) o upisivanju kvadrata u krivu (više informacija o tome ovde, a fina lista referenaca i informacije o najsvežijem progresu mogu se videti ovde). Njegov dokaz kasnije je osporen s više strana, a meni se čini da bi se sve moglo okrpiti osim upravo krivih poput navedene. (Mada, i pored svega, mislim da je njegov pokušaj prošao previše nezapaženo. Ne sećam se više kako sam ga ja pronašao pošto je bilo davno, ali sad nisam uspeo da nađem nijednu referencu na njegov rad.) Dokaz i kritika nalaze se u prilogu.

Elem, kad se uranium već potrudio da locira zadatak, ne bi mi mrsko da potražim zvanično rešenje. Nešto je (očekivano?) jednostavnije od viđenih. U slobodnoj interpretaciji:

Krive $\Gamma$ i $\Gamma'$ moraju se seći jer obe sadrže $P$ (dakle, ne može biti jedna u spoljašnjosti druge) i imaju isti prečnik.

Potpis

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

4325.pdf65.23k

Re: Zanimljivi zadaci 24.09.2007. u 18:55 · pre 232 meseci #16

Lep primer sa $y=\left\{\begin{array}{ll}x\sin\frac 1 x,&x\not=0\\0,&x=0\end{array}\right$ ... ali izgleda da te je Zenon upecao [ "niti možemo stići u nulu, niti možemo iz nje poći"

].
Dakle, čudi me tvoj zaključak o neprolasku kad si lepo primetio da je f-ja neprekidna... znači, možeš da izračunaš "kad" ćeš biti u bilo kojoj tački uključujući i (0,0) i veruj mi da će to "kad" biti različito od "nikad"

.

Tako da do daljnjeg

, mislim da je problem samo u onoj višeznačnosti/konkavnosti (i da nam to esencijalno sprečava slobodno kretanje), jer izgleda da pokušaji u pravcu povratka jednoznačnosti vode ka gubitku neprekidnosti odgovarajuće f-je... mada, treba to još ispitati...

Što se tiče upisivanja kvadrata, trenutno nemam vremena da detaljnije pogledam sav materijal, ali jasno je da je problem izuzetno uzbudljiv - tako da u ime nas koji za njega nismo čuli do sad - veliko hvala!

_{Fajlovi koje si ostavio su identični...(upload glitch?!)... u prilogu ove poruke je (nadam se) onaj nameravani sa kritikama.}

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Gleason - Schaeffer.pdf56.99k

Re: Zanimljivi zadaci 24.09.2007. u 19:19 · pre 232 meseci #17

Citat:

uranium:
Dakle, čudi me tvoj zaključak o neprolasku kad si lepo primetio da je f-ja neprekidna... znači, možeš da izračunaš "kad" ćeš biti u bilo kojoj tački uključujući i (0,0) i veruj mi da će to "kad" biti različito od "nikad"

.

I dalje mi se čini mi da i pored toga (što svakako stoji, nisam ni pokušavao da osporim) nećemo proći, jer prolazak ne vezujemo za vreme već za situaciju u kojoj smo. Dakle, situacija je otprilike: „Ako si došao na rub, u nastavku puta malo se vraćaš, pa zatim ideš napred do sledećeg ruba gde ćeš se opet malo vratiti...“ Dakle, ako ovako vežeš kretanje za te „povratke“, onda zaista nikad nećeš proći; vezivanje za vreme bi svakako bilo bolje (u ovom pogledu), ali samo ako je to uopšte moguće.

Drugim rečima, slažem se da bismo prošli u nekom trenutku, ali problem je što taj trenutak nikad neće doću (za razliku od realnog sveta, kojim se bavio Zenon, gde će svaki trenutak doći). Trećim rečima

, zamisli da pomenutu krivu crtaš olovkom po papiru; ti moraš pojedinačno obraditi svaki zaokret (ne možeš ih sve upakovati u limes), pa krivu nikad nećeš završiti (što nam daje još jedan opis krivih ispuštenih u Ogilvijevom dokazu: one koje se ne mogu nacrtati rukom na papiru

).

Oba priložena fajla zaista su greškom bila identična (sad sam obrisao jedan). Svejedno, drugi nameravani je ovo što si ti pronašao.

Potpis

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

Re: Zanimljivi zadaci 24.09.2007. u 21:16 · pre 232 meseci #18

Da pokušam uz pomoć slike

Recimo da se šetamo po onoj neverending sinusoidi

(u smeru ka "singularitetu") i u svakoj tački se preko neke tačke P preslikamo nazad na krivu... u konačnom ceo deo pre singulariteta biće neprekidno (i neinjektivno) preslikan negde na onaj "donji" deo krive... tako da uopšte ne vidim šta me nakon toga sprečava da nastavim dalje [ through the black hole and beyond

]

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

singularity.PNG18.08k

Re: Zanimljivi zadaci 24.09.2007. u 22:37 · pre 232 meseci #19

Već smo se složili da to preslikavanje „preko neke tačke nazad na krivu“ ne prolazi čim dođemo do nekonveksnih krivih. Ovo što si ti prikazao upravo je ono vezivanje za vreme koje sam pominjao u prošloj poruci (u zavisnosti od toga gde se u određenom trenutku nalazi prva tačka, odaberemo drugu), ali pošto to, upravo rekosmo, ne valja, moramo naći drugi pristup.

Taj pristup sastoji se u tome da obe tačke mrdamo istovremeno, pazeći kad koju treba malo da vratimo. Pošto si se potrudio da mi nacrtaš

šta hoćeš, red bi bio da i ja uradim tako. Naime, pogledaj još jednom ovu sliku (gornju). Pomeramo obe tačke istovremeno, usaglašavajući brzine tako da stalno budu kolinearne s tačkom $P$ , i sad vidi šta se dešava: u jednom momentu tačka $B$ (recimo da smo krenuli s njom nadesno) doći će na ovo „ispupčenje“ (tada će posmatrana prava lokalno biti tangenta na datu krivu u tački $B$ ), i ne bi mogao da nastaviš okretanje kako si počeo; da bi nastavio obilazak, moraš sad okretati tako da se tačka $A$ vraća; to će trajati dok tačka $B$ ne dođe u „udubljenje“, pa onda tačka $A$ opet kreće napred. Moguće je da sam ovo konfuzno objasnio, ali verujem da ćeš shvatiti, jer je u suštini stvarno jednostavno. Samo još primeti da smo u istu situaciju mogli doći i s tačkom $A$ , pa bismo onda tačku $B$ „vraćali“, i tako kad koja dođe na red.

Time smo dobili neki postupak za obilazak cele krive, tako što „ispupčenja“ i „udubljenja“ obradimo jedno po jedno. Međutim, tu leži problem sa spornom krivom: kada jedna od tačaka dođe do okoline nule, šablon nam nalaže da postupamo tako što idemo na jednu stranu dokle treba, pa na drugu dokle treba, pa na prvu dokle treba, pa na drugu dokle treba... i tako mi prolazimo bregove i doline jedno po jedno, a ovo „dokle treba“ stalno će iskakati (i svaki put će „trebati“ manje, ali to nam ne umanjuje tugu).

Potpis

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

Re: Zanimljivi zadaci 25.09.2007. u 01:04 · pre 232 meseci #20

Ovo već postaje komično

Citat:

Bojan Basic:

Taj pristup sastoji se u tome da obe tačke mrdamo istovremeno, pazeći kad koju treba malo da vratimo. Pošto si se potrudio da mi nacrtaš

šta hoćeš, red bi bio da i ja uradim tako. Naime, pogledaj još jednom ovu sliku (gornju). Pomeramo obe tačke istovremeno, usaglašavajući brzine tako da stalno budu kolinearne s tačkom $P$ , i sad vidi šta se dešava: u jednom momentu tačka $B$ (recimo da smo krenuli s njom nadesno) doći će na ovo „ispupčenje“ (tada će posmatrana prava lokalno biti tangenta na datu krivu u tački $B$ ), i ne bi mogao da nastaviš okretanje kako si počeo; da bi nastavio obilazak, moraš sad okretati tako da se tačka $A$ vraća; to će trajati dok tačka $B$ ne dođe u „udubljenje“, pa onda tačka $A$ opet kreće napred. Moguće je da sam ovo konfuzno objasnio, ali verujem da ćeš shvatiti, jer je u suštini stvarno jednostavno. Samo još primeti da smo u istu situaciju mogli doći i s tačkom $A$ , pa bismo onda tačku $B$ „vraćali“, i tako kad koja dođe na red.

Opis je sasvim jasan, i upravo to sam i hteo da kažem onim crtežom... samo obrneš stvari - šta je bio kodomen sada uzmeš da je domen...
_{Naravno, čak i ako se ograničimo samo na ovaj thread, to ne bi bio prvi put da jedan drugome objašnjavamo ono što drugi već zna

Doduše...verovatno sam ja to radio češće...}

Citat:

Bojan Basic:

Time smo dobili neki postupak za obilazak cele krive, tako što „ispupčenja“ i „udubljenja“ obradimo jedno po jedno. Međutim, tu leži problem sa spornom krivom: kada jedna od tačaka dođe do okoline nule, šablon nam nalaže da postupamo tako što idemo na jednu stranu dokle treba, pa na drugu dokle treba, pa na prvu dokle treba, pa na drugu dokle treba... i tako mi prolazimo bregove i doline jedno po jedno, a ovo „dokle treba“ stalno će iskakati (i svaki put će „trebati“ manje, ali to nam ne umanjuje tugu).

Ja se zaista izvinjavam što postajem periodičan

ali gde ti tu vidiš problem? U svakoj "krivini" (ili bregu/dolini) mi smo imali jedan jedini izbor u kom smeru da krenemo i koji od preseka sa pravom da izaberemo tako da se ne vratimo u već pređenu tačku [na tom luku] a da ona f-ja ostane neprekidna... Dakle, ne vidim da sad tu treba da se umeša neka božanska/ljudska inteligencija pa da odluči da li da krenemo "napred" ili "nazad" [gledajući domen]... Znači mi unapred imamo jasan algoritam za svaku krivinu, pa samim tim i za sve njih...

Ako se i dalje ne budemo slagali [ a verovatno nećemo biti te sreće

] mislim da sasvim spokojno možemo prebaciti raspravu u neke filozofske, logičke ili skupovno-teorijske vode...

Hajde da vidimo ovakav primer:

neka je $g: \mathb{N}\rightarrow \{0,1\}$ i neka je $g(n)=1\Longleftrightarrow n \,\,$je prost$$
jasno je da imamo algoritam koji nam posle konačno mnogo koraka nedvosmisleno govori da li je dati broj prost ili nije.
Da li bi ti sad prihvatio da je f-ja $g$ dobro definisana na celom $\mathb{N}$ ?

Ako ne prihvataš - onda je to tvoj filozofski stav i ja to apsolutno poštujem, pa je to onda kraj nesporazumima

, a ako prihvataš, e onda bih voleo da mi objasniš u čemu je suštinska razlika između te i one prethodne situacije sa krivom

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Srodne teme