Lajos
Eredeti szerző: jotunder
Március tizenötödike alkalmából Széchenyi-díjjal tüntették ki Pósa Lajos matematikust. Nem tudom matematikus lennék-e, ha a gimiben nem Lajos az egyik matematikatanárom. Azt hiszem az a legvincentesebb köszöntés, ha egyszerűen csak elmondok egy játékos feladatot, amit még gyerekként hallottam tőle.
Van egy Hilbert Hotel New Yorkban. Afféle hagyományos New York-i hotel, minden emeleti ablakból egy tűzlétra vezet egy olyan ablakhoz ami egy emelettel lejjebb van. Mint minden rendes New York-i hotelben, minden egyes emeleten csak véges sok ablak van. Azonban, mint minden Hilbert Hotel-ben, az emeletek alulról-felfelé a természetes számokkal vannak megszámozva. A kérdés az, hogy van-e olyan út amelyik a földszintről vezet tűzlétrákon keresztül, úgy, hogy minden lépésben felfelé haladunk.
Ezt a feladatot akkor kaptam tőle (a pontos eredeti szövegre már nem emlékszem, csak a hotelre és a tűzlétrára), amikor már elég jól megtanított a Hilbert Hotelekre.
Ez volt az első találkozásom a kompaktsággal, persze akkor még nem tudtam erről. És soha nem felejtem el. Köszönöm, Lajos.
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16522196-6933ef0aae0f2' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16522196&origin=www.orulunkvincent.hu&obj_id=192691293-16522196-6933ef0aae0f2&n=1' data-name='like-post-frame-192691293-16522196-6933ef0aae0f2' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>
zavart érzek az erőben.
Ha a minden emeleti ablakból vezet egy lépcső az alatta lévő emelet valamelyik ablakához, valamint a főccintre is, akkor töjk mindegy hogy az emeletek számozása a gyök minusz Pí * X szerint kiszámolt vagy rovarfajokról nevezzük el őket, mindenképpen fel lehet menni a szálloda tetejire.
Ha az emeletek betűkkel lennének jelölve, más lenne a megoldás?
Tudtommal a földszintről sosincs tűzlétra (és a feladatban sem említed, h lenne), tehát nem.
Hilbert-szalloda=olyan szalloda, amiben vegtelen sok szoba van. Mivel minden emeleten veges sok szoba van, nem lehet a szinteket betukkel vagy rovarfajokkal szamozni.
@dvhr: Ezek szerint az emeletei végtelen számúak? Mert ebben az esetben akkor sem lehet feljutni, hha a földszintről is van tűzlétra.
@dvhr:
Sajnálatos módon a feladat kiírása szerinti hotelben véges számú szoba van minden emeleten.
De ha végtelen számú is van, ha a minden emeleti ablakból vezet létra az alatta levő emelet valamelyik ablakához, akkor minden ablakhoz vezet létra, ergo csak függőleges irányú haladással bejárható a főccinttő a tetőig.
Ha véges számú szoba van, akkor viszont hiányzik a kiírásból egy feltétel, hogy az egyes emeleteken azonos számú szoba van-e.
@kiskii:
ha jól sejtem itt végtelen sok emelet van, minden emeleten véges sok ablakkal.
ergo tető sincs, csak egy fölfelé vezető utat kell keresni (és az sem kell, hogy minden emeleten ugyanannyi ablak legyen)
A Hilbert Hotel klikkelhető. A wikipedia oldalán minden pontosan el van magyarázva.
@jotunder: sportoljon az onyiscsenkó
@kiskii:
1. Van egyes szint, kettes szint, hármas szint, és így tovább.
2. Minden szinten véges sok ablak van, és ezekből egy darab létra vezet le, valamelyik ablakba ami az alatta lévő szinten van. Az is lehet, hogy a négyes szinten van három ablak, de ebből pontosan egy olyan van, amelyikbe vezet létra az ötös szintről. Azaz, ha véletlenül alulról elindulsz felfelé és a négyes szinten nem ehhez az ablakhoz érsz, akkor vége az utadnak.
3. A végesség fontos. Képzeld el, hogy minden szinten végtelen sok ablak van, és az n-edik szint ablakainak számozása n, n+1, n+2,stb
Az n-edik szint k-as ablakából az n-1-ik szint k-as ablakába vezet létra. Ez azt jelenti, hogy ha az első szinten elindulsz a k-adik ablakból akkor a k-adik szintig tudsz csak felfelé menni.
@jotunder: Nem vagyok egy matek-zseni, de a „paraszti logika” szerint az első szint első ablakából mindenképpen vezetnie kell végtelen magasságig létrasornak? („minden emeleti ablakból egy tűzlétra vezet egy olyan ablakhoz ami egy emelettel lejjebb van”) 🙂
A feladat elég homályosan van itt felvezetve, tán nem is értem.
De az könnyen belátható, hogy tetszőleges n-re az n-edik szintig van felfelé út. Hiszen ha az n-edik szinten választok egy szobát, (akármelyiket), akkor onnan van létra eggyel lefele, és onnan is és onnan is egész a földszintig.
Viszont nincs garancia arra, hogy ez a kiválasztott szoba rajta lenne egy végtelen felfelé vezető útvonalon, hisz már az is lehet, hogy ebbe a szobába fentről nem vezet létra, vagy ha vezet, lehet, hogy abba a szobába nem vezet, ahonnan az a létra jön.
Szóval meggyőződésem, hogy van ilyen út felfelé (bár persze bizonyítani nem tudom) de abban is biztos vagyok, hogy lentről nem lehet ezt az utat megtalálni.
Adott k szint. A k-adik szinten n ablak. Mivel a k-1.ik szintre vezet le n létra egy-egy ablakhoz ezért a k-1. szinten is minimum n ablaknak kell lennie.
Ebből következik, hogy a k-1. szintről a k-2. szintre is minimum n tűzlétra vezet le. És így tovább. Egészen k-(k-1). szintig, ami ugyebár az első. és onnan annyi tűzlétra vezet le, amennyi ablak az 1. szinten van. Ha valahol több ablak van, akkor onnan már n+x tűzlétra vezet le.
Innen nem nehéz megállapítani, hogy van olyan útvonal amin csak fölfelé menve is megtudjuk tenni az utat. Azt csak matematikai logikával nehéz megállapítani melyik útvonal is az, de nem ez volt a kérdés.
Kivéve, ha a tűzlétrák nem dőlnek össze vissza, hanem egyenesen merőlegesen lefelé mennek, és ha egy ablakhoz össze vissza mindenhonnan jöhetnek fentről tűzlétrák, akkor ez a megoldás nem feltétlenül jó.
De akkor is ott van az az állítás, hogy minden ablakból vezet le tűzlétra. vagyis hiába vezet le csak a z. szinten egy ablakhoz mondjuk a z+1. szint m ablakából m tűzlétra, a z-1. szinten van olyan ablak ahová a z. szint ezen kitüntetett ablakából vezet le tűzlétra. És a z-2. szinten lesz olyan ablak ahová a z-1. szint inkriminált ablakából vezet le tűzlétra. És a z-3. szinten lesz olyan ablak…
Kicsit bonyolult.
Vagyis kivéve, ha tűzlétrák dőlnek összevissza és nem egyenesen mennek lefele.
Bocsi.
És még egy apróság. Nem lehetetlen, hogy a legfelső emeleten nincs ablak – ott trollok laknak. Nos ebben az esetben senki nem mászik oda fel. A feladat leírásából nem következik automatikusan az ottani ablaklét. Azt ki kell zárni a megoldáshoz.
@mantegna: Vannak a „zsakutcas” ablakok. Ezek olyan ablakok, ahonnan NEM vezet felfele tuzletra. Ilyen ablakok bizony letezhetnek. Vannak a „2-zsakutcas” ablakok, ahonnan egyet meg lehet felfele menni, de kettot mar nem. Altalaban vannak a „k-zsakutcas”-ablakok, amelyekbol k-1 lepest lehet felfele tenni. Egy ablak „cuki” ha semmilyen k-ra nem k-zsakutcas.
Vegyuk eszre, hogy az elso szinten van cuki ablak. Kell, hogy legyen, mert ha minden ablak valamilyen k-ra zsakutcas lenne, tekintettel arra, hogy az emeleten csak veges sok ablak van nem lehetne tetszolegesen magasra feljutni a szintrol. A kovetkezo amit eszre kell venni, hogy cuki ablakbol el lehet jutni felfele egy cuki ablakba. Persze, hiszen, ha csak zsakutcas ablakba lehetne eljutni egy lepesben, akkor maga az ablak is zsakutcas lenne.
A megoldas tehat az, hogy elindulunk egy cuki ablakbol, abbol vezet felfele egy ut egy masik cuki ablakba, es igy tovabb.
Ez a feladat valojaban a Konig Lemma neven ismert tetel.
De régen foglalkoztam matematikával…
Viszont a kiírásban az szerepel, hogy az emeletek természetes számokkal vannak számozva. Amikor régen ilyesmit próbáltak nekem tanítani, akkor azt mondták, hogy a nulla nem természetes szám. Ebből számomra az következik, hogy nincs földszint (ha azt tekintjük nulladik emeletnek).
@Sörhastáncos: First floor….
@jotunder: Hát igen, így jár aki nem ért hozzá, és izomból trollkodik a feladat elolvasása után 🙂 (De legalább leszögeztem előre, hogy nincs hozzá sok közöm.)
Amúgy meg a földszintre nekem a ground floor vagy a downstairs rémlett. De megnéztem a szótárban, New Yorkban, ahol a hotel van, tényleg first floor néven ismerik.
Csak ismetelni tudok: Lajos, koszonom!
Bar en nem lettem matekszakos, matematikus, de a matekszakkorok, a matektaborok jok voltak.
Lajos megerdemli a dijat abszolut. 🙂
Készitsünk három, a szokásostól eltérő számozású dobókockát, hogy körbeverjék egymást!
Moszkvában, a Szovjetunió fővárosában megépitették a világ legnagyobb szállodáját. Olyan sok szoba van benne, hogy számozásukhoz nem a természetes számokat, hanem a 0 és 1
közötti valós számokat használták. Fel is használtak minden ilyen számot. Nagyon elszontyolodtam, amikor megérkezésemkor kiderült, hogy a szálloda tele van. Azonban Grisa, a segédportás (némi vodka elfogyasztása után) megigérte, elintézi, hogy nekem is kerüljön szoba, de senkinek ne kelljen kiköltözni. Hogyan?
@dvhr: Szerintem egyszeruen csak huzott neked egy (szoba)szamot 0 es 1 kozott egy vegtelen urnabol 🙂
@Hector: Bocsanat, Hector, ugy ertettem, hogy senkinek sem kell kikoltozni a szallodabol. Szobak kozotti atkoltozesre persze szukseg van.
@dvhr: Igen, szoval Grisa olyan jofej, hogy azt mondja neked, hogy valaszd ki te magad a szobat. Ekkor Grisa atkoltozteti, a szobaban lako(ka)t a szobaszam negyzetenek szobaja, ahonnan atkoltozteti az ott lako(ka)t a szobaszam kobenek szobajaba, es igy tovabb. Igy mindenkinek jut szoba. Persze koltoztetesi modbol is vegtelen all rendelkezesre.
@Hector: kekeckedések:
1. Na jó, de mennyire végtelen? (Itt már végre különbözik a feladat az alapváltozattól, miszerint a szobákat természetes számokkal számozzák, ld. jotunder linkjét.)
2. A megoldásod nem tökéletes, kihúzhatod Grisánál a gyufát, ha a 0-s vagy az 1-es szobát választod.
@dr Brcskzf Gröőő:
1. Megszamlalhatatlanul vegtelen. |Szobak szama| = |R|
2. A „kozotti” nekem nyitott intervallumra utal. Ha esetleg megse, akkor ha dvhr a 0 vagy 1-es szobaba szeretne menni, akkor Grisa elokapna a 0 es 1 kozotti nyitott itervallumu valos szamokat tartalmazo urnajat es abbol huzna egyet. Majd oda koltoztetne a kiturt vendegeket, es innentol ismet a szobaszam hatvanyainak iteralasaba kezdene.