Problem B. 5278. (December 2022)
B. 5278. In Noname School of Nowhere, the graduating class consists of four groups, each specializing in a different subject: math, physics, chem and bio. On day, they are all sitting around a large round table in the school cafeteria: everyone has someone sitting directly opposite them, and everyone has neighbours sitting right next to them on either side. However a student is selected, it is observed that this student, the two neighbours, and the one sitting straight across the table all belong to different groups. How many students may there be in the graduating class if there are less than \(\displaystyle 20\) of them?
Proposed by K. A. Kozma, Győr
(3 pont)
Deadline expired on January 10, 2023.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Mivel mindenkivel szemben ül valaki, így a diákok száma páros, legyen tehát a végzősök száma \(\displaystyle 2n\), ahol \(\displaystyle n\) egész szám.
Megmutatjuk, hogy az asztal körül bármely 4 szomszédos helyen mindig 4 különböző csoportba tartozó ül, és így az asztal körül körbesétálva ez a 4 hosszú minta ciklikusan ismétlődik. A diákokat számozzuk meg az asztal mellett körbesétálva sorrendben az \(\displaystyle 1,2,\dots,2n\) számokkal, és \(\displaystyle a_i\) jelölje, hogy az \(\displaystyle i\)-edik végzős melyik csoportba tartozik. A feltételt a 2-es diákra alkalmazva kapjuk, hogy \(\displaystyle a_1,a_2,a_3,a_{n+2}\) mind különbözők, legyen mondjuk \(\displaystyle a_1=A,a_2=B,a_3=C,a_{n+2}=D\) (ahol \(\displaystyle A,B,C,D\) valamilyen sorrendben a matekos, fizikás, kémiás, bioszos csoportot jelöli). A feltételt a 3-as diákra alkalmazva kapjuk, hogy
\(\displaystyle \{A,B,C,D\}=\{a_2,a_3,a_4,a_{n+3}\}=\{B,C,a_4,a_{n+3}\},\)
vagyis
\(\displaystyle \{a_4,a_{n+3}\}=\{A,D\},\)
míg az \(\displaystyle (n+2)\)-es diákra alkalmazva
\(\displaystyle \{A,B,C,D\}=\{a_{n+1},a_{n+2},a_{n+3},a_2\}=\{a_{n+1},D,a_{n+3},B\},\)
vagyis
\(\displaystyle \{a_{n+1},a_{n+3}\}=\{A,C\}.\)
Így csak \(\displaystyle a_{n+3}=A\) lehet, és ezért \(\displaystyle a_4=D\).
Ezután ehhez hasonlóan kapjuk, hogy \(\displaystyle a_5=A\) (hiszen az előző gondolatmenet alapján \(\displaystyle a_5\)-nek \(\displaystyle a_2=B,a_3=C,a_4=D\) mindegyikétől különböznie kell), és így tovább, végig ez a 4 hosszú sorozat ismétlődik ciklikusan: \(\displaystyle A,B,C,D,A,B,C,D,\dots\).
Tehát \(\displaystyle a_i\) csoportját az \(\displaystyle i\) sorszám 4-es maradéka határozza meg. Speciálisan, mikor körbeérünk, azt kell kapnunk, hogy a \(\displaystyle (2n+1)\)-edik diák (aki ugyanaz, mint az 1-es) csoportjára \(\displaystyle a_{2n+1}=a_1\), ezért \(\displaystyle 4\mid 2n\). Viszont \(\displaystyle a_1\ne a_{n+1}\), ezért \(\displaystyle 4\nmid n\), tehát \(\displaystyle n=4k+2\) alakú (\(\displaystyle k\) egész). Ha \(\displaystyle n=4k+2\), akkor a fenti beosztás megfelelő, hiszen az \(\displaystyle i-1,i,i+1,n+i\) sorszámok (modulo \(\displaystyle 2n\) értve őket) páronként különböző 4-es maradékot adnak. Ez az \(\displaystyle i-1,i,i+1\) hármasra világos, \(\displaystyle n+i\) pedig különböző paritású, mint \(\displaystyle i-1\) és \(\displaystyle i+1\), valamint \(\displaystyle n=4k+2\) miatt \(\displaystyle i\)-től is különbözik a 4-es maradéka. (Mivel \(\displaystyle 4\mid 2n\), így a sorszámok 4-es maradéka független attól, hogy az adott modulo \(\displaystyle 2n\) maradékosztály melyik reprezentánsát választjuk ki.)
Tehát pontosan akkor teljesülhet a feltétel, ha a diákok száma \(\displaystyle 2n=8k+4\) alakú. Mivel a feltétel szerint vannak matekosok, ezért \(\displaystyle 0<k\), hiszen \(\displaystyle k=0\), és így \(\displaystyle 2n=4\) esetén csak egyetlen matekos lenne. Ugyanakkor \(\displaystyle 2n<20\) alapján \(\displaystyle k<2\). Tehát csak \(\displaystyle k=1\), \(\displaystyle n=12\) lehet.
Tehát a végzős reálosok 12-en vannak.
Statistics:
146 students sent a solution. 3 points: 98 students. 2 points: 14 students. 1 point: 20 students. 0 point: 7 students. Unfair, not evaluated: 5 solutionss.
Problems in Mathematics of KöMaL, December 2022