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:

92 dolgozat érkezett.
6 pontot kapott:Ágoston Barbara, Ámon Benedek, Árok Anna, Atanaszov Hedvig, Besze Zsolt, Borján Gergő, Deák Gergely, Deme Erik, Dévényi Róbert , Gál Csaba, Héjj Anna, Jakusch Tamás, Jójárt Emese, Kádár 1115 Júlia, Kalina Rozi, Képiró Árpád Zsolt, Kothencz Laura, Kurucz Márton, Lovas Kiara, Mészáros Anna Veronika, Morvai Eliza, Ökördi Laura, Radzik Réka, Schleier Anna , Sipos Dorka, Somlai Dóra, Szabó Viktória, Szirtes Berta , Szirtes Hanna, Tóth Gréta, Vaszilievits-Sömjén Villő, Viczián Dániel, Waldhauser Miklós, Welther Károly.
5 pontot kapott:Aggod Ádám, Csáki Borbála, Kovács Dominik, Nagy Flóra, Nagy László Zsolt, Pálfi Fruzsina Karina, Vankó Lóránt Albert, Varga Domonkos Márk, Vukics Zoé.
4 pontot kapott:9 versenyző.
3 pontot kapott:17 versenyző.
2 pontot kapott:14 versenyző.
1 pontot kapott:7 versenyző.
0 pontot kapott:1 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:1 dolgozat.

A KöMaL 2020. márciusi matematika feladatai