Feladat: 1957. évi Kürschák matematikaverseny 2. feladata Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1958/február, 40 - 45. oldal  PDF  |  MathML 
Témakör(ök): Természetes számok, Számtani sorozat, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1958/január: 1957. é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. Jelöljük 1, 2, 3, 4, 5, 6 számokkal a szereplő színeket és számpárokkal az ezekkel a színekkel gyártható kelméket. Induljunk ki egy gyártott kelméből, pl. az 56 kelméből. Ha az 12 és 34, valamint az 13 és 24 kelmepárok valamelyike két gyártott kelméből áll, akkor már eljutottunk három kívánt tulajdonságú kelméhez. Ha ez nincs így, akkor mind a két kelmepárban van nem gyártott kelme, pl. az 12 és 13 kelméket nem gyártják. Nem jelent megszorítást, hogy csak ezt az esetet vizsgáljuk, mert átszámozással mindig elérhetjük minden még el nem intézett helyzetnél, hogy ez az eset álljon elő.
Mivel minden szín legalább háromféle párosításban szerepel a gyártott kelmék között, minden szín csak legfeljebb kétféleképpen párosítható más színnel úgy, hogy nem gyártott kelme színpárjához jussunk. Ezért tudjuk, hogy 14 gyártott kelme, hiszen az 12 és 13 kelméket nem gyártják. Feltehetjük, hogy 23 nem gyártott kelme, mert különben 14, 23, 56 célunknak megfelelő kelmekiválasztás volna.
Ha viszont 12 és 23 nem gyártott kelmék, akkor az előbb mondottak szerint következik, hogy 25-nek gyártott kelmének kell lennie. Abból, hogy 13 és 23 nem gyártott kelmék, ugyanúgy következik, hogy a 36 kelmét gyártják. Ilyen módon a feladat kívánalmának megfelelő 14, 25, 36 kelmekiválasztáshoz jutottunk.

 
Megjegyzés. Megtehetjük, hogy a színeket pontokkal ábrázoljuk és azokat a pontpárokat, amelyek gyártott kelme színpárját adják, egy élnek mondott vonallal kötjük össze. A gyártott kelmék így egy ábrát, gráfot szolgáltatnak. Ennek a gráfnak hat szögpontja van, két-két szögpontját legfeljebb egy él köti össze, és a feladat kikötése szerint minden szögpontból legalább három él indul ki. A feladat annak bizonyítását kívánja, hogy a gráf élei közül kiválasztható három úgy, hogy végpontjaik mind különbözők legyenek.
Azt, hogy két szögpontot nem köt össze él, jelölhetjük azzal, hogy ezt a két szögpontot szaggatott vonallal kötjük össze. Ilyen megállapodás mellett készült a közölt első megoldás okoskodását szemléltető 4. ábra.
 
 

Ebben csak azokat az éleket és élhiányokat tüntettük föl, amelyek a megoldásban szóhoz jutottak.
 

II. megoldás. Ismét számokkal jelöljük a színeket és számpárokkal a kelméket. Feltehetjük, hogy az 12 kelmét gyártják. Mivel a 3 szín legalább háromféle párosításban szerepel a gyártott kelmék között, szerepelnie kell az 1, 2 színektől különböző színnel párosítva. Feltehetjük ezért, hogy 34 is gyártott kelme, s hogy az 56 kelmét nem gyártják, mert különben máris eljutottunk volna egy, a követelményt kielégítő kelmekiválasztáshoz. (Okoskodásunkat a 4. ábra módszerévél az 5. ábra szemlélteti.)
 
 
5. ábra
 

