Problem B. 5368. (February 2024)

B. 5368. In a table tennis championship any two contestants played with each other exactly once. In each match, the winner got 1 point, and the loser got 0 points (there is no tie in table tennis). Interestingly, one contestant has won against exactly those who scored more than him in the championship and lost to exactly those who scored less than him in the championship. Find the smallest possible number of contestants participating in the championship. (It is possible that several contestants got the same score at the end of the championship. At least two contestants participated in the championship.)

Proposed by Kartal Nagy, Budapest and Bálint Hujter, Budapest

(4 pont)

Deadline expired on March 11, 2024.

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

Megoldás. Legyen a feladatban vizsgált játékos Pál. Nem lehet olyan játékos, aki ugyanannyi pontot szerzett a bajnokság során, mint Pál, hiszen akkor Pál se nem győzhette volna le, se nem kaphatott volna ki tőle a feltételek szerint.

Nevezzük kispontúnak azokat a játékosokat, akik Pálnál kevesebb pontot szereztek és nevezzük nagypontúnak azokat, akik Pálnál több pontot szereztek a bajnokság végén.

A kispontú játékosok számát jelölje \(\displaystyle k\), a nagypontú játékosok számát pedig jelölje \(\displaystyle n\). Összesen tehát \(\displaystyle k+n+1\) játékos vett részt a versenyen, tehát egy játékos legfeljebb \(\displaystyle k+n\) pontot szerezhetett.

\(\displaystyle \binom{k}{2} = k \cdot \frac{k-1}{2}\) olyan meccs volt, amelyen két kispontú játszott egymás ellen. Tehát kell legyen olyan kispontú játékos, aki legalább \(\displaystyle \frac{k-1}{2}\) meccset megnyert a kispontú ellenfelei ellen. Mivel minden kispontú legyőzte Pált, ezért kijelenthető, hogy van olyan kispontú játékos, aki legalább \(\displaystyle 1 + \frac{k-1}{2} = \frac{k+1}{2}\) pontot szerzett.

\(\displaystyle \binom{n}{2} = n \cdot \frac{n-1}{2}\) olyan meccs volt, amelyen két nagypontú játszott egymás ellen. Van tehát olyan nagypontú játékos, aki legalább \(\displaystyle \frac{n-1}{2}\) meccset elvesztett nagypontú ellenfél ellen. Mivel még Páltól is kikapott, ezért legalább \(\displaystyle \frac{n-1}{2} +1\) meccset vesztett, azaz legfeljebb \(\displaystyle (n+k)-\left( \frac{n-1}{2} +1 \right) = \frac{n}{2}+k-\frac12\) pontot szerzett.

Ha Pál \(\displaystyle p\) pontot szerzett, akkor:

\(\displaystyle \frac{k+1}{2} \leq p -1 \quad \text{ és } \quad p + 1 \leq \frac{n}{2}+k-\frac12, \)

azaz

Tehát Pálon kívül legalább 6, összesen tehát legalább 7 résztvevője kellett legyen a bajnokságnak.

7 résztvevővel megvalósíthatóak a feladat feltételei. Legyen \(\displaystyle n=k=3\), a nagypontúak és a kispontúak közötti összes meccset nyerjék meg a nagypontúak. A 3 nagypontú között pedig legyen körbeverés, csakúgy, mint a 3 kispontú között. Ekkor a nagypontúaknak \(\displaystyle k+1 = 4\) pontja, Pálnak \(\displaystyle n = 3\) pontja, a kispontúaknak pedig \(\displaystyle 1+1 = 2\) pontja van.

Statistics:

98 students sent a solution.
4 points:	58 students.
3 points:	15 students.
2 points:	10 students.
1 point:	6 students.
0 point:	3 students.
Not shown because of missing birth date or parental permission:	4 solutions.

Problems in Mathematics of KöMaL, February 2024