Problem K. 575. (January 2018)

K. 575. Six people are having a meeting. Among any three participants there are two who do not know each other. Prove that there is a set of three participants who do not know each other at all. (Acquaintance is mutual.)

(6 pont)

Deadline expired on February 12, 2018.

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

Megoldás. A résztvevők legyenek \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\), \(\displaystyle D\), \(\displaystyle E\) és \(\displaystyle F\).

\(\displaystyle A\)-n kívül még öt ember van, így \(\displaystyle A\)-nak vagy van legalább három ismerőse, vagy legalább három ,,nem ismerőse” a többiek között.

Ha \(\displaystyle A\)-nak van legalább három ismerőse a többiek között (pl. \(\displaystyle B\), \(\displaystyle C\), \(\displaystyle D\), ...), akkor ők nem ismerhetik egymást, mert ha pl. \(\displaystyle B\) és \(\displaystyle C\) ismerik egymást, akkor \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\)-re nem teljesül a feladat feltétele. Ekkor \(\displaystyle B\), \(\displaystyle C\) és \(\displaystyle D\) nem ismerik egymást, az állítást beláttuk.

Ha A legalább három főt nem ismer (pl. \(\displaystyle B\), \(\displaystyle C\), D,...), akkor ők hárman nem ismerhetik mind egymást, mert akkor lenne három olyan résztvevő, akik mind ismerik egymást. Így valamelyik kettő közülük (pl. \(\displaystyle B\) és \(\displaystyle C\)) nem ismerik egymást, és ekkor \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\)-re teljesül a feladat feltétele, az állítást beláttuk.

Statistics:

69 students sent a solution.
6 points:	Andó Lujza, Balkányi Zsófia, Balogh Domonkos, Biró 424 Ádám, Buzás Bence István, Cserkuti Sándor, Fajka Lilla, Faragó Zsombor, Fekete András Albert, Fonyi Máté Sándor, Horcsin Bálint, Izsa Regina Mária, Jeddi Gábor, Kadem Aziz, Kéri Botond, Kovács 721 Péter, Kovács 787 Zsófia, Kovács Gábor Benedek, Lengyel Katalin, Mácsai Dániel, Mályusz Etre, Molnár Lehel, Ryan Voecks, Sas 202 Mór, Schenk Anna, Sike 912 András, Sümegi Géza, Takács Dóra, Vitószki Eszter, Zempléni Lilla.
5 points:	Ágoston Viktor, Mészáros Katalin, Viharos Márta Judit.
4 points:	4 students.
3 points:	7 students.
2 points:	9 students.
1 point:	8 students.
0 point:	4 students.
Unfair, not evaluated:	4 solutionss.

Problems in Mathematics of KöMaL, January 2018