Mivel az 56 kelmét nem gyártják, s az 5 szín legalább három színnel párosítva gyártásra kerül, az 15, 25, 35, 45 kelmék közül legalább hármat gyártanak, azaz legfeljebb egyet nem gyártanak. Feltehetjük tehát, hogy a 35 és 45 kelmék mindegyikét gyártják, mert különben átszámozással érhetnők el ezt a helyzetet.
Miként az 5 szín esetében tettük, a 6 színről is beláthatjuk, hogy az 16, 26, 36, 46 kelmék közül legfeljebb egyet nem gyártanak. Gyártják ezért a 36, 46 kelméknek legalább az egyikét. Ha pl. 46 gyártott kelmét jelöl, akkor az 12, 35, 46 kelmekiválasztás kielégíti a feladat követelményét.
 
Megjegyzések. 1. Helyes a feladat állításának következő általánosítása: Egy gyár legalább hat különböző színű fonalból kétszínű kelméket gyárt. Minden szín legalább háromféle párosításban szerepel. Kiválasztható akkor háromféle kelme úgy, hogy ezeken hat különböző szín szerepeljen. Ennek az állításnak a bizonyítását megkapjuk, ha a közölt második megoldásban ,,az 56 kelmét nem gyártják'' szavakat az ,,és az 5, 6 színeket magasabb sorszámú színnel sem párosítják'' szavakkal toldjuk meg.
2. A feladat állításának másirányú általánosítása a következő: Egy gyár 2n különböző fonalból kétszínű kelméket gyárt. Minden szín legalább n-féle párosításban szerepel. Kiválasztható akkor n-féle kelme úgy, hogy mindegyik szín előforduljon valamelyiken. Itt n tetszőleges természetes számot jelöl. A második megoldás gondolatmenetével ezt az általánosítást is bizonyíthatjuk.
Válasszuk ki a lehető legtöbb kelmét úgy, hogy a kiválasztott kelméken csupa különböző szín szerepeljen. Tegyük fel, hogy k darab kelmét választhatunk így ki, s hogy k<n. Ha ebből ellentmondásra tudunk következtetni, akkor bebizonyítottuk, hogy k=n, azaz állításunk helyes.
A k darab kiválasztott kelme színeit 1, 2,...,2k számokkal jelöljük. Mivel k<n, vannak 2k-nál nagyobb sorszámú színek is. Bizonyos, hogy a 2n-1 és 2n színek az utóbb említett színek közül valók.
Bármely két 2k-nál nagyobb sorszámú színről megállapíthatjuk, hogy ilyen színösszeállítású kelme nem készül, hiszen különben a k darab kelme kiválasztását ennek a kelmének kiválasztásával folytathattuk volna. Igaz ezért, hogy a 2n-1 és 2n színek csak az 1, 2,...,2k színek között előfordulókkal lehetnek párosítva, s így közülük legalább n-féle színnel valóban párosítva is vannak.
Az 1, 2,...,2k színeket a k darab kiválasztott kelme párokba sorolja.Tekintsük e 2k-féle szín közül azt a legalább n-et, amelyeknek párjai a 2n-1 színnel párosítva gyártásra kerültek. Ha ezt a legalább n-féle színt az 1,2,...,2k színek közül elhagyjuk, akkor legfeljebb 2k-n, tehát n-nél kevesebb szín marad. Ebből az következik, hogy a tekintett legalább n-féle szín között kell lennie a 2n színnel párosítottnak, hiszen a 2n szín is legalább n színnel van párosítva az első 2k szín közül.
Beláttuk így, hogy a kiválasztott k darab kelme között van olyan, amelyiknek egyik színe a 2n-1 színnel, másik színe a 2n színnel is párosítva van. Hagyjuk el ezt a kelmét a kiválasztott k darab kelme közül, s a maradó k-1 darab kelméhez csatoljuk hozzá azt a két kelmét, amelyeken az elhagyott kelme színei, valamint a 2n-1, 2n színek szerepelnek. Ilyen módon k+1 csupa különböző színt tartalmazó kelméhez jutottunk. Ez ellentmond annak, hogy k értékét a lehető legnagyobbnak választottuk, s ez az ellentmondás állításunk helyességét bizonyítja.
3. A most bizonyított általánosítást tovább általánosíthatjuk ugyanúgy, ahogyan a feladat állítását először általánosítottuk. Így a következő általánosításhoz jutunk: Egy gyár legalább 2n különböző fonalból kétszínű kelméket gyárt. Minden szín legalább n-féle párosításban szerepel. Kiválasztható akkor n-féle kelme úgy, hogy ezeken 2n különböző szín szerepeljen. Ez az általánosítás magában foglalja az előző kettőnek mindegyikét. Bizonyítása új okoskodást nem kíván, mert a második általánosítás bizonyítása szószerint alkalmazható ennek bizonyítására is.
4. Felmerülhet a kérdés, nem lehet-e olyan irányban tovább általánosítani eddigi eredményeinket, hogy minden szín esetében n-nél kevesebb párosításban való gyártást követelünk meg. Vonatkozik ez a kérdés az n=3 esetre is.
Akkor sem jutunk helyes kijelentéshez, ha n-et minimálisan, ti. (n-1)-re csökkentjük. Ezt a következő példával bizonyítjuk: Legyen 2n a színek száma, és osszuk ezeket egy n-1 színből és egy n+1 színből álló csoportra. Gyártsuk mindazokat a kelméket, amelyeken egy első csoportba tartozó és egy második csoportba tartozó szín szerepel.
Most minden szín legalább n-1 párosításban szerepel, viszont n kelme a színek mindegyikét nem tartalmazhatja, hiszen a második csoportot alkotó n+1 szín közül csak legfeljebb n szín szerepelhet a kiválasztott n-féle kelmén.
 
