Feladat: 1962. évi Kürschák matematikaverseny 2. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Császár Zoltán ,  Kóta József ,  Máté Attila ,  Pósa Lajos ,  Sebestyén Zoltán 
Füzet: 1963/március, 100 - 107. oldal  PDF  |  MathML 
Témakör(ök): Egyéb sokszögek geometriája, Szabályos sokszögek geometriája, Kombinatorikus geometria síkban, Gráfelmélet, Euler-féle poliédertétel alkalmazásai, Kombinatorikai leszámolási problémák, Geometriai egyenlőtlenségek, Pont körüli forgatás, Ponthalmazok, Skatulyaelv, Egyéb szinezési problémák, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1963/március: 1962. évi Kürschák matematikaverseny 2. feladata

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.

I. megoldás. Egy konvex n-szögben d átlót választunk ki úgy, hogy közülük bármely kettőnek legyen közös pontja (1. ábra). Két csúcsot akkor mondunk szomszédosnak, ha kiválasztott átló köti össze őket. Egy csúcs akkor i-edfokú, ha i csúccsal szomszédos. Az i-edfokú csúcsok számát ai-vel jelöljük. Ezek szerint

a1+a2+a3+...≤n,
hiszen a baloldal értéke akkor volna n, ha azoknak a csúcsoknak a számát is hozzáadnók, amelyeknek nincs szomszédjuk, azaz nem indul ki belőlük kiválasztott átló.
 
 
1. ábra
 

Ha valamely csúcs fokszáma i>2, akkor a belőle kiinduló kiválasztott átlók közül két ,,szélső'' közrefog egyet vagy többet. Az ilyen közrefogott átló másik végpontjában nem csatlakozhat hozzá kiválasztott átló, mert annak nem lehetne közös pontja a két ,,szélső'' mindegyikével. Eszerint i>2 esetén minden i-edfokú csúcs legalább i-2 elsőfokú csúccsal szomszédos. Minden elsőfokú csúcs természetesen csak legfeljebb egy magasabb fokú csúccsal lehet szomszédos. Ebből az elsőfokú csúcsok a1 számára
a1≥a3+2a4+3a5+...
következik, hiszen a harmadfokú csúcsok legalább egy-egy elsőfokúval szomszédosak, a negyedfokúak legalább kettővel-kettővel, stb.
A d darab kiválasztott átlónak összesen 2d vége van. Ezek a végek a csúcsoknál helyezkednek el, minden i-edfokú csúcsba i vég fut. Ezek szerint
2d=a1+2a2+3a3+4a4+...
Ebből az egyenletből az előzők felhasználásával
2d=(a1+2a2+2a3+2a4+...)+(a3+2a4+...)≤≤(a1+2a2+2a3+2a4+...)+a1==2(a1+a2+a3+a4+...)≤2n
következik. Bebizonyítottuk tehát, hogy valóban d≤n.
 

