Problem B. 5532. (April 2026)
B. 5532. An opera house has 8 boxes. With a box subscription, one can reserve the same box for at most 7 different evenings of the 2027/28 season, chosen by the buyer. There is one performance each evening. A box can be rented by only one person for a given evening, but multiple subscriptions may refer to the same box as long as the sets of selected evenings are disjoint. What is the minimum number of different performances in the repertoire such that the opera house can always arrange the program (knowing the subscribers' chosen dates) so that every box subscriber sees only different performances?
Proposed by András Imolay, Budapest
(6 pont)
Deadline expired on May 11, 2026.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
Problem B. 5532. is not processed yet.
Problems in Mathematics of KöMaL, April 2026