Problem C. 1903. (May 2026)

C. 1903. The 17 enthusiastic members of a math club would like to get together for a group math session during the summer break, so they collect everyone’s availability: from each person, they receive a time interval consisting of at least two days. (For example, from July 3 to July 6.)

After collecting the data, it turned out that among any three students there are two who have marked a common day.

Is it guaranteed that there will be a day such that every student will be available?

Is it guaranteed that there will be two days such that every student will be available on at least one of the two days?

Proposed by Zoltán Paulovics, Budapest

(5 pont)

Deadline expired on June 10, 2026.

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

Megoldás. Az első kérdésre a válasz tagadó, tehát előfordulhat, hogy olyan intervallumokat adnak meg a diákok, amelyek a feladat feltételeit kielégítik, de még sincs olyan nap, amelyen mindenki ráérne a közös matekozásra. Egy lehetséges példa: az első tizenöt diák a szünet első két napját adja meg. A 16. diák a szünet 2. és 3. napját, míg a 17. diák a 3. naptól kezdődően a teljes szünetet.

Ekkor teljesül, hogy bármely három diák között van kettő, akik megjelöltek közös napot, de nyilvánvaló, hogy nincs olyan nap, amelyen mindenki ráérne.

A második kérdésre viszont igenlő a válasz. Ezt konstruktívan bizonyítjuk, azaz adunk egy eljárást, amivel kiválasztható két olyan nap, hogy mindenki ráérjen legalább az egyiken.

Ha az \(\displaystyle i.\) diák által megadott intervallumot \(\displaystyle [a_i;b_i]\) jelöli, úgy vezessük be a legkisebb \(\displaystyle b_i\) értékre a \(\displaystyle B_1\) jelölést. Tekintsük azon intervallumokat, amelyek kezdőértéke nagyobb, mint \(\displaystyle B_1\), azaz \(\displaystyle B_1 < a_i\), és ezen intervallumok közül a legkisebb \(\displaystyle b_i\) értékre vezessük be a \(\displaystyle B_2\) jelölést.

Most megmutatjuk, hogy mindenki ráér a \(\displaystyle B_1\)-gyel vagy \(\displaystyle B_2\)-vel jelölt napok egyikén, azaz nem létezhet olyan intervallum, amely sem \(\displaystyle B_1\)-et, sem \(\displaystyle B_2\)-t nem tartalmazza.

Hiszen ha létezne egy ilyen \(\displaystyle [a_k;b_k]\) intervallum, akkor \(\displaystyle B_1\) választása miatt \(\displaystyle b_k > B_1\), illetve \(\displaystyle B_2\) választása miatt \(\displaystyle b_k > B_2\) állna fenn, azaz \(\displaystyle a_k > B_2\) lenne. De akkor a \(\displaystyle B_1\)-et, illetve \(\displaystyle B_2\)-t adó diszjunkt intervallumok mellé \(\displaystyle [a_k;b_k]\)-t választva harmadikként, találnánk három diákot, akik közül egyik páros sem jelölt meg közös napot. Ez pedig ellentmondana a feladat feltételének.

Bizonyítottuk, hogy minden intervallum tartalmazza \(\displaystyle B_1\)-et vagy \(\displaystyle B_2\)-t, következésképpen mindenki ráér ezen napok közül legalább az egyiken.

Statistics:

88 students sent a solution.
5 points:	57 students.
4 points:	15 students.
3 points:	11 students.
2 points:	3 students.
1 point:	1 student.

Problems in Mathematics of KöMaL, May 2026