III. megoldás. Képzeljük úgy, hogy mindenféle színpárosítással gyártanak kelmét, de nem mindegyiket hozzák forgalomba. Feladatunk ekkor a forgalomba hozott kelmékről szól. Mi most a raktáron maradó kelméket fogjuk vizsgálni.
Ha találunk a forgalomba hozott kelmék között olyat, amelyiknek a forgalomból való kivonása után a feladat kikötése továbbra is teljesül (hogy ti. minden szín legalább háromféle párosításban szerepeljen), akkor ezt a kelmét vonjuk ki a forgalomból. Folytassuk a raktárnak ezt a szaporítását mindaddig, amíg el nem mondhatjuk, hogy bármelyik további kelmének a forgalomból való kivonása után már lenne olyan szín, amelyik csak kétféle párosításban szerepelne a forgalomban maradó kelmék között. Elég, ha a feladat állítását az ilyen helyzetekre bizonyítjuk, mert az ilyen helyzetben lehetséges kelmekiválasztás a forgalomból kivont kelmék újbóli piacradobása után is lehetséges marad.
A raktár kelméin belül minden szín csak legfeljebb kétféle párosításban szerepelhet, hiszen legalább háromféle párosítása forgalomban van. Előző megállapításunk értelmében azt is kimondhatjuk, hogy a most mondott tulajdonság már nem maradna meg, ha a raktárt bármely további kelmével szaporítanók. Vizsgáljuk meg, hogy ilyen kikötések mellett a raktár milyen kelméket tartalmazhat.
A vizsgálatot megkönnyítjük azzal, hogy a színeket pontokkal ábrázoljuk, és szaggatott vonallal kötjük össze azokat a pontpárokat, amelyek egy a raktáron található kelme színeit adják. Ilyen módon egy gráf szögpontjaihoz és éleihez jutottunk. A gráf egy szögpontját annyiadrendűnek mondjuk, ahány él ebből a szögpontból kiindul. Kikötéseink szerint a gráf minden szögpontja legfeljebb másodrendű, és ez nem maradna igaz, ha a gráfhoz akármilyen további élt csatolnánk.
Ebben a gráfban csak akkor szerepelhet két 2-nél kisebb rendszámú szögpont, ha ezt a két szögpontot él köti össze, hiszen különben ezt az összekötő élt a gráfhoz csatolhatnók, és ezután sem keletkeznék 2-nél nagyobb rendszámú szögpont. Ebből következik, hogy csak a következő esetek lehetségesek: 1) a gráf minden szögpontja másodrendű, 2) csak egyetlen egy szögpont rendszáma kisebb 2-nél, a többi mind másodrendű, 3) két elsőrendű szögpontot él köt össze, a többi szögpont másodrendű. Ha ugyanis volna három 2-nél kisebb rendszámú szögpont, akkor ezeknek páronként éllel kellene összekötve lenniök, és így mégis csak kiindulna két-két él ebből a három szögpontból.
Minden él két szögpontba fut, ezért valamennyi él valamennyi végét összeszámlálva páros számot kell kapnunk. Ez azt jelenti, hogy a gráf valamennyi szögpontjának rendszámát összeadva páros számot kell kapnunk. Ebből következik, hogy ha csak egy szögpont rendszáma kisebb 2-nél, akkor ebből a szögpontból nem indul ki egyetlen él sem. Így azt is beláttuk, hogy ha a raktárt ábrázoló gráfnak egy éle másodrendű szögpontból indul ki, akkor ennek az élnek a másik végpontja is másodrendű szögpont.
A másodrendű szögpontokat összekötő élekről megállapíthatjuk most már, hogy ezek szögpontokban egymáshoz csatlakozó élekből álló körutakat, ,,sokszögeket" alkotnak, hiszen bármelyikből bármilyen irányban elindulhatunk, s a végpontok másodrendűsége miatt az utat mindaddig folytathatjuk, amíg már bejárt élre nem lépünk. Ilyenkor csak a kezdőél kezdőpontjához juthattunk, mert a bejárt élek többi végpontjaiba csak már bejárt élek futnak. Már láttuk, hogy gráfunknak hat, öt vagy négy másodrendű szögpontja van. Az ezekből kiinduló élek az első esetben vagy hatszöget, vagy két háromszöget, a második és harmadik esetben pedig csak ötszöget, ill. négyszöget alkothatnak, hiszen minden sokszögnek legalább három oldala van.
Megállapításainkat összefoglalva kimondhatjuk, hogy a forgalomba nem hozott kelmék raktárát ábrázoló gráf csak a következők valamelyike lehet: 1a) hatszög, 1b) két közös szögpont nélküli háromszög, 2) ötszög és egy további szögpont, amelyből nem indul ki él, 3) négyszög és két további, éllel összekötött szögpont. Ezeket az eseteket a 6. ábra mutatja be.
 
 
6. ábra
 