Megjegyzések. 1. Megoldásunk az átlókról csak azt használta ki, hogy azok a csúcsokat összekötő egyenes szakaszok. Változatlanul helyes marad tehát a megoldás, ha a sokszög oldalait is az átlói közé soroljuk, ha tehát azt bizonyítjuk, hogy egy konvex n-szög csúcsait összekötő szakaszok közül nem lehet n-nél többet úgy kiválasztani, hogy bármely kettőnek legyen közös pontja.
2. Csak ott gondoltunk arra, hogy egy konvex sokszög csúcsairól van szó, ahol a ,,közrefogott'' átlókról mondhattuk, hogy elsőfokú csúcsokba vezetnek. Itt sincs azonban erre szükség. Ha egy pontból más-más irányba három szakasz indul, akkor sohasem csatlakozhat mindegyikhez annak végpontjában olyan szakasz, amelynek a pontból kiinduló másik két szakasz mindegyikével van közös pontja. Ha ugyanis a három szakasz egy a ponton áthaladó egyenes által határolt félsíkban van, akkor nem mondtunk újat; ha viszont nem ez a helyzet, akkor a három szakasz egyikéhez sem csatlakozhat annak végpontjában olyan szakasz, amelynek van közös pontja a másik kettő mindegyikével. Ezek szerint azt is bebizonyítottuk, hogy ha a sík n pontja közül egy egyenesen sincs kettőnél több, akkor e pontokat összekötő szakaszok közül nem lehet n-nél többet úgy kiválasztani, hogy bármely kettőnek legyen közös pontja.
Szükség volt itt arra a megszorításra, hogy kettőnél több pont nincs egy egyenesen. Nemcsak azért, hogy bizonyításunk, amely más-más irányba induló szakaszokról szólt, alkalmazható legyen, hanem azért is, mert pl. egy egyenesen egymást követően felvett A, B, C, D pontok AB, AC, AD, BC, BD összekötő szakaszai már ellentmondanának a megszorítás nélkül kimondott állításnak.
3. Megemlítjük végül, hogy a most említett általánosítások ugyanúgy kiolvashatók a következő megoldásból is.
 

II. megoldás. Bebizonyítjuk, hogy ‐ miként megjegyzésünkben már említettük ‐ ha nemcsak az átlókból válogathatunk, hanem az oldalakból is, akkor sem választható ki n-nél több, páronként közös ponttal rendelkező szakasz.
Ha az n-szög csúcsai között van elsőfokú, tehát olyan, amelyből csak egy kiválasztott szakasz indul ki, akkor hagyjunk el ábránkból egy ilyen szakaszt. Eredetileg d szakasz szerepelt, és együttesen m≤n végpontjuk volt. Az elhagyás után csak d1=d-1 szakasz maradt, és végpontjaik száma is legalább 1-gyel kisebb: m1≤n-1.
Ha lehetséges, hagyjunk el ismét ugyanúgy egy szakaszt. Ezáltal d2=d-2 szakaszhoz jutunk, amelyek végpontszáma m2≤n-2. Folytassuk ezt, amíg csak lehetséges. Végül dk=d-k szakaszhoz jutunk, amelyeknek együttesen mk≤n-k végpontjuk van.
Az így kapott ábrában már nincs elsőfokú szögpont, de nincs 2-nél nagyobb fokszámú sem, mert ha egy csúcsból három szakasz is kiindul, akkor a ,,közrefogott'' szakaszok végpontja csak elsőfokú lehet, amint ezt az előző megoldásban is felhasználtuk. A végábrában ezek szerint minden végpont másodfokú. A szereplő dk szakasz 2dk vége tehát párosával esik egybe, azaz mk=dk pontba fut. Az mk=dk eredmény akkor is helyes, ha az elhagyogatások befejezése után egyetlen szakasz sem marad meg, mert akkor dk=0 és mk=0.
A dk=mk eredményből az előzők szerint d-k≤n-k, azaz d≤n következik, ami a feladat állítása volt.
 

