Feladat: F.2862 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Barát János ,  Csermely Zoltán ,  Csorba Péter ,  Csörnyei Marianna ,  Dienes Péter ,  Dőtsch András ,  Duzmath Zsolt ,  Futó Gábor ,  Függ Róbert István ,  Hajba Tamás ,  Horváth Gábor ,  Katz Sándor ,  Kóczy László ,  Kuba András ,  Kucsera Henrik ,  Kuti Sándor ,  Lente Gábor ,  Marx Gábor ,  Molnár-Sáska Gábor ,  Németh Ákos ,  Párniczky Benedek ,  Radics Norbert ,  Raffai Tamás ,  Ratkó Éva ,  Risbjerg Anna ,  Szabó Szilárd ,  Szeidl Ádám ,  Szendrei Tamás ,  Valkó Benedek 
Füzet: 1992/március, 109 - 110. oldal  PDF file
Témakör(ök): Kombinatorikai leszámolási problémák, Kombinációk, Feladat
Hivatkozás(ok):Feladatok: 1991/szeptember: F.2862

Egy 30-tagú társaságban bármely két ember vagy barátja, vagy pedig ellensége egymásnak és mindenkinek pontosan hat ellensége van. Hányféleképpen lehet kiválasztani a társaságból három embert úgy, hogy közülük bármely kettő barát vagy pedig bármely kettő ellenség legyen?

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.

A 30 ember közül összesen (303)=4060-féleképpen tudunk 3-at kiválasztani. Egy kiválasztott emberhármasban vagy mindenki ellensége mindenkinek, vagy mindenki mindenkinek barátja, vagy ketten barátok és ezek ellenségei a harmadiknak, vagy pedig ketten ellenségek és ők a harmadiknak barátai.
Vegyük észre, hogy az utóbbi két esetben a három ember közül pontosan kettő olyan, hogy barátja is és ellensége is van az adott emberhármasban, az első két esetben pedig nincs ilyen ember. Ezért a feladat szempontjából kedvezőtlen emberhármasok számát kiszámíthatjuk úgy, hogy megnézzük, hányféleképpen tudunk kiválasztani egy embert és hozzá egy barátot és egy ellenséget. Ekkor minden kedvezőtlen emberhármast kétszer számolunk, hiszen a kedvezőtlen hármasokban két ilyen ember van.
Minden embernek 6 ellensége és 23 barátja van, ezért egy emberrel 623=138-féleképpen lehet egy barátot és egy ellenséget párba állítani. Mivel 30 ember van, a kedvezőtlen emberhármasok száma.

301382=2070.
A kedvező emberhármasok száma tehát 4060-2070=1990.
 
Megjegyzés. Általában, ha n ember van és ezeknek rendre e1,e2,...,en ellensége, akkor hasonlóan kapjuk, hogy azoknak az emberhármasoknak a száma, amelyekben mindenki mindenkinek barátja vagy mindenki mindenkinek ellensége,
(n3)-i=1nei(n-1-ei)2.

 

 Csörnyei Mariann (Fazekas M. Főv. Gyak. Gimn., II. o. t.)
 dolgozata alapján