Könnyű most már mind a négy esetben három további élt úgy berajzolni, hogy ennek a három élnek mind a hat szögpontja más-más szögpont legyen. A 7. ábrán két ilyen élhármast láthatunk, amelyeknek mindegyike megfelel a 6. ábrának mind a négy gráfjánál. Ez azt jelenti, hogy a forgalomba hozott kelmék közül mindig kétféleképpen is kiválaszthatunk hármat a feladat követelményének megfelelő módon.
 

Megjegyzések. 1. Megoldásunkból a feladat állításának újabb általánosítását olvashatjuk ki. Hogy ezt könnyebben megtehessük, előbb átfogalmazzuk az eredeti feladatot. Nem szorul magyarázatra, hogy feladatunk állítása a következő kijelentéssel egyenértékű: Egy társaságnak hat tagja van. A hat személy mindegyikének legalább három ismerőse van a társaság tagjai között. Le lehet akkor ültetni a társaság tagjait három asztalhoz úgy, hogy mindegyik asztalnál ketten, éspedig ismerősök üljenek.
Ha a 7. ábra két rajzát egymásra fektetjük, akkor a 8. ábra hatszögéhez jutunk. Mivel beláttuk, hogy található ilyen hatszög, bebizonyítottuk a feladat állításának következő általánosítását: Egy társaságnak hat tagja van. A hat személy mindegyikének legalább három ismerőse van a társaság tagjai között. Le lehet akkor ültetni a társaság tagjait egy kerek asztalhoz úgy, hogy mindenki mindkét oldalról ismerős mellett üljön.
 
 
7. ábra
 
 
 