III. megoldás. Közömbös, hogy melyik konvex n-szög átlói közül akarunk megfelelő módon lehető legtöbbet kiválasztani, hiszen két átló közös pontjának létezése csak azon múlik, hogy az átlók végpontjai a sokszög határán elválasztják-e egymást, illetőleg vannak e közöttük egybeesők. Elég ezért, ha a feladat állítását a szabályos n-szögre bizonyítjuk be.
A szabályos n-szög átlóit csoportokba soroljuk, egy csoportba sorolva az egymással párhuzamosakat. Ha belátjuk, hogy nincs n-nél több csoport, bebizonyítottuk a feladat állítását, hiszen akkor n-nél több átló kiválasztásakor arra kényszerülünk, hogy egy csoportból több átlót válasszunk ki, s az ilyen párhuzamos átlóknak nincs közös pontjuk.
Az említett csoportok száma valóban nem lehet n-nél nagyobb. Ha ugyanis a sokszög középpontjából merőlegest állítunk egy átlóra, ez a merőleges egyenes a sokszögből csak csúcsban vagy egy oldal felezőpontjában léphet ki, ti. aszerint, hogy a sokszög kerületének az átló végpontjait összekötő, a merőleges által felezett része páros vagy páratlan sok oldalból áll-e (2. ábra). Minthogy n csúcs és n oldalfelezőpont van, minthogy továbbá minden merőleges e 2n pont közül más-más kettőt metsz ki, csak n ilyen merőleges lehet. Mivel az egy csoportba sorolt átlók ugyanarra az egyenesre merőlegesek, a csoportok száma valóban nem lehet n-nél nagyobb.
 
 
2. ábra
 

 
Megjegyzések. 1. Beláttuk, hogy a feladat előírása szerint nem választható ki n-nél több átló. Kérdés, n átló kiválasztható-e.
Nyilván nem választható ki, ha n értéke 3 vagy 4, mert a háromszögnek nincs átlója, a négyszögnek pedig csak két átlója van. Ha viszont n≥5, akkor mindig kiválasztható n átló az előírt módon, amint ezt a 3. ábra könnyen általánosítható példája bemutatja. Igaz marad ez természetesen akkor is, ha az oldalak kiválasztását is megengedjük. Ebben az esetben azonban nincs már szükség a háromszög és a négyszög kirekesztésére.
 
 
3. ábra
 

Nem választható ki viszont minden esetben n páronként közös ponttal rendelkező összekötő szakasz, ha nem egy konvex sokszög csúcsairól, hanem a sík n pontjáról van szó. Ha az egyik pontot az összes többivel összekötjük, az előírást kielégítő n-1 szakaszt kapunk. Többet nem kaphatunk pl. akkor, ha az ABCΔ csúcsairól és a háromszögben haladó BC körív n-3>0 további pontjáról van szó (4. ábra). Ezt a következőképpen láthatjuk be:
 
 
4. ábra
 

A-ból csak n-1 szakasz indul ki. A BC ív n-1 pontját összekötő szakaszok közül is csak n-1 választható ki az előírásnak megfelelően, hiszen ezek egy konvex (n-1)-szög csúcsai. Ha A-ból induló szakaszt is és a BC ív pontjait összekötő szakaszt is kiválasztunk, akkor ezek közös pontja csak az A-ból induló szakasz másik végpontja lehet. Ha tehát a kiválasztott szakaszok között csak egyetlen A-ból induló van, akkor ennek másik végpontja szükségképpen minden más kiválasztott szakasznak is végpontja, s ezért így is csak n-1 szakaszhoz juthatunk. Ha viszont két A-ból induló szakaszt és a BC ív egy húrját is kiválasztjuk, akkor ezek szükségképpen háromszöget alkotnak, és további szakasz már nem választható hozzájuk az előírás megsértése nélkül.
Megemlítjük itt még, hogy ha tetszőleges n-szög esetében csak a belső átlók közül válogathatunk, akkor még n-1 páronként közös ponttal rendelkező sem választható ki minden esetben, hanem csak 2. Az 5. ábra példája mutatja, hogy többet nem követelhetünk meg. Nem nehéz bebizonyítani, hogy ha n≥5, akkor két csatlakozó belső átló mindig található, e bizonyítást azonban az olvasóra hagyjuk.
 
 
5. ábra
 

2. Felmerül a kérdés, hogy ha a sík (hármasával nem egy egyenesen elhelyezkedő) n pontját összekötő szakaszok közül ki lehet választani n páronként közös ponttal rendelkezőt, akkor ez az n szakasz milyen ábrát alkothat. Bebizonyítjuk, hogy csak egy páratlan oldalú csillagsokszög adódhat, amelyhez még a csúcsaiból induló, az odafutó oldalak szögtartományában haladó szakaszok járulhatnak (6. ábra).
 
 
6. ábra
 

