A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Megjegyzések az 1147. gyakorlathoz
Gondoljuk, hogy előttünk fekszik az ‐ egész számok összes lehetséges elrendezése az 1147. gyakorlat úthálózatának pontjain, továbbá hogy minden egyes elrendezés mellett fel van tüntetve a szomszédos számpárjai közti különbségek legkisebbike, , valamint legnagyobbikuk, . Kérdezzük, mi a talált összes értékek legnagyobbika, , és mi a talált értékek legkisebbike: . Bebizonyítjuk, hogy mindkét keresett érték -tal egyenlő, mégpedig úgy, hogy egyrészt külön-külön belátjuk a , illetőleg egyenlőtlenséget, másrészt példát adunk olyan elrendezésre, melyben , illetőleg . Az előbbire már az 1147. gyakorlat megoldása tartalmaz példákat, az utóbbira példa az 1. ábra.
1. ábra I. Tegyük fel, hogy van olyan elrendezés, melyben egyetlen különbség sem kisebb -nél: . Egy ilyen elrendezésben egy számmal szomszédos pontokon nem állhatnak az -tól -ig terjedő egész számok. Nem minden esetében tartozik a kizárt szám mindegyike az elrendezendő számok közé, azonban az és számok mindegyike valóban legalább számot zár ki, és legföljebb számot enged meg szomszédjaként. Először ezek helyzetével foglalkozunk, ezeket típusú számoknak nevezzük, a náluk kisebbeket -, a nagyobbakat pedig -típusúaknak. Állítjuk, hogy bármelyik -típusú számtól mindegyik másik -számhoz a hálózat páros számú útszakaszát tartalmazó útvonalon jutunk át. Szemléletesebben mondhatjuk ki ezt annak az észrevételnek a felhasználásával, hogy a csomópontok kiszínezhetők két színnel úgy, hogy minden útszakasz két végpontja különböző színű. Állításunk ekkor azt mondja, hogy az elrendezésben mind a négy -szám ugyanolyan színű ponton áll, hiszen páros számú útszakaszból álló, nem zárt útvonal végpontjai megegyező színű pontok. (A 2. ábra a) és b) része azt mutatja, hogy a kis körút, ill. a középső körút jelű pontjából kiindulva , útszakasz megtételével mely ponthoz érünk el; egy a nagy körúton kijelölt csomópontból való kiindulás megfelelő ábrája úgy adódik -ból, hogy felcseréljük a sugárutak végpontjainak adatait.)
2. ábra Amennyiben vegyesen világos és sötét ponton állnak a -számok, eloszlásuk a két színre vagy vagy . Ezek kizárása végett gondoljunk a -számokkal szomszédos pontok betöltésére. Két ugyanolyan színű pontnak együttvéve legalább szomszédja van ‐ hiszen egy pont , ill. 3 másikkal szomszédos aszerint, hogy a középső vagy valamelyik szélső körút megy át rajta ‐, továbbá közös szomszédaik száma legföljebb , ti. amikor pontosan az egyik a középső körúton áll. Így eloszlás esetén a négy -számnak együttvéve legalább szomszédja lenne. Másrészt az -típusú számok közül az a legnagyobb, ami még felléphet legalább egy -szám mellett, a , a -típusú számok közül pedig a legkisebb ilyen a . Így -szám szomszédjaként szóba sem jöhet más szám, mint az , , , (-típus) és , , , (-típus). Ennyi pedig kevés a mondott pont betöltéséhez. Hasonlóan a eloszlás esetén a három egyszínű pontnak együttvéve legalább szomszédja van, a másik színűnek legalább , együtt ismét több, mint ahány - és -típusú szám van. Ezek alapján mondhatjuk, hogy mindegyik -szám pl. világos ponton áll. Megmutatjuk, hogy a sötét pont nem tölthető be a követelmény megtartásával. A sötét pontokban nyilván vegyesen állnak - és -típusú számok, valamelyik típus mindenesetre többségben van, hiszen a pontok száma páratlan. Mondhatjuk, hogy pl. -szám van több (ugyanis minden számunk helyére az őt -re kiegészítő számot írva újra megfelelő elrendezést kapunk, és abban minden egyes -, -, -típusú szám helyén rendre egy -, -, -típusú szám áll), így a sötét ponton álló -számok száma legföljebb . Tekintsük e számok második szomszédait (amelyek persze szintén sötét ponton állnak). Minden pont legalább másikkal áll másod-szomszédságban (2. ábrák), ezért minden sötét ponton álló -számnak van legalább két -típusú másodszomszédja. Különbségük legalább , mert közös szomszédjuk csak az -típusúnál nagyobb és a -típusúnál kisebb szám lehet; ezért csak -típusú szám szerepelhet sötét ponton, de közülük a -es sem, mert az ezt legalább -gyel meghaladó számok közül csak egy szerepelhet, a -as. Emiatt legfeljebb három -típusú szám állhat sötét ponton, s legalább három -típusú, náluk legalább -gyel nagyobb másodszomszédjuk van, így pedig a -as sem léphet fel. Ugyanígy a -es, végül az -es sem, így valóban nem tölthető be a sötét pont, hiszen -típusú szám csak van, és valóban nem lehetséges elrendezés. II. Egy olyan elrendezésben, melyben , az , , , számok egyike sem állhat a középső körúton. Ehhez belátjuk, hogy az , , az , , a , és a , számpárok egyikének tagjai sem állhatnak egymástól útszakasznyinál kisebb távolságban. Az első három párban a különbség legalább , viszont útszakaszon a legnagyobb megengedett különbséggel is ‐ mondjuk így: feszítetten is ‐ csak különbség alakulhat ki. és pedig azért nem állhat útszakasznyi távolságban, mert bármely pontból bármely olyan másikba, amely tőle útszakasznyira van, mindig vezet két, közös közbülső pontot nem tartalmazó útvonal (2. ábrák), és nem állhat mindkét útvonal mentén a feszített , , , számsorozat. Mármost a középső körút pontjaitól csak ‐ másik pont van legalább útszakasznyi távolságra, és ennyi az alábbiak szerint kevés a mondott szám elrendezésére. Ha pl. az -es számot a 3. ábra pontjába írjuk be ‐ jelképesen ‐, akkor és számára csak a , pontok jönnek szóba, így pedig a -es szintén csak -ben állhatna, mert -tól , , és vannak legalább útszakasznyira, -től pedig , , és , és e két felsorolásban csak közös. Hasonlóan adódik állításunka -es, -es és -as számra.
3. ábra Ezek szerint, az ábra betöltését az -essel kezdve, lényegében csak jön szóba, és ekkor és számára , és közül kettő választandó. A , pár nem választható, mert az előbbiekhez hasonlóan -ra vezet; az , párból egyértelműen , az , pár pedig mellőzhető, mert tükörképe az utóbbinak a tengelyre nézve. A , számpárra fent mondottak érvényesek az , párra is, ezért a -os csak -ben vagy -ben állhat. Folytassuk az , , elhelyezést. A ‐ különbség nem lehet feszítetten , azaz , mert -ből -ba -n át is, -n át is eljuthatunk, s nem lehet . Így , és miatt , azaz , továbbá az , pontokba csak és irható. Ugyanígy miatt , ezért , így pedig , végül . A , kiindulás hasonlóan adja egymás után egyértelműen a , , , elhelyezést. Mindig érvényes, hogy ha az és számok távolsága útszakasz, akkor a egységnyi növekedés a köztük vezető két, közös közbülső pont nélküli útvonal egyikén az , , , számokon megy végbe, másikukon pedig az , , , számokon át, mert az egyetlen még gondolható , , , sorozat amazok mindegyikét lehetetlenné, teszi. (A fenti két példán kívül a két végpont úgy is állhatna még egymáshoz képest, mint pl. és .) Most már könnyen adódik, hogy a -as szám nem helyezhető el. Ugyanis egyrészt a , pár távolsága is legalább útszakasz, másrészt az iméntiek szerint a , távolság is legalább . Ha ugyanis és távolsága , akkor a köztük levő két útvonal egyikén , , , áll, holott a -est vagy -be, vagy -ba írtuk, és ezek egyike sem szomszédos sem -mel, sem -val, ahol a -es állhat. Mármost -től és -tól legalább útszakasznyira , , , , ill. , , , van, tehát a -as részére csak a foglalt és felelne meg.
Lásd ezen számban, 215. o.Lényegében véve ezt használta ki az 1147. gyakorlatban látott a) és b) elrendezés, a számokat,,kicsikre'' és,,nagyokra'' kettéosztva. |