Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A K. 654. feladat (2020. március)

K. 654. Egy összejövetelen 20 ember vett részt. Menet közben az derült ki, hogy mindenki pontosan 13 embert ismer a résztvevők közül (az ismeretség kölcsönös). Hány közös ismerőse van a jelenlevők között a társaság két tetszőlegesen kiválasztott tagjának, ha a közös ismerőseik száma a lehető legkevesebb?

(6 pont)

A beküldési határidő 2020. április 14-én LEJÁRT.


1. megoldás. Legyen a két kiválasztott ember A és B. Állításunk, hogy legalább 6 közös ismerősük van. Ugyanis ha csak 5 lenne, akkor a közös ismerősökön kívül A és B még legalább 7-7 különböző embert ismerne (hiszen egymást is ismerhetik). Azonban ez már összesen 7 (csak A ismerősei) + 7 (csak B ismerősei) + 5 (közös ismerősök) + 2 (A és B) = 21 különböző ember, de csak 20-an vannak.

Meg kell mutatni még azt is, hogy létezik olyan, a feladatban szereplő társaság, ahol a 6 fellép mint valamely két ember közös ismerőseinek száma.

Az alábbi ábrán a csúcsok jelölik az embereket; a piros él a szomszédos csúcsokat köti össze, a narancssárga a másodszomszédosokat, a sárga minden 3. csúcsot, a zöld minden 4-ediket, a világoskék minden 5-ödiket, a sötétkék minden 6-odikat, végül a lila az átellenes csúcsokat. Látható, hogy bármely két embernek pontosan 6 vagy 8 közös ismerőse van.

2. megoldás. Ha A és B ismerik egymást, akkor egymáson kívül mindkettőjüknek pontosan 12 ismerősük van: \(\displaystyle n\) fő közös és \(\displaystyle (12-n)\) fő csak az egyiküknek ismerőse. Ezek szerint a társaság tagjainak száma \(\displaystyle 2+n+2(12-n)=20\), ahonnan \(\displaystyle n=6\). Ha \(\displaystyle A\) és \(\displaystyle B\) nem ismerik egymást, akkor közös ismerőseiknek számát \(\displaystyle m\)-mel jelölve hasonló gondolatmenettel kapjuk, hogy \(\displaystyle 2+m+2(13-m)=20\), azaz \(\displaystyle m=8\). Tehát bármely, a feladat feltételeinek megfelelő társaságban azoknak, akik ismerik egymást pontosan \(\displaystyle 6\), akik pedig nem ismerik egymást, azoknak pontosan \(\displaystyle 8\) közös ismerősük van. (Ahogy a fenti ábrán is.)


Statisztika:

A K. 654. feladat értékelése még nem fejeződött be.


A KöMaL 2020. márciusi matematika feladatai