Problem K. 654. (March 2020)

K. 654. There were 20 people at a meeting. It turned out that everyone knew exactly 13 of the other participants (acquaintance is mutual). What is the minimum possible number of acquaintances that an arbitrary pair of participants may have in common?

(6 pont)

Deadline expired on April 14, 2020.

Sorry, the solution is available only in Hungarian. Google translation

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.)

Statistics:

92 students sent a solution.
6 points:	Á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 points:	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 points:	9 students.
3 points:	17 students.
2 points:	14 students.
1 point:	7 students.
0 point:	1 student.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, March 2020