Kezdőlap


Feladat:	Pontversenyen kívüli P.231	Korcsoport: 18-	Nehézségi fok: -
Füzet:	1980/április, 168 - 169. oldal		PDF \| MathML
Témakör(ök):	Gráfelmélet, Indirekt bizonyítási mód, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1974/december: Pontversenyen kívüli P.231

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.

Tegyük fel, hogy az állítás nem igaz, és tekintsük mindazokat az ellenpéldákat, amelyekben a lehető legkevesebb versenyző szerepel. Ezek mindegyikében keressük ki azt a játékost, (vagy az egyik olyat), aki a lehető legkevesebb döntetlen mérkőzést játszotta, legyen ez $A$ . Válasszunk ki olyan ellenpéldát, amelyben $A$ döntetlenjeinek száma minimális, jelöljük ezt $k$ -val. Megmutatjuk, hogy $k$ semmiféle értéket nem vehet fel, ez igazolja az állításunkat.

I. Nem lehet

k = 0

A feltétel szerint mindenkihez található olyan, akivel összesen páratlan sok döntetlent játszott, tehát mindenki legalább egy döntetlen mérkőzést játszott.

1. ábra

II. Nem lehet

k = 1

Tegyük fel, hogy

A

csak

B

-vel játszott döntetlenül, és hagyjuk el az

A

és

B

játékosokat (1. ábra). Továbbra is ellenpéldát kapunk: a játékosok száma páratlan, és ha a többi résztvevő egy

H

részhalmazában csak

B

játszott volna páratlan sok döntetlent, akkor a

H \cup {A}

halmazhoz nem volna "jó'' résztvevő. Így ellentétbe kerültünk azzal, hogy az ellenpéldában a lehető legkevesebb versenyző szerepel.

III. Nem lehet

k \geq 2

sem.

A

döntetlenül mérkőzött

B

-vel és

C

-vel is, módosítsuk a bajnokság eredményét a következő módon (2. ábra). Ha egy résztvevő

B

-vel döntetlenül játszott, de

C

-vel nem, akkor a

C

-vel való játszmája is legyen döntetlen; ha egy résztvevő

B

-vel és

C

-vel is döntetlenül játszott (mint például

A

), akkor a

C

és közte lefolyt játszmát nyerje meg

C

. Az összes többi eredményt változatlanul hagyjuk.

2. ábra

Az olvasóra bízzuk annak ellenőrzését, hogy a módosítás után is teljesülnek a feladat feltételei. Ez viszont lehetetlen, hiszen a módosítás után

A

-nak eggyel kevesebb,

(k - 1)

döntetlenje van, mint előtte, noha feltettük, hogy a döntetlen mérkőzések minimális száma

k

.
Mivel több eset nincs, a feladat állítását bizonyítottuk.

P. T.