Még egy megjegyzés. A bizonyításban lényegében azt mutattam meg, hogy egy körvonal nem ágyazható be folytonosan a számegyenesbe (én háromszögvonallal dolgoztam, de bármilyen egyszerű zárt görbére hasonlóan megy a dolog). Ennél általánosabban igaz a következő: az n-dimenziós gömbfelület nem ágyazható be folytonosan az n-dimenziós euklideszi térbe. Pontosabban: ha f:Sn->Rn egy folytonos függvény, akkor van x eleme Sn úgy, hogy f(x)=f(-x). Ez utóbbi a nevezetes Borsuk-Ulam tétel.
Ez a bizonyítás többet ad, mint amit a 11933-ban állítottam. Nevezetesen: egy f:(0,1)x(0,1)->(0,1) injekciónak minden háromszögvonalon (általánosabban minden egyszerű zárt görbén) van szakadási pontja.
Igazad van, nem voltam elég precíz. Elmondom a javított verziót konkrétabban és részletesebben.
Tegyük fel, hogy az f:(0,1)2->(0,1) injekció folytonos a K nyílt körlemezen. Jelölje g az f megszorítását a K-ra, tehát g:K->(0,1) folytonos és injektív. Legyen a,b,c három pont a K-ban, amik nincsenek egy egyenesen. Ekkor f(a),f(b),f(c) három különböző szám a (0,1)-ben. Az általánosság megszorítása nélkül f(a)<f(b)<f(c). Az a-t és a c-t összekötő szakasz pontjai az (1-t)*a+t*c alakban adhatók meg, ahol t a [0,1] intervallumon fut végig. Ez a szakasz a K-ban helyezkedik el, ezért h(t):=f((1-t)*a+t*c) egy folytonos függvény a [0,1]-ből a (0,1)-be. Tudjuk, hogy h(0)=f(a) és h(1)=f(c), vagyis a Bolzano-tétel miatt valamilyen 0<t<1 számra h(t)=f(b). Az f injektivitása miatt erre a t-re teljesül, hogy (1-t)*a+t*c=b, vagyis b az a-t és a c-t összekötő szakaszon fekszik. Ellentmondás.
Viszont még mindig nem győztél meg, ami persze lehet az én hibám. Ezzel van bajom: "Tegyük fel, hogy nem, tehát f folytonos és injektív egy K nyílt körlemezen. Legyen k a kör középpontja, és m=f(k) annak képe. Ekkor f a K-{k} halmazt folytonosan képezi a (0,1)-{m} halmazra. Ez ellentmondás, mert K-{k} összefüggő, de (0,1)-{m} nem az."
- Egyrészt a (0,1)-{m} az nem egyenlő f(K-{k})-val ez utóbbi csak részhalmaza az előbbinek. Szóval lehet, hogy f(K-{k}) mindig <m, például.
- Másrészt valahogy az is zavar, hogy egy pont nagyon nem zavar be a folytonosságba. Vagyis igazából azt nem látom, hogy a folytonosság klasszikus definíciója (minden epszilonhoz van delta, stb) hol sérül?
Őszintén szólva mi csak egyetemen tanultuk érintőlegesen a matematikának néhány területét de egyikbe se mentünk részletesen bele. Engem csak érdekel ez a téma ezért néztem utána.
Kérdésedre válaszolva a wikipédiában az RSA-séma tétele fejezettől már nem teljesen világos számomra. Vagy pl. miért használják az Euler féle függvényt, mi a szerepe...
De szerintem könnyebben megérteném, az Egyszerű RSA-példa fejezetet mert ott már konkrét számokról van szó.
Ugye jól értem amúgy az első kérdésre adott válaszodból, hogy fordítva is jó lenne, vagyis a véges kettedestörteket véges alakban hagyni? Azaz mindegy, csak állapodjunk meg.
Igen, úgy látom, hogy így is jó a konstrukció. Hiszen ez esetben az összefűzött diadikus tört nem állhat valahonnét kezdve csupa 1-esből, ezen feltétel mellett pedig szintén egyértelmű a diadikus felírás.
Ezt most így hirtelen nem látom, miért van így. Miért van így? :)
Nincs így, hibásat mondtam. Pl. az összefűzés leképezés, amiről beszéltünk, folytonos az irracionális koordinátájú pontokban.
Ami igaz, az a következő: egy f:(0,1)x(0,1)->(0,1) injekció szakadási pontjai sűrűn vannak.
Tegyük fel, hogy nem, tehát f folytonos és injektív egy K nyílt körlemezen. Legyen k a kör középpontja, és m=f(k) annak képe. Ekkor f a K-{k} halmazt folytonosan képezi a (0,1)-{m} halmazra. Ez ellentmondás, mert K-{k} összefüggő, de (0,1)-{m} nem az.
Igen, nem állhat csupa nullából, hisz az a,b sem állhat. Ez ok.
Ugye jól értem amúgy az első kérdésre adott válaszodból, hogy fordítva is jó lenne, vagyis a véges kettedestörteket véges alakban hagyni? Azaz mindegy, csak állapodjunk meg.
Még egy bónusz kérdés: "A függvény egyetlen pontban sem lehet folytonos" Ezt most így hirtelen nem látom, miért van így. Miért van így? :)
A 11917-ben adott válaszom nem volt jó. Valójában nincs szükség a hármas számrendszerben nézni az összefűzött számjegyeket, tehát kettes számrendszerben nézve is injektív a függvény. Ennek oka, hogy a definíció alapján az összefűzött számjegyek egy végtelen diadikus törtet alkotnak (tehát nem áll csupa nullából valahonnét kezdve, vö. 1-es kérdésed), ilyen felírása pedig minden (0,1)-beli számnak csak egy van.
Fú nagyon köszönöm a segítséget, így már menni fog a dolog, egy C programot kell írni erre, de az alap ötlet nemvolt már meg, az volt a gond, de ezek alapján menni fog, nagyon szépen köszi mégegyszer!
Kicsit jobban utánanézve a keresett f(m,n) számoknak neve is van: Delannoy-számok. Kifejezhetők a binomiális együtthatókból, de a képletek nem kifejezetten egyszerűek.
De még így sem tudok elindulni, nem elég kézzelfogható számomra.
Pedig amit mondtam, elég kézzelfogható. Ahogyan a binomiális együtthatókat rekurzívan lehet képezni a Pascal-háromszögben (a háromszögben minden szám a felett álló két szám összege), ugyanígy az említett mennyiségeket is lehet rekurzívan képezni az
f(m,n) = f(m-1,n) + f(m,n-1) + f(m-1,n-1)
képlettel. Tehát: vegyél elő egy kockás papírt, jelölj ki rajta egy origót, és utána minden rácspontra írd rá, hogy hányféleképpen érhető el. Az origóba az 1 kerül, tőle balra és lefelé pedig minden rácspontra a 0. Ezek után használd rekurzívan azt a szabályt, hogy minden 1x1-es rácsnégyzeten a jobb felső csúcsba írt szám a többi három csúcsra írt számok összege. Tehát sorra lehet menni a nemnegatív rácspontokon:
Hát köszönöm a választ! De még így sem tudok elindulni, nem elég kézzelfogható számomra. Legyen egy példa, pl (3,4) pontba eljutni, átlók nélkül, ugye hármat kell jobbra és 4et fel lépni, az összes 7 lépés, tehát 7alatt a 4 kombináció megadja a lehetséges utakat (átlók nélkül) , de nem találok ilyenfajta megoldást, átlókkal. Így átlók nélkül úgy oldottam meg, hogy megnéztem mennyiszer megyek át a megadott ponton, aztán azokat kivontam az összes útból. Viszont ha átlókon is lehet menni úgy egyszerűen nem jövök rá a dolgra, egyénként köszönöm a segítséget :)
Először úgy oldd meg a feladatot, hogy nincs (c,d) pont, amit el kell kerülni. Tehát legyen f(m,n) a lehetséges útvonalak száma az origóból az (m,n) pontba úgy, hogy 1 lépésben 1-et mehetünk jobbra, vagy felfelé, vagy átlósan jobbra felfelé. Erre lehet viszonylag egyszerű képletet kapni, hiszen
f(m,n) = f(m-1,n)+f(m,n-1)+f(m-1,n-1).
Ha az f(m,n)-et már tudod, akkor a feladatodra is tudod a választ, hiszen 0<=c<=m és 0<=d<=n esetén a (c,d)-n átmenő utak száma f(c,d)+f(m-c,n-d), vagyis a feladatbeli utak száma f(m,n)-f(c,d)-f(m-c,n-d).
Köszönöm a választ! Az a baj, hogy már táblázatba foglaltam, de nem találom meg az összefüggést. Az a probléma, hogy az átlós lépéseket nem tudom lekezelni. Ha átló nélkül oldom úgy sikerült az egész feladat, de így nem találom a logikát benne! Esetleg találkozott már valaki ilyen feladattal és tudna adni valami tippet?
Sziasztok, valaki tudna segíteni ebben a feladatban? Az origóból hányféleképpen juthatunk el az (m, n) pontba, ha 1 lépésben 1-et mehetünk jobbra, vagy felfelé, vagy átlósan jobbra felfelé, de úgy, hogy a (c, d) ponton nem mehetünk át.
de azt hittem van valami szebb, ami ilyen elemi műveletekkel, függvényekkel operál
A függvény egyetlen pontban sem lehet folytonos, ezért nem várható, hogy jóval egyszerűbb példa létezzék, mint amit adtam.
1) miért kell, hogy ne végződjenek valahonnét kezdve csupa nullára?
Ez csak azért kell, mert a véges diadikus törtek kétféleképpen is felírhatók diadikus törtként. Pl. a kettes számrendszerben 0.1 ugyanaz, mint 0.0111... Egy definíció esetén egyértelműsíteni kell, hogy melyik felírást használjuk, ha két felírás is van.
2) a jobb oldalt miért hármas számrendszerben kell érteni? Kettesben miért nem jó?
Kettesben azért nem jó, mert akkor nem lesz injektív a függvény. Ennek oka hasonló, mint fent: egyes számok kétféleképpen is előállnak diadikus törtként, tehát a számjegyek nem kaphatók vissza egyértelműen a függvényértékből. Persze a hármas számrendszerben is előfordul ez a jelenség, de csak úgy, hogy az egyik felírás csupa 2-esre végződik valahonnét kezdve, miközben mi csak a 0 és az 1 számjegyeket használjuk definíció szerint.
Köszi szépen. Én is ilyesmire gondoltam, de azt hittem van valami szebb, ami ilyen elemi műveletekkel, függvényekkel operál, és nem a tizedes/kettedes törtbeli leírással.
Két kérdés még:
1) miért kell, hogy ne végződjenek valahonnét kezdve csupa nullára?
2) a jobb oldalt miért hármas számrendszerben kell érteni? Kettesben miért nem jó?
