Kezdőlap


Feladat:	F.2370	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Ákosfai Z. , Alberti G. , Balázs Z. , Böröczky K. , Danyi P. , Engländer J. , Erdős 228 L. , Hetyei G. , Holbok I. , Kántor Cs. , Lenkó Cs. , Magyar Á. , Megyesi G. , Mohay T. , Papp 193 G. , Sigray I. , Simák Gy. , Szabó E. , Szabó Endre , Szederkényi Edit , Törőcsik J. , Wágner P. A. , Weisz F. , Zieger B.
Füzet:	1983/március, 107 - 108. oldal		PDF \| MathML
Témakör(ök):	Gráfelmélet, Indirekt bizonyítási mód, Feladat, Logikai feladatok
Hivatkozás(ok):	Feladatok: 1982/május: F.2370

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.

Ábrázoljuk a társaság tagjait az ábécé nagy betűivel jelölt pontokkal és ismertségüket ‐ melyet kölcsönösnek feltételezünk ‐ e pontokat összekötő szakaszokkal. Tehát két pont akkor és csak akkor van összekötve, ha az általuk reprezentált személyek ismerősök. A feltételek miatt ebben a pontszakasz rendszerben biztosan van legalább egy $A B$ szakasz és van egy $C$ pont úgy, hogy $A C$ és $B C$ szakasz is létezik.
Megmutatjuk, hogy az összes többi pont össze van kötve $A$ , $B$ , $C$ valamelyikével.
Tegyük fel ugyanis, hogy $D$ nem ismeri $A$ , $B$ , $C$ egyikét sem. Ekkor létezik $E$ , aki $A$ -t és $D$ -t ismeri. A feltétel szerint $E$ nincs összekötve sem $B$ -vel, sem $C$ -vel, hiszen ekkor lenne a társaságban két olyan ember, akit nem pontosan egy másik ismer. (Pontok és szakaszok nyelvén ezt úgy fogalmazhatjuk, hogy négyszög nem jöhet létre, hiszen ennek átellenes csúcsai nem felelnek meg a feltételeknek.) Ugyanilyen okból létezik $F$ , aki $B$ -t és $D$ -t ismeri, valamint $G$ , aki $C$ -t és $D$ -t ismeri (1. ábra).

1. ábra

2. ábra

3. ábra

Az ábrán szereplő hét ember között további ismeretségek nem lehetnek, mert bármely két pontot összekötő szakaszt behúzva, négyszög keletkezne. Vannak továbbá olyan

H

I

J

K

L

M

tagjai, a társaságnak, akik rendre az

(A, E)

(B, F)

(C, G)

(E, D)

(F, D)

(G, D)

párok közös ismerősei (2. ábra). Előző megjegyzésünk alapján e hat ember bármelyike különbözik az 1. ábrán szereplő hét ember bármelyikétől. Belátjuk, hogy

H

I

J

K

L

M

-mel valóban hat egymástól különböző embert jelöltünk. Elég a

H = I

H = K

K = L

eseteket kizárni. A 3. ábráról leolvasható, hogy pont-szakasz rendszerünkben bármelyik egyenlőség fennállása esetén négyszög keletkezne.
Mivel indirekt feltevésünkből az következett, hogy a társaságnak legalább 13 tagja van, állíthatjuk, hogy mindenki ismeri

A

B

C

valamelyikét.
Megmutatjuk, hogy az összes többi pont

A

B

C

közül ugyanazzal van összekötve.

4. ábra

5. ábra

Tegyük fel ugyanis ennek ellenkezőjét, tehát hogy

D B

és

E A

szakaszok léteznek. Mivel minden pont az

A

B

C

közül pontosan eggyel van összekötve, léteznie kell egy

F

-nek, aki

E

-t és

D

-t ismeri. Ez az

F

azonban nem lehet összekötve sem

A

-val, sem

B

-vel, sem

C

-vel, mivel ekkor az

(F, B)

;

(F, A)

;

(F, C)

párokat két tagja is ismerné a társaságnak (4. ábra).
Így tehát mindenki ismeri

A

B

C

egyikét, pl.

A

-t. Az 5. ábrán látható, hogy létezik ilyen, a feltételeknek megfelelő társaság.

Szabó Endre (Budapest, Fazekas M. Gyak. Gimn., IV. o. t.)

Megjegyzés. A feladat állítása nemcsak

11

, hanem bármilyen páratlan számú tagból álló társaságra igaz. Ennek a "barátság-tétel'' néven ismert állításnak bizonyítása egyáltalán nem könnyű.