8. ábra
 

Eredményünket a gráfok körén belül maradva is megszövegezhetjük. Ha egy gráf éleiből olyan körutat lehet alakítani, amelyik szögpontokban egymáshoz csatlakozó élekből áll, s amelyik minden szögponton áthalad, és csak egyszer halad át, akkor ezt a gráf Hamilton-féle körútjának nevezzük, magát a gráfot pedig Hamilton-félének mondjuk. Eredményünk ezek után így szövegezhető: Ha egy grófnak hat szögpontja van, és ezek mindegyike legalább harmadrendű, akkor ez a gráf Hamilton-féle. Természetesen csak olyan gráfokra gondolunk, amelyekben két szögpontot nem köt össze több él.
2. Eredményünket tovább általánosíthatjuk. Helyesek maradnak kijelentéseink, ha hat és három helyett 2n és n szerepel, és itt n tetszőleges, de 1-nél nagyobb természetes számot jelöl. Ha tehát gráfokról szólunk, akkor a következőt állítjuk: Ha egy gráfnak 2n szögpontja van és n>1, ha továbbá minden szögpont legalább n-edrendű, akkor a gráf Hamilton-féle.
Ennél többet fogunk bizonyítani. Bizonyítjuk, hogy ha egy gráfnak legfeljebb 2n szögpontja van és n>1, ha továbbá minden szögpont legalább n-edrendű, akkor a gráf Hamilton-féle. Könnyű belátni, hogy ez a kijelentés csak a 2n-1 szögpontú gráfokra mond ki olyat, ami nem következik nyomban az előző kijelentésből. A kimondott tételt Dirac Gábor bizonyította 1951-ben. Mi itt csekély módosítással az ő bizonyítását ismertetjük.
Először azt igazoljuk, hogy ha egy gráf kielégíti a tétel követelményeit, akkor alakítható a gráf éleiből olyan körút, amelyik n-nél több élt tartalmaz. Ha körutat mondunk, eleve feltesszük, hogy azt szögpontokban csatlakozó élek alkotják, s hogy a körút egy szögponton sem halad át többször. Állításunk bizonyítása végett induljunk el valamelyik élen egy szögpontból, és az él végpontjában lépjünk rá egy másik élre. Ezt megtehetjük, mert a szögpontok legalább másodrendűek. Folytassuk utunkat egymáshoz szögpontokban csatlakozó éleken át haladva mindaddig, amíg ezt megtehetjük anélkül, hogy már érintett szögpontba jutnánk. Utunk P végpontjára igaz akkor az, hogy az innen tovább vezető élek mindegyikének végpontját érintettük már. E végpontok között van egy, amelyet legkorábban érintettünk. Ha az ebbe vezető élen folytatjuk utunkat, akkor körutat tettünk meg. Ez a körút n-nél több élből áll, mert tartalmazza a P szögpontot és az ebből induló legalább n él végpontjának mindegyikét.
Tételünket indirekt úton bizonyítjuk. Feltesszük, hogy a G gráf kielégíti tételünk követelményeit, de nincs Hamilton-féle körútja. Ebből a feltevésből ellentmondásra fogunk következtetni.
Válasszunk ki egy G éleiből alakított és lehető legtöbb élt tartalmazó K körutat. E körút éleinek számát k-val jelöljük. Már bizonyítottuk, hogy k>n. Van G-nek olyan szögpontja, amelyet K nem tartalmaz, hiszen feltevésünk szerint K nem lehet Hamilton-féle körút. Az ilyen szögpontok száma n-nél kisebb, mert G-nek legfeljebb 2n, K-nak pedig k>n miatt n-nél több szögpontja van. Ebből következik, hogy az ilyen szögpontokból ki kell indulniok a K körúton végződő éleknek, hiszen G minden szögpontja legalább n-edrendű. Van eszerint a K körúton olyan A szögpont, amelyikből kiindul nem a K körúton végződő él is.
Induljunk el az A szögpontból egy ilyen élen, és szögpontokban csatlakozó éleken át tovább haladva menjünk el mindaddig, amíg ezt megtehetjük anélkül, hogy a K körútra lépnénk, vagy utunk során már érintett szögpontba jutnánk. Utunk végpontját B-vel, az AB út éleinek számát l-lel jelöljük. Ez az A-ból kiinduló út l darab, a K körúthoz nem tartozó szögponthoz vezetett el. Ebből k+l2n következik, hiszen G-nek legfeljebb 2n szögpontja van. A k>n egyenlőtlenség figyelembevételével ilyen módon l<n helyességét is beláttuk.
Vizsgáljuk most, hogy B-ből hová vezetnek élek. Csak a K körút és az AB út szögpontjaihoz vezethetnek, mert különben az AB utat tovább folytathattuk volna. Az AB út szögpontjaiba csak legfeljebb l él indulhat, ezért K-nak A-tól különböző szögpontjaiba B-ből legalább n-l él indul, hiszen B legalább n-edrendű.
Ha a BC él C végpontja K-nak A-tól különböző szögpontja, akkor a K körúton nem vezethet el A-ból C-be (l+1)-nél kevesebb él. Ez abból következik, hogy az ellenkező esetben a K körutat az ABC kerülővel bővíthetnők, és így egy k-nál több élű körúthoz jutnánk, ami ellentmond K megválasztásának.
Beláttuk ilyen módon, hogy a B szögpontból legalább n-l él indul annak a D1D2 ívnek a szögpontjaihoz, amelyet úgy kapunk meg K-ból, hogy az A szögpontból kiindulva mindkét irányban l+1 csatlakozó élt elhagyunk (lásd 9. ábra).
 
 
9. ábra
 