Második megoldásunk mutatja, hogy az elsőfokú pontokba futó szakaszok elhagyása után csupa másodfokú ponttal rendelkező ábrához kell jutnunk (ehhez az eredményhez I. megoldásunk alapján is eljuthatunk). Ez az ábra most nem lehet üres, mert akkor az utolsó elhagyás egyszerre két végpontot szüntetne meg, s így csak az mk<n-k egyenlőtlenség lehetne érvényes, ami kizárja d-n teljesülését. Eszerint az elhagyások után maradó ábrában zárt töröttvonal található, mert valamelyik szakaszon elindulva a pontok másodfokúsága miatt mindig folytathatjuk utunkat csatlakozó szakaszon, és így valamikor már bejárt szakaszhoz kell érnünk. Minthogy az ilyen zárt töröttvonal szakaszai vagy csatlakoznak, vagy metszik egymást, csillagsokszöghöz jutottunk. Ennek szükségképpen páratlan sok csúcsa van. Ha ugyanis AB egy szakasza, akkor a további csúcsok a szakaszok metszése miatt váltakozva az AB egyenes egyik és másik oldalán helyezkednek el, de közülük az A-val és B-vel szomszédos ugyanazon az oldalon van, hiszen az ezeket AB-vel összekötő szakaszok is metszik egymást.
Megvizsgáljuk, hogy a már megtalált csillagsokszögön kívül milyen szakaszok szerepelhetnek még az eredeti ábrában. Ha egy pont a csillagsokszög csatlakozó AB, BC oldalai által meghatározott ABC szögtartományban vagy csúcsszögének tartományában van, akkor belőle csak B-be futhat szakasz, mert különben nem volna közös pontja AB és BC mindegyikével. Ilyen szakasz is csak akkor felelhet meg, ha magában az ABC szögtartományban van, mert különben nem volna közös pontja a csillagsokszög további oldalaival, amelyek ezen a szögtartományon belül kötik össze az AB, BC szakaszokat.
Állításunk teljes bizonyításához elég már csak azt igazolnunk, hogy a sík minden pontja a csillagsokszög valamelyik szögének vagy szöge csúcsszögének tartományában helyezkedik el. Ennek igazolására az AB egyenest B körül elforgatjuk úgy, hogy az ABC szögnek és csúcsszögének tartományát végigsöpörve CB helyzetbe jusson. Ezt követően C körül forgatjuk el ugyanúgy, majd a következő csúcs körül, míg végül is eredeti helyzetébe tér vissza, tehát együttesen 180∘ egész számú többszörösével fordul el.
Nem lehetséges azonban, hogy az egyenes 180∘-nál többet forduljon el. Az ellenkező esetben ugyanis egyenesünk az első félfordulat során olyan a helyzetet is elfoglal, amelyen a csillagsokszög egyetlen csúcsa helyezkedik csak el, ti. az, amely körül éppen forgatunk. A második félfordulat során egyenesünk a-val párhuzamos b helyzetbe jut. Azonos helyzetről nem lehet szó, mert a nem tartalmaz második csúcsot. A párhuzamos a, b egyenesek mindegyike kettévágja a csillagsokszög egy-egy szögét, ezért e szögek egy-egy szára a párhuzamosok sávján kívül helyezkedik el. Így tehát az ezeket a szárakat szolgáltató sokszögoldalaknak a feltételezett esetben nem lehetne közös pontjuk.
Már csak azt kell belátnunk, hogy ha egy egyenes a síkban mozog, és 180∘-os elfordulás után eredeti helyzetébe tér vissza, akkor mozgása során a sík minden pontján áthalad. Ez valóban így van, mert ha valamely P pontnak nem volna meg ez a tulajdonsága, akkor P-ből mindig félegyenest indíthatunk, amely a mozgó egyenest merőlegesen metszi. Ez a félegyenes P körül forog, és a 180∘-os elfordulás után ellentétes irányú lesz. Nem metszheti ezért merőlegesen ugyanazt az egyenest, amelyet a mozgás kezdetekor metszett.
3. Felvetjük azt a kérdést is, hogy hányat kell kiválasztani egy konvex n-szög átlói közül, hogy bizonyosan legyen ezek között k olyan, amelyeknek páronként nincs közös pontja. Feladatunk a k=1 esettel foglalkozott. Ebben az esetben n+1 átló kiválasztása megfelel, de kevesebb nem.
Könnyű belátni, hogy a felvetett általános esetben kn+1 átló kiválasztása megfelel, sőt megfelel akkor is, ha nemcsak az átlók, hanem az oldalak közül is válogathatunk. Ez harmadik megoldásunkból szinte közvetlenül kiolvasható, mert ha kn+1 átlót vagy oldalt választunk ki az n csoportból, akkor valamelyikből legalább (k+1)-et kell kiválasztanunk.
Nehezebb megmutatni, hogy kisebb szám nem felel meg. Megmutatjuk, hogy ez valóban így van, vagyis olyan előírást adunk a konvex n-szög átlói közül nk átló meghúzására, hogy ne lehessen ezek közül k+1 páronként közös pont nélküli átlót kiválasztani.
Csak akkor van értelme ilyen előírás megadásának, ha az n-szögnek egyáltalában van k+1 páronként közös pont nélküli átlója. Ez csak akkor igaz, ha n≥2k+4. Ha ugyanis olyan átlókat tekintünk, amelyeknek nincs közös pontjuk, akkor bármelyiknek bármelyik oldalán vagy található olyan csúcs, amely nem végpontja átlóink egyikének sem, vagy pedig van ezen az oldalon további átló. Ez utóbbi esetben tovább haladhatunk, és esetleg újabb meg újabb átlóhoz jutunk, de végül is el kell jutnunk olyan csúcshoz, amely átlóinknak nem végpontja. Ilyen csúcs ezek szerint legalább kettő van, ti. egy átló mindkét oldalán legalább egy. Ha tehát k+1 átlóról van szó, akkor ezek 2(k+1) végpontján kívül még legalább két csúcsnak kell lennie.
Legyen tehát n≥2k+4, és legyenek az n-szög csúcsai sorban
A0,A1,B1,A2,B2,...,Ak,Bk,Ak+1,Ak+2,C1,C2,...,Cn-2k-3.
Rajzoljuk meg ebben a konvex n-szögben mindazokat az átlókat, amelyeknek legalább az egyik végpontja B jelű, továbbá A0Ak+2 kivételével mindazokat az átlókat, amelyek két A jelű csúcsot kötnek össze (7. ábra; a 3. ábra a k=1 esetben ugyanezt mutatja be). Könnyű ellenőrizni, hogy összesen nk átlót rajzoltunk meg.
 
 
7. ábra
 

