Feladat:	Gy.3214	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Harangi Viktor ,  Takács Marcella ,  Varjú Péter
Füzet:	1999/március, 148 - 149. oldal		PDF  |  MathML
Témakör(ök):	Gráfelmélet, Konstruktív megoldási módszer, Gyakorlat
Hivatkozás(ok):	Feladatok: 1998/szeptember: Gy.3214

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.   I. megoldás. Minden félénknek a definíció szerint legfeljebb, a feltételezés szerint pedig legalább 3 ismerőse van. Ez azt jelenti, hogy minden félénknek pontosan 3 ismerőse van. A feltevés szerint ezek az ismerősök félénkek, tehát félénk embernek nincs nem félénk ismerőse. Mivel a feltevés szerint mindenkinek van félénk ismerőse, és az ismeretség kölcsönös, ezért mindenki félénk. Ezzel az első állítást beláttuk. Egy ilyen $n$ tagú társaságban az ismeretségek száma $\frac{3n}{2}$. Mivel ez egész szám, $n$ csak páros lehet. A társaságban legalább négyen vannak, különben nem lehetne egy embernek 3 ismerőse. Megmutatjuk, hogy minden $n\ge 4$ páros szám megfelelő. Állítsuk ehhez az embereket egy szabályos $n$ szög csúcsaiba. Mindenki ismerje a két szomszédos csúcsban lévő embert, és a vele szemközti csúcsban levőt, a többieket pedig ne. Ez a társaság nyilván megfelel a feladat feltételeinek. Ezzel beláttuk, hogy a társaság tagjainak a száma páros és legalább 4.  Takács Marcella (Székesfehérvár, József A. Gimn., 9. o.t.)   II. megoldás. a) Legyen a társaság $n$ tagú. Tagonként számlálva a félénk ismerősöket, az $n$ tag összesen legalább $3n$ félénket ismer. Mivel egy félénket legfeljebb 3 tag ismerhet, félénk tagokat legfeljebb 3-szor számoltunk meg. Így legalább $\frac{3n}{3}=n$ félénk van, ami azt jelenti, hogy mindenki félénk. b) Mindenki 3 tagot ismer, így az egyikük ismerőseivel együtt legalább 4-en vannak. Ezért $n\ge 4$. Mivel mindenki pontosan 3 tagot ismer, és az ismeretség kölcsönös, az ismeretségek száma: $\frac{3n}{2}$, tehát az $n$ értéke páros. Megadunk egy konstrukciót olyan $n$-re, amelyre $2\mid n$ és $n\ge 4$. Az ábrán látható gráfokban a csúcsok a tagokat, az élek pedig az ismeretségeket jelképezik:  Varjú Péter (Szeged, Radnóti M. Gimn., 10. o.t.)   Megjegyzés. Harangi Viktor (Fazekas M. Főv. Gyak. Gimn., 9. o.t.) a félénkség definíciójában szereplő értéket 3-ról $m$-re általánosítva is megoldotta a feladatot. Az I. megoldáshoz hasonló módon igazolva, hogy az adott feltételek esetén mindenki félénk, megmutatta, hogy ha az $m$ páros szám, akkor minden $n\ge m+1$ számra létezik a megfelelő $n$-tagú társaság, ha pedig az $m$ páratlan ‐ mint a feladatban ‐ akkor ezen kívül még az is szükséges, hogy az $n$ páros legyen.