Kezdőlap


Feladat:	2019. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	2019/szeptember, 324. oldal		PDF \| MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Gráfelmélet

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.

Egy szociális hálózatnak $2019$ tagja van, közülük némely párok barátai egymásnak. Ha $A$ barátja $B$ -nek, akkor $B$ is barátja $A$ -nak. A következő típusú esemény előfordulhat többször egymás után, egy időben mindig csak egy ilyen esemény történik:

A

B

C

olyanok, hogy

A

barátja

B

-nek is és

C

-nek is, de

B

nem barátja

C

-nek, akkor barátságot változtathatnak úgy, hogy

B

és

C

most már barátai egymásnak,

A

és

B

, valamint

A

és

C

barátsága viszont megszűnik. Az összes többi barátság változatlan marad.

Kezdetben 1010 olyan tag van, amelyek mindegyikének pontosan 1009 barátja van, és 1009 olyan tag, amelyek mindegyikének pontosan 1010 barátja van. Bizonyítsuk be, hogy létezik a fenti típusú eseményeknek egy olyan sorozata, amelyek végén minden tagnak legfeljebb egy másik tag a barátja.