Kezdőlap


Feladat:	1468. matematika gyakorlat	Korcsoport: 18-	Nehézségi fok: -
Megoldó(k):	Bakonyvári Mária , Balog A. , Biró A. , Böősi I. , Dozmati Z. , Dózsa L. , Fehér J. , Geréb Erzsébet , Hornung T. , Jani G. , Jónás B. , Kóczy Annamária , Kovács M. , Maácz Ágnes , Mikoss L. , Mohai L. , Németh Gy. , Nyirkos P. , Piszkor L. , Rózsa S. , Szabó Judit , Székely Katalin , Szelecki Gy. , Torma T. , Vass A.
Füzet:	1974/február, 69 - 70. oldal		PDF \| MathML
Témakör(ök):	Gráfok összefüggősége, Kombinatorikai leszámolási problémák, Szélsőérték-feladatok differenciálszámítás nélkül, Gyakorlat
Hivatkozás(ok):	Feladatok: 1973/április: 1468. matematika gyakorlat

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.

Jelöljük a szükséges kézfogások számát $S$ -sel, azoknak a kézfogásoknak a számát pedig, amelyekre nem kerül sor, jelöljük $N$ -nel. Az $(S + N)$ összeg az $n$ ember között elképzelhető összes kézfogás száma. Ha mindenki mindenkivel kezet fog, akkor mindenki $(n - 1)$ -szer fog kezet, az $n (n - 1)$ szorzatban azonban minden kézfogást kétszer számítanánk, tehát a kézfogások száma ennek a szorzatnak a fele:

\begin{matrix} S + N = \frac{1}{2} n (n - 1) . \end{matrix}

Emiatt

S

keresett legnagyobb szóbajöhető értékét megkapjuk, ha

\frac{1}{2} n (n - 1)

-ből levonjuk

N

legkisebb értékét:

\begin{matrix} S_{max} = \frac{1}{2} n (n - 1) - N_{min} . \end{matrix}

Elég tehát azt meghatároznunk, hogy ha a társaságban az ismerősök kezet fognak, legalább hány kézfogásra kerül sor. Azok az emberek, akiknek már két ismerősük van, kétszer fogtak kezet. Mivel

k

ilyen ember van, ez legfeljebb

2 k

kézfogás, ugyanis egy ilyen kézfogást esetleg kétszer is számoltunk ‐ ti. ha mindkét fél a kiemelt

k

személy közül való ‐, de 2-nél többször nem; ezért legalább

k

kézfogásra biztosan sor került, így

N_{min} = k

.
Valóban előfordulhat, hogy

N_{min}

értéke éppen

k

, ti. ha a "két‐ismerősű'' emberek együttesét "kettes klub''-nak nevezve, éppen az derül ki, hogy minden egyes klubtagnak mind a két ismerőse ugyancsak klubtag. Ez nyilvánvalóan csak

k ≧ 3

mellett lehetséges. Ha ekkor minden tag egyik‐egyik kezével megfogja 2 ismerősének egyik‐egyik kezét, akkor a klub egy vagy több körbe áll össze, és mindegyik körben legalább 3 tag áll. Ez a

k

számú "összefogás'' teszi ki az

N

"nem szükséges'' kézfogást,

N_{min} = k

, és ekkor

\begin{matrix} S_{max} = \frac{1}{2} n (n - 1) - k . \end{matrix}

k = 2

esetben a klubon belül vagy 1 "összefogás'' lesz vagy egy sem, így

N_{min} = 2 \cdot 2 - 1 = 3

; a

k = 1

esetben pedig ennek az egyetlen kiemelt vendégnek a 2 bemutatkozása marad el, és rendre

\begin{matrix} S_{max} = \frac{1}{2} n (n - 1) - 3, ill. S_{max} = \frac{1}{2} n (n - 1) - 2. \end{matrix}