 |
A B. 5532. feladat (2026. április) |
B. 5532. Egy operaháznak 8 páholya van. Egy páholybérlettel a 2027/28. szezon legfeljebb hét különböző, a vásárló által kiválasztott estéjére le lehet foglalni ugyanazt a páholyt. Minden este egy előadás van. Egy páholyt egy estére csak egyvalaki bérelhet ki, de szólhat több bérlet is ugyanabba a páholyba, amennyiben a kiválasztott esték halmaza diszjunkt. Legalább hányféle előadásból áll a repertoár, ha az operaház garantáltan össze fogja tudni állítani úgy a programot (a bérletesek napjainak ismeretében), hogy minden páholybérletes csupa különböző előadást láthasson?
Javasolta: Imolay András (Budapest)
(6 pont)
A beküldési határidő 2026. május 11-én LEJÁRT.
Megoldás. Legalább 49 előadásból kell állnia a repertoárnak.
Ha kevesebb, mint 49 előadásból állna a repertoár, az operaház bajba kerülhetne. Előfordulhat ugyanis, hogy 56 bérlettel úgy foglalták le az első 49 estére a páholyokat, hogy bármely két estéhez található olyan bérletes, aki mindkét estén jelen van.
Megadunk egy ilyen konstrukciót. Ehhez a 49 estét és az 56 bérlet közül 49-et is egy-egy olyan \(\displaystyle (x,y)\) számpárral reprezentálunk, ahol \(\displaystyle x,y \in \{0,1,2,\ldots,6\}\). A páholyok közül az első hetet \(\displaystyle 0\)-tól \(\displaystyle 6\)-ig megszámozzuk, míg a nyolcadik páholyt a \(\displaystyle \infty\) jellel látjuk el.
A \(\displaystyle (k,n)\) jelű bérlet szóljon a \(\displaystyle k\)-adik páholyba az \(\displaystyle \left( i, ki+n \right)\) jelű estéken, ahol az \(\displaystyle ki+n\) modulo 7 értendő (azaz ha \(\displaystyle ki+n > 6\), akkor a 7-es osztási maradékát tekintjük helyette). Ezen kívül még minden \(\displaystyle k \in \{0,1,2,3,4,5,6\}\) esetén készítünk még egy \(\displaystyle (k,\infty)\) jelű bérletet is, amely a \(\displaystyle \infty\) jelű páholyba a \(\displaystyle (k,i)\) jelű estékre szól, minden \(\displaystyle i \in \{0,1,2,3,4,5,6\}\) esetén.
Így összesen \(\displaystyle 56\) bérletünk van, melyik mindegyike 7 előadásra szól.
Két dolgot kell ellenőriznünk.
- [(1)] Egy páholyba egy estére csak egy bérlet szól.
- [(2)] Bármely két estéhez található olyan bérlet, amely mindkét estére szól.
Az (1) igazolásához tekintsük a \(\displaystyle k\) jelű páholyt és az \(\displaystyle (i,j)\) estét. Ha \(\displaystyle k \in \{0,1,\ldots,6 \}\), akkor az a \(\displaystyle (k,n)\) jelű bérlet szól ide és ekkorra, amelyre \(\displaystyle j \equiv n+ki\), azaz \(\displaystyle j-ki \equiv n\) mod \(\displaystyle 7\); ezzel \(\displaystyle n\) érétkét egyértelműen meghatároztuk. Az \(\displaystyle \infty\) jelű páholyba pedig az \(\displaystyle (i,\infty)\) jelű bérlet szól az \(\displaystyle (i,j)\) estére.
A (2) bizonyításához tekintsünk két tetszőlegesen választott estét: \(\displaystyle (i_1,j_1)\) és \(\displaystyle (i_2,j_2)\).
Ha \(\displaystyle i_1 = i_2\), akkor az \(\displaystyle (i_1,\infty)\) jelű bérlet szólt mindkét estére.
Ha \(\displaystyle i_1 \neq i_2\), akkor mivel a 7 prímszám, ezért egyértelműen létezik egy olyan \(\displaystyle k\) egész, amelyre
\(\displaystyle k(i_2 - i_1) \equiv j_2-j_1 \quad ( \mathrm{mod}~7). \)
(Hiszen ismert, hogy prím modulus esetén egyértelműen létezik multiplikatív inverze a 0-n kívül mindennek, a \(\displaystyle (j_2-j_1)\)-et az \(\displaystyle (i_2-i_1)\) multiplikatív inverzével szorozva kapjuk meg \(\displaystyle k\)-t.)
Átrendezve
\(\displaystyle j_1 - ki_1 \equiv j_2 - ki_2 \quad ( \mathrm{mod}~7), \)
és ezt a közös értéket \(\displaystyle n\)-nek választva a \(\displaystyle (k,n)\) jelű bérlet szólni fog az \(\displaystyle (i_1,j_1)\) és az \(\displaystyle (i_2,j_2)\) jelű estékre is.
Innen már csak annak a bizonyítása van hátra, hogy ha legalább 49-féle előadásból áll a repertoár, akkor biztosan össze tudják jól állítani a programot, bármilyen bérletek esetén. Ha ugyanis időrendi sorban haladnak az estéken, minden estére tudnak olyan előadást választani, amely nem ütközik egyik bérlet egyik korábbi előadásával sem. Hiszen egy estére legfeljebb 8 bérlet szólhat, melyik mindegyike legfeljebb 6 korábbi előadást érint, így ezek összesen legfeljebb \(\displaystyle 8 \cdot 6 = 48\)-féle előadást zárhatnak ki, biztosan marad tehát a repertoárban legalább egy előadás, amely minden bérletesnek újdonságot jelent.
Megjegyzés. A megoldás fő részében tulajdonképpen egy 7-edrendű affin síkot konstruáltunk meg: a pontok az estéknek, a bérletek az egyeneseknek felelnek meg. A pontokat a \(\displaystyle \mathbb{Z}_7\) véges test elemeivel koordinátázva a \(\displaystyle k\)-adik páholy bérletei tekinthetők a \(\displaystyle k\) meredekségű egyeneseknek (a \(\displaystyle \infty\) jelű páholy bérletei pedig a ,,végtelenül meredek'', avagy függőleges egyenesek). Hasonlóképpen konstruálható véges \(\displaystyle p\)-edrendű affin sík, tetszőleges \(\displaystyle p\) prímszám esetén.
Ha az estéket egy-egy gráf csúcsainak tekintjük, és azokat kötjük össze éllel, amelyek szerepelnek egy közös bérletben, akkor a megoldásunk második része azon gráfelméleti állításból következik, mely szerint \(\displaystyle \chi(G) \leq \Delta(G)\), ahol \(\displaystyle \chi(G)\) a \(\displaystyle G\) gráf kromatikus száma, míg \(\displaystyle \Delta(G)\) a legnagyobb fokszáma.
Statisztika:
A B. 5532. feladat értékelése még nem fejeződött be.
A KöMaL 2026. áprilisi matematika feladatai