A C. 1903. feladat (2026. május)

C. 1903. Egy matekszakkör 17 lelkes tagja szeretne a nyári szünetben egy közös matekozásra összejönni, ezért összegyűjtik, ki mikor ér rá: mindenkitől egy, legalább két napból álló intervallumot kapnak. (Például július 3-ától 6-áig.)

Az összegyűlt adatok alapján megállapítható, hogy bármely három diák között van kettő, akik megjelöltek közös napot.

Lesz-e biztosan olyan nap, amelyen mindenki ráér?

Lesz-e biztosan két olyan nap, hogy mindenki ráér legalább az egyiken?

Javasolta: Paulovics Zoltán (Budapest)

(5 pont)

A beküldési határidő 2026. június 10-én LEJÁRT.

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.

Statisztika:

88 dolgozat érkezett.
5 pontot kapott:	56 versenyző.
4 pontot kapott:	16 versenyző.
3 pontot kapott:	11 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2026. májusi matematika feladatai