Kezdőlap


Feladat:	Pontversenyen kívüli P.348	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Alberti Gábor , Hetyei Gábor , Király Z.
Füzet:	1982/január, 23 - 24. oldal		PDF \| MathML
Témakör(ök):	Gráfelmélet, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1981/április: Pontversenyen kívüli P.348

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.

Ha egy körút $l$ darab várost érint, és csak autóbuszt (csak repülőt) kell hozzá igénybe vennünk, akkor azt fogjuk mondani, hogy ez egy $l$ hosszúságú autóbuszkörút (repülőkörút).
Tegyük fel, hogy $k \geq 3$ és van $2 k + 1$ hosszú autóbuszkörút. Bebizonyítjuk, hogy ekkor vagy van $2 k$ hosszú autóbuszkörút, vagy van $2 k$ hosszú repülőkörút. Legyenek a $2 k + 1$ hosszú autóbuszkörút során érintett városok (az érintés sorrendjében) $V_{1}$ , $V_{2}$ , $...$ , $V_{2 k + 1}$ , $V_{1}$ . Az egyöntetű jelölés kedvéért ciklikusan kiterjesztjük a $V_{i}$ városok indexelését: $V_{2 k + 1 + i} = V_{i}$ minden $i$ egészre.
Legyen $j$ tetszőleges egész, és helyettesítsük a $V_{1} V_{2} V_{3} ... V_{2 k + 1} V_{1}$ körút $V_{j}$
$V_{j + 1} 1 V_{j + 2}$ szakaszát a közvetlen $V_{j} V_{j + 2}$ járattal. Ha ez a járat autóbuszjárat, akkor máris kaptunk egy $2 k$ hosszú autóbusz körutat. Ha viszont $V_{j}$ és $V_{j + 2}$ között minden $j$ -re repülő jár, akkor először is csinálhatunk egy $2 k + 1$ hosszú repülőkörutat: $V_{1} V_{3} V_{5} ... V_{2 k + 1} V_{2} V_{4} ... V_{2 k} V_{1}$ . Ezt a körutat így is felírhatjuk: $V_{1} V_{3} V_{5} ... V_{2 k + 1} V_{2 k + 3} V_{2 k + 5} ... V_{4 k + 1} V_{4 k + 3} (= V_{1})$ . (Az 1. ábrán ezt a körutat a szaggatott élek jelzik.) Legyen $j$ tetszőleges egész, és helyettesítsük ebben a körútban a $V_{j} V_{j + 2} V_{j + 4}$ szakaszt a $V_{j} V_{j + 4}$ közvetlen járattal. Ha ez a járat repülőjárat, akkor így ezzel $2 k$ hosszú repülőúthoz jutottunk.

1. ábra

2. ábra

Marad tehát az az eset, ha

V_{j}

és

V_{j + 4}

között is minden

j

-re autóbusz jár. Ez esetben viszont menjünk végig a következő útvonalon.

V_{1} V_{5} V_{6} V_{2} V_{3} V_{7} ... V_{2 k + 1} V_{1}

, ahol

k = 3

esetén a

V_{7} ... V_{2 k + 1}

szakasz az egyetlen

V_{7} = V_{2 k + 1}

városból áll,

k > 3

esetén pedig

V_{7}

és

V_{2 k + 1}

között "egyesével'' haladunk. Ez az útvonal csupa autóbusz járatot használ, és ha

k \geq 3

, akkor ez egy

2 k

hosszú körút (lásd a 2. ábrát). Így tehát most is egy

2 k

hosszú autóbuszkörúthoz jutottunk. Ezzel beláttuk, hogyha van

2 k + 1

hosszú autóbuszkörút, akkor vagy van

2 k

hosszú autóbuszkörút vagy van

2 k

hosszú repülőkörút.
Az autóbusz és repülő szerepének felcserélésével ugyanez a gondolatmenet azt is adja, hogy ha van

2 k + 1

hosszú repülőkörút, akkor szintén van

2 k

hosszú autóbuszkörút vagy

2 k

hosszú repülőkörút.
Mivel pedig nincs

2 k

hosszú autóbusz- és repülőkörút, így

2 k + 1

hosszú autóbusz- és repülőkörút sincsen. Ezzel a feladat állítását beláttuk.

Megjegyzés.

k = 2

esetén a

V_{1} V_{5} V_{6} V_{2} V_{3} V_{7} ... V_{2 k + 1} V_{1}

útvonal nem körút, hiszen ebben az esetben már

V_{6} = V_{1}

. Tehát

k = 2

-re a feladat állítása nem is igaz: ha

V_{1} V_{2} V_{3} V_{4} V_{5} V_{1}

autóbuszkörút,

V_{1} V_{3} V_{5} V_{2} V_{4} V_{1}

viszont repülőkörút, akkor a 4 hosszú körutakhoz mindig szükség van autóbuszra is, repülőre is, és mégis van 5 hosszú autóbuszkörút (sőt repülőkörút is).