Állítjuk, hogy ezek közül az átlók közül csak k darab páronként közös pont nélküli választható ki. Ezt k-ra vonatkozó teljes indukcióval bizonyítjuk be. Már tudjuk, hogy állításunk a k=1 esetben helyes. Legyen tehát k>1, és tegyük fel, hogy állításunk minden olyan esetben helyes, amikor k szerepét k-nál kisebb szám tölti be.
Ha valamennyi kiválasztott átlónak van B jelű csúcsa is, akkor számuk nem lehet k-nál nagyobb, hiszen csak k darab B jelű csúcs van. Elég ezért azzal az esettel foglalkoznunk, amikor olyan h átlót is kiválasztunk, amely két A jelű csúcsot köt össze. Megvizsgáljuk, hogy h két oldalán hány további átló választható ki. Vágjuk fel tehát n-szögünket két sokszögre, S1-re és S2-re. S1 csúcsai csak A és B jelűek, S2 csúcsai között pedig a C jelűek is szerepelnek. Helyezkedjék el a B jelű csúcsok közül j darab S1 határán, k-j pedig S2 határán. Nyilván j>0, viszont k-j=0 is lehetséges.
Azt állítjuk, hogy S1-ben csak j-1 olyan átló választható ki, amelyeknek egymással és h-val nincs közös pontjuk. Már beláttuk, hogy j darab páronként közös pont nélküli átló csak legalább 2j+2 oldalú sokszögben van. S1 legfeljebb éppen ennyi oldalú lehet (ha ti. A0 vagy Ak+2 is szerepel h végpontjai között), azonban olyan átlók számát vizsgáljuk, amelyeknek h-val sincs közös pontjuk. Az ilyen átlók pedig annak az S'1 sokszögnek is átlói, amelyet S1-ből kapunk, ha egy átlójával a h oldalt és egy szomszédos oldalát levágjuk (8. ábra). Minthogy S'1 legfeljebb 2j+1 oldalú, S1-ből sem lehet az előírt módon j-1 átlónál többet kiválasztani.
S2-ben csak akkor van egyáltalában átló a megrajzoltak közül, ha j<k, azaz van S2-nek B jelű csúcsa is. Feltesszük tehát, hogy j<k. Vizsgáljuk meg, hogy S2 határán a csúcsok betűjelzése olyan elrendezésű-e, mint n-szögünkben, természetesen k helyett csak k-j darab B jelű csúccsal. Ez bekövetkezik, ha h végpontjai között A0 vagy Ak+2 is szerepel. Minden más esetben ugyancsak elérhetjük ezt azáltal, hogy S2-bő1 egy átlóval a h oldalt és egy csatlakozó, B jelű pontba vezető oldalt levágunk (8. ábra). A kiválasztható átlók számát vizsgálva az így kapott S'2 sokszögre térhetünk át, hiszen csak olyan átló választható ki, amelynek h-val sincs közös pontja. Minden esetben alkalmazhatjuk tehát az indukciós feltevést, s ezért kimondhatjuk, hogy S2-ből a követelményt kielégítő módon nem lehet k-j átlónál többet kiválasztani.
 
 
8. ábra
 