Minthogy n-l pozitív, valóban kell, hogy az elhagyás után még maradjon egy D1D2 ív, de az is lehetséges, hogy ez az ív már csak az egyetlen D1=D2 szögpontból áll. A D1D2 ív éleinek száma az ív származtatása folytán k-2(l+1).
A D1D2 ív két szomszédos szögpontjába nem érkezhetnek élek B-ből, mert akkor a K körutat a B szögponton át vezető kerülővel k+1 élű körúttá bővíthetnők, pedig k-nál többélű körút nincs. A B szögpontból a D1D2 ívhez induló, legalább n-l él végpontjai között az ívnek legalább n-l-1 szakasza helyezkedik el, és beláttuk, hogy ezeknek a szakaszoknak mindegyike legalább két élből áll. Igazoltuk így, hogy a D1D2 ív éleinek száma legalább 2(n-l-1).
A D1D2 ív élszámára vonatkozó eredményeinket egybevetve
k-2(l+1)2(n-l-1),
azaz k2n adódik. K azonban csak akkor tartalmazhatja G-nek legalább 2n szögpontját, ha G-nek 2n szögpontja van, hiszen több szögpontja nem lehet, s ha a K körút G valamennyi szögpontját tartalmazza. Ez azt jelenti, hogy K Hamilton-féle körút, pedig feltettük, hogy G-nek nincs Hamilton-féle körútja. Ez az ellentmondás tételünk helyességét bizonyítja.
Megemlítjük még, hogy a most bizonyított tételt így is szövegezhetjük: Ha egy gráfnak legalább három szögpontja van, és egy szögpont rendszáma sem kisebb a szögpontszám felénél, akkor a gráf Hamilton-féle.