Ezek szerint az általunk megrajzolt nk átló közül kiválasztható, páronként közös pont nélküli átlók száma (magára h-ra is gondolva) valóban legfeljebb 1+(j-1)+(k-j)=k.
Megoldatlan kérdés, hogy ha a most tárgyalt problémát nem egy konvex n-szögre, hanem a sík n pontjára vetjük fel, vajon szintén nk+1 adja-e a feleletet.
4. Feladatunk problémájának utolsó általánosításaként még az angol Conway sejtését említjük meg. E sejtés szerint, ha a sík n pontját összekötő vonalakat rajzolunk, amelyek közül bármely kettőnek vagy van közös végpontja, vagy pedig egyetlen pontban metszik egymást, de más közös pontjuk nincs, akkor ezeknek az összekötő vonalaknak a száma csak legfeljebb n lehet. Hangsúlyozzuk, hogy vonalak érintkezési pontja nem metszéspont, a vonalak érintkezését kizártuk.
Eldöntetlen kérdés, hogy vajon ez a sejtés helyes-e. Említést érdemel, hogy a vizsgált ábrák itt lényegesen mások, mint az összekötő szakaszokra felvetett problémánál, és nem csak a vonalak görbülése miatt. Ezt a 9. ábra is mutatja, melyben 6 pontot 6 vonal köt össze az előírásnak megfelelően, mégpedig ciklikus módon. Láttuk, hogy szakaszok esetében ez csak páratlan sok pontra lehetséges.
 
 
9. ábra
 

Olvasóink is megkísérelhetik a vonalakra vonatkozó probléma megoldását. Ha valakinek sikerül az előírásnak megfelelően úgy rajzolnia vonalakat, hogy számuk nagyobb, mint végpontjaik együttes száma, akkor megoldotta a problémát. Nehezebb a probléma lezárása, ha nemcsak nem sikerül ilyen ábrát rajzolni, hanem ilyen ábra nincs is. Ebben az esetben ennek bebizonyítására volna szükség.