Problem B. 5149. (January 2021)

B. 5149. In how many different ways is it possible to fill in a \(\displaystyle 6\times 6\) table with the numbers \(\displaystyle 1,2,\dots,36\) so that however 6 fields are selected, all lying in different rows and in different columns, the sum of the numbers in 6 such fields should always be the same?

(6 pont)

Deadline expired on February 15, 2021.

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

Megoldás. Arra a feltételre, hogy ``bárhogy választunk 6 mezőt, melyek közül semelyik kettő nincs egy sorban vagy oszlopban, a kiválasztott mezőkbe írt számok összege mindig ugyanannyi'' hivatkozzunk \(\displaystyle (*)\) feltételként. A \(\displaystyle (*)\) feltételnek eleget tevő kitöltéseket hívjuk röviden megfelelőnek.

Azt fogjuk meghatározni, hányféleképpen lehet a \(\displaystyle 0,1,\dots,35\) számokkal kitölteni a mezőket úgy, hogy a \(\displaystyle (*)\) feltétel teljesüljön. Ez egyben a feladat kérdését is megválaszolja, hiszen minden értékhez 1-et adva megfelelő kitöltést kapunk az \(\displaystyle 1,2,\dots,36\) számokkal, és megfordítva, minden \(\displaystyle 1,2,\dots,36\) számokat használó megfelelő kitöltés előáll ily módon.

Tekintsünk egy megfelelő kitöltést, és rendezzük át úgy a sorokat és oszlopokat, hogy az 1. sor 1. mezőjébe kerüljön a 0, az első sorban balról jobbra, az első oszlopban pedig fentről lefelé növekvő értékek szerepeljenek. A \(\displaystyle (*)\) feltételnek megfelelő kitöltések számát megkaphatjuk úgy, hogy megszámoljuk az előbbi átrendezés szerinti megfelelő kitöltéseket, majd a választ szorozzuk \(\displaystyle (6!)^2\)-tel, hiszen ennyiféleképpen lehet permutálni a sorokat és oszlopokat.

Az első sorban szereplő értékek legyenek balról jobbra \(\displaystyle a_1=0<a_2<\dots<a_6\), az első oszlopban szereplő értékek pedig fentről lefelé haladva \(\displaystyle a_1=b_1=0<b_2<\dots<b_6\). Azt állítjuk, hogy az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik mezőjében szereplő érték \(\displaystyle a_j+b_i\). Ha \(\displaystyle i=1\) vagy \(\displaystyle j=1\), akkor ez világos, tegyük fel, hogy \(\displaystyle 1<i,j\). Az 1. sor 1. mezőjéből és az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik mezőjéből álló pár kiegészíthető 4 további mezővel úgy, hogy a kapott 6 mező különböző sorokból és oszlopokból kerüljön ki. Ugyanezzel a 4 mezővel szintén ugyanígy egészíthető ki az 1. sor \(\displaystyle j\)-edik és az \(\displaystyle i\)-edik sor első mezőjéből álló pár. Mivel \(\displaystyle (*)\) alapján a két esetben a hat-hat érték összege ugyanannyi, és mivel ugyanazzal a négy mezővel egészítettük ki a párokat, ezért az 1. sor 1. mezőjébe írt számnak (0) és az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik mezőjébe írt számnak az összege ugyanannyi, mint az 1. sor \(\displaystyle j\)-edik mezőjébe írt számnak (\(\displaystyle a_j\)) és az \(\displaystyle i\)-edik sor 1. mezőjébe írt számnak (\(\displaystyle b_i\)) az összege. Tehát az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik mezőjébe valóban \(\displaystyle a_j+b_i\) kerül.

Nem nehéz megmutatni, hogy ebben az esetben a \(\displaystyle (*)\) feltétel valóban teljesül, hiszen 6 mezőt választva különböző sorokból és különböző oszlopokból, a mezőkbe írt számok összege mindenképpen

\(\displaystyle a_1+a_2+a_3+a_4+a_5+a_6+b_1+b_2+b_3+b_4+b_5+b_6\)

lesz.

A kérdés tehát az, hány olyan

\(\displaystyle A=\{a_1,a_2,\dots,a_6\},\quad B=\{b_1,b_2,\dots,b_6\}\)

halmazpár van, melyekre

\(\displaystyle 0=a_1<a_2<\dots<a_6, \quad 0=b_1<b_2<\dots<b_6\)

és

\(\displaystyle A+B=\{a_i+b_j: 1\leq i\leq 6,1\leq j\leq 6\}=\{0,1,\dots,35\}.\)

Utóbbi feltételt röviden jelöljük úgy, hogy \(\displaystyle A\oplus B=\{0,1,\dots,35\}\): \(\displaystyle A\) és \(\displaystyle B\) direkt összege \(\displaystyle \{0,1,\dots,35\}\). Ekkor \(\displaystyle \{0,1,\dots,35\}\) minden eleme egyértelműen áll elő \(\displaystyle A\) és \(\displaystyle B\) egy-egy eleme összegeként.

Egy ilyen előállításra úgy is gondolhatunk, hogy a hat elemű \(\displaystyle A\) halmaz \(\displaystyle A+b_1=A+0=A\), \(\displaystyle A+b_2=\{a+b_2:a\in A\}\), ..., \(\displaystyle A+b_6=\{a+b_6:a\in A\}\) eltoltjai páronként diszjunktak, és lefedik \(\displaystyle \{0,1,\dots,35\}\)-öt. Megjegyezzük, hogy egy ilyen lefedés \(\displaystyle A\) ismeretében a következőképpen kapható: a legkisebb \(\displaystyle A=A+b_1\) által nem fedett elem \(\displaystyle b_2\), a legkisebb \(\displaystyle (A+b_1)\cup (A+b_2)\) által nem fedett elem \(\displaystyle b_3\), és így tovább...

Mivel az 1-et is meg kell kapnunk, ezért \(\displaystyle 1\in A\) vagy \(\displaystyle 1\in B\), azonban \(\displaystyle 1\in A\) és \(\displaystyle 1\in B\) egyszerre nem teljesülhet, mert akkor az 1-et kétféleképpen is megkapnánk. Tegyük fel mondjuk, hogy \(\displaystyle 1\in A\) (és \(\displaystyle 1\notin B)\). (Az \(\displaystyle 1\in B\) esetben is ugyanannyi megfelelő kitöltést kapunk.)

Legyen \(\displaystyle k\) a legkisebb olyan pozitív egész szám, amire \(\displaystyle k\notin A\). Ekkor tehát \(\displaystyle \{0,1,\dots,k-1\}\subseteq A\), de \(\displaystyle k\notin A\). Az eddigiek alapján \(\displaystyle 2\leq k\leq 6\), hiszen \(\displaystyle 0,1\in A\) és \(\displaystyle |A|=6\). Csak úgy lehet \(\displaystyle k\in A\oplus B\), ha \(\displaystyle k\in B\). Legyen \(\displaystyle \ell\) a legkisebb olyan pozitív egész, amire \(\displaystyle k\ell\notin B\), ekkor tehát \(\displaystyle \{0,k,2k,\dots,(\ell-1)k\}\subseteq B\). Jegyezzük meg, hogy

\(\displaystyle \{0,1,\dots,k-1\}\oplus \{0,k,2k,\dots,(\ell-1)k\}=\{0,1,2,\dots,k\ell-1\}\)

és világos, hogy \(\displaystyle 2\leq \ell \leq 6\). Mindezek alapján

\(\displaystyle A\cap \{0,1,\dots,k\ell-1\}=\{0,1,\dots,k-1\}, \quad B\cap \{0,1,\dots,k\ell-1\}=\{0,k,\dots,k(\ell-1)\},\)

különben valamelyik elem többféleképpen is előállna összegként.

A legkisebb érték, aminek előállítása egyelőre nem garantált, \(\displaystyle k\ell\). Csak úgy lehet \(\displaystyle k\ell\in A\oplus B\), ha \(\displaystyle k\ell\in A\).

Ha \(\displaystyle k\ell<36\), akkor \(\displaystyle k\ell\in A\oplus B\), ami csak úgy lehet, hogy \(\displaystyle k\ell\in A\), hiszen \(\displaystyle \ell\) definíciója alapján \(\displaystyle k\ell\notin B\), márpedig ha az \(\displaystyle A+b_1,A+b_2,\dots,A+b_{\ell}\) eltoltak nem fednék \(\displaystyle k\ell\)-et, akkor a soron következő eltolt legkisebb eleme, vagyis \(\displaystyle a_1+b_{\ell+1}=b_{\ell+1}\) lehetne csak \(\displaystyle k\ell\). (Az is világos \(\displaystyle A\cap \{0,1,\dots,k\ell-1\}=\{0,1,\dots,k-1\}\) alapján, hogy \(\displaystyle k\ell\)-et \(\displaystyle A+b_1=A,\dots,A+b_{\ell}=A+k(\ell-1)\) közül csak \(\displaystyle A+b_1\) tartalmazhatja.)

Tehát \(\displaystyle k\ell\in A\). Ekkor \(\displaystyle k\ell+k\in A+b_2\). Mivel \(\displaystyle A\) mindent eltoltjának \(\displaystyle k\) legkisebb eleme szomszédos, ezért a \(\displaystyle k\ell+1,\dots,k\ell+k-1\) számok egyikét sem fedheti valamely \(\displaystyle A+b_j\) eltolt \(\displaystyle j>\ell\) mellett. Azt is tudjuk \(\displaystyle A\cap \{0,1,\dots,k\ell-1\}=\{0,1,\dots,k-1\}\) alapján, hogy \(\displaystyle A+b_2=A+k\), ..., \(\displaystyle A+b_{\ell}=A+k(\ell-1)\) sem tartalmazhatják ezen elemek egyikét sem. Tehát mindenképpen \(\displaystyle k\ell+1,\dots,k\ell+k-1\in A\).

Most \(\displaystyle k\) lehetséges értékei alapján külön-külön vizsgáljuk az eseteket.

1. eset: \(\displaystyle k=6\)
Ekkor \(\displaystyle A=\{0,1,2,3,4,5\}\). Világos, hogy ekkor a 6 eltolt csak \(\displaystyle A,A+6,A+12,A+18,A+24,A+30\) lehet, vagyis \(\displaystyle B=\{0,6,12,18,24,30\}\).

2. eset: \(\displaystyle k=5\) vagy \(\displaystyle k=4\)
Ekkor \(\displaystyle k\ell<36\), ezért a fentiek alapján \(\displaystyle A\)-nak legalább \(\displaystyle 2k\) eleme kellene, hogy legyen (\(\displaystyle 0,1,\dots,k-1,k\ell,k\ell+1,\dots,k\ell+k-1\)), viszont \(\displaystyle |A|=6\) miatt ez nem lehetséges.

3. eset: \(\displaystyle k=3\)
Ekkor az előző esethez hasonlóan kapjuk, hogy \(\displaystyle A=\{0,1,2,3\ell,3\ell+1,3\ell+2\}\).

Ha \(\displaystyle \ell=2\), akkor \(\displaystyle A=\{0,1,2,6,7,8\}\). Ekkor \(\displaystyle b_2=3\), és az \(\displaystyle A+b_1=A,A+b_2=A+3\) eltoltak diszjunkt módon fedik \(\displaystyle \{0,1,2,3,4,5,6,7,8,9,10,11\}\)-et. A 12-nek tehát \(\displaystyle A+b_3\) legkisebb elemének, vagyis \(\displaystyle b_3\)-nak kell lennie: \(\displaystyle b_3=12\). Ezt így folytatva (a legkisebb még nem fedett elem mindig a soron következő eltolt legkisebb eleme kell legyen) kapjuk, hogy \(\displaystyle B=\{0,3,12,15,24,27\}\), ami valóban megfelelő.

Ha \(\displaystyle \ell=3\), akkor \(\displaystyle A=\{0,1,2,9,10,11\}\). Ekkor \(\displaystyle b_2=3,b_3=6\), és az első három eltolt, \(\displaystyle A,A+3,A+6\) által fedett rész \(\displaystyle \{0,1,\dots,17\}\). Így sorra kapjuk, hogy \(\displaystyle b_4=18\), majd \(\displaystyle b_5=21\), végül \(\displaystyle b_6=24\). A kapott \(\displaystyle B=\{0,3,6,18,21,24\}\) valóban megfelelő.

Ha \(\displaystyle \ell=4\), akkor \(\displaystyle A=\{0,1,2,12,13,14\}\). Ekkor \(\displaystyle b_2=3, b_3=6, b_4=9\), és az első négy eltolt, \(\displaystyle A,A+3,A+6,A+9\) által fedett rész \(\displaystyle \{0,1,2,\dots,23\}\). Így \(\displaystyle b_5=24\) kellene, hogy legyen, azonban ekkor \(\displaystyle a_6+b_5=14+24=38>35\) alapján nem kapunk megoldást.

Ehhez hasonlóan, ha \(\displaystyle \ell=5\), akkor \(\displaystyle A=\{0,1,2,15,16,17\}\). Ekkor \(\displaystyle b_2=3, b_3=6, b_4=9,b_5=12\), és az első öt eltolt, \(\displaystyle A,A+3,A+6,A+9,A+12\) által fedett rész \(\displaystyle \{0,1,2,\dots,29\}\). Így \(\displaystyle b_6=30\) kellene, hogy legyen, azonban ekkor \(\displaystyle a_6+b_6=17+30=47>35\) alapján nem kapunk megoldást.

Végül, ha \(\displaystyle \ell=6\), akkor \(\displaystyle A=\{0,1,2,18,19,20\}\). Ekkor \(\displaystyle b_2=3, b_3=6, b_4=9,b_5=12,b_6=15\), és a kapott \(\displaystyle B=\{0,3,6,9,12,15\}\) valóban megfelelő.

4. eset: \(\displaystyle k=2\)
Ekkor tudjuk, hogy \(\displaystyle A\)-nak biztosan elemei \(\displaystyle 0,1,2\ell,2\ell+1\). Azt is tudjuk, hogy az első \(\displaystyle \ell\) eltolt \(\displaystyle A+b_1=A\), \(\displaystyle A+b_2=A+2\), ..., \(\displaystyle A+b_\ell=A+2(\ell-1)\). Jegyezzük meg, hogy \(\displaystyle \{0,1,2\ell,2\ell+1\}\oplus \{0,2,\dots,2(\ell-1)\}=\{0,1,\dots,4\ell-1\}\), és így \(\displaystyle 2\ell+2,2\ell+3,\dots,4\ell-1\) egyike sem eleme \(\displaystyle A\)-nak. Tehát a második szomszédos \(\displaystyle A\)-beli elempár (\(\displaystyle 2\ell\) és \(\displaystyle 2\ell+1\)) után legalább annyi nem \(\displaystyle A\)-elem jön, mint amennyi az első szomszédos elempár (\(\displaystyle 0\) és \(\displaystyle 1\)) után volt, ezt \(\displaystyle a_3-a_2\leq a_5-a_4\) alakban is írhatjuk.

Azt fogjuk megmutatni, hogy \(\displaystyle A\) maradék két eleme csak \(\displaystyle 4\ell\) és \(\displaystyle 4\ell+1\) lehet.

Világos, hogy \(\displaystyle a_6+b_6=35\) és az is, hogy vagy \(\displaystyle a_5+b_6=34\) vagy \(\displaystyle a_6+b_5=34\). Utóbbi esetben \(\displaystyle b_5=b_6-1\) lenne, ami \(\displaystyle a_1+b_6=a_2+b_5\) teljesülését vonná maga után, ami nem lehetséges. Tehát \(\displaystyle a_5+b_6=34\), és így \(\displaystyle a_6-a_5=1\), vagyis \(\displaystyle A\) maradék két eleme is szomszédos. Legyen \(\displaystyle A':=a_6-A=\{a_6-a:a\in A\}\) és \(\displaystyle B':=(35-a_6)-B=\{35-a_6-b:b\in B\}\). Ekkor \(\displaystyle A'\) és \(\displaystyle B'\) hat elemű halmazok, melyekre

\(\displaystyle A'+ B'=(a_6-A)+(35-a_6-B)=35-(A+B)=35-\{0,1,\dots,35\}=\{0,1,\dots,35\},\)

vagyis \(\displaystyle A'\) és \(\displaystyle B'\) is megfelelő halmazpárt alkot. Az \(\displaystyle A'\) halmaz két legkisebb eleme \(\displaystyle a_6-a_6=0\) és \(\displaystyle a_6-a_5=1\), valamint azt is tudjuk, hogy \(\displaystyle a_6-a_4\ne 2\), hiszen \(\displaystyle a_4\) és \(\displaystyle a_5\) nem szomszédosak. Tehát \(\displaystyle A'\)-re is érvényesek a 4. eset során tett eddigi megállapítások. Speciálisan, az \(\displaystyle a_3-a_2\leq a_5-a_4\) egyenlőtlenség mintájára \(\displaystyle (a_6-a_4)-(a_6-a_5)\leq (a_6-a_2)-(a_6-a_3)\), amiből \(\displaystyle a_5-a_4\leq a_3-a_2\). Vagyis csak \(\displaystyle a_3-a_2=a_5-a_4\) lehetséges, és így valóban \(\displaystyle A=\{0,1,2\ell,2\ell+1,4\ell,4\ell+1\}\).

Vizsgáljuk az eseteket \(\displaystyle \ell\) értéke szerint.

Ha \(\displaystyle \ell=2\), akkor \(\displaystyle A=\{0,1,4,5,8,9\}\). Ekkor \(\displaystyle b_1=0,b_2=2\) alapján \(\displaystyle A+\{b_1,b_2\}=\{0,1,\dots,11\}\), így a legkisebb nem fedett eleme a 12, vagyis \(\displaystyle b_3=12\). Ugyanígy folytatva, a legkisebb nem fedett elemek alapján sorra kapjuk, hogy \(\displaystyle b_4=14,b_5=24,b_6=26\). A kapott \(\displaystyle B=\{0,2,12,14,24,26\}\) valóban megfelelő.

Ha \(\displaystyle \ell=3\), akkor \(\displaystyle A=\{0,1,6,7,12,13\}\). Ekkor \(\displaystyle b_1=0, b_2=2,b_3=4\). A korábbiakhoz hasonlóan kapjuk, hogy \(\displaystyle b_4=18,b_5=20,b_6=22\). A kapott \(\displaystyle B=\{0,2,4,18,20,22\}\) valóban megfelelő.

Ha \(\displaystyle \ell=4\), akkor \(\displaystyle A=\{0,1,8,9,16,17\}\). Ekkor \(\displaystyle b_1=0,b_2=2,b_3=4,b_4=6\), és ezután \(\displaystyle b_5=24\) következne, azonban \(\displaystyle a_6+b_5=17+24=41>35\), így nem kapunk megoldást.

Ha \(\displaystyle \ell=5\), akkor \(\displaystyle A=\{0,1,10,11,20,21\}\). Ekkor \(\displaystyle b_1=0,b_2=2,b_3=4,b_4=6,b_5=8\), és ezután \(\displaystyle b_6=30\) következne, azonban \(\displaystyle a_6+b_6=21+30=51>35\), így nem kapunk megoldást.

Végül, ha \(\displaystyle \ell=6\), akkor \(\displaystyle A=\{0,1,12,13,24,25\}\). Ekkor \(\displaystyle b_1=0, b_2=2,b_3=4,b_4=6,b_5=8,b_6=10\). A kapott \(\displaystyle B=\{0,2,4,6,8,10\}\) valóban megfelelő.

Az összes esetet megvizsgáltuk, a kapott \(\displaystyle A\oplus B=\{0,1,\dots,35\}\) előállítások a következők:

\(\displaystyle \{0,1,2,3,4,5\}\oplus \{0,6,12,18,24,30\};\)

\(\displaystyle \{0,1,2,6,7,8\}\oplus \{0,3,12,15,24,27\};\)

\(\displaystyle \{0,1,2,9,10,11\}\oplus \{0,3,6,18,21,24\};\)

\(\displaystyle \{0,1,2,18,19,20\}\oplus \{0,3,6,9,12,15\};\)

\(\displaystyle \{0,1,4,5,8,9\}\oplus \{0,2,12,14,24,26\};\)

\(\displaystyle \{0,1,6,7,12,13\}\oplus \{0,2,4,18,20,22\};\)

\(\displaystyle \{0,1,12,13,24,25\}\oplus \{0,2,4,6,8,10\}.\)

Tehát összesen hét megfelelő felbontás van. Az \(\displaystyle A\leftrightarrow B\) szimmetriát figyelembe véve a megfelelő \(\displaystyle A\oplus B\) előállítások száma tehát \(\displaystyle 2\cdot 7=14\) (a fenti hét előállítást az \(\displaystyle 1\in A,1\notin B\) feltevés mellett kaptuk). A sorok és oszlopok permutálását is figyelembe véve pedig a megfelelő kitöltések száma \(\displaystyle 14\cdot (6!)^2\).

Tehát a táblázat megfelelő kitöltéseinek száma \(\displaystyle 14\cdot (6!)^2=7257600\).

Megjegyzés. Az \(\displaystyle A\oplus B=\{0,1,\dots,35\}\) feltételnek eleget tevő hat elemű halmazokat a következő módon is megkereshetjük. Legyen \(\displaystyle f(x)=x^{a_1}+x^{a_2}+\dots+x^{a_6}\) és \(\displaystyle g(x)=x^{b_1}+x^{b_2}+\dots+x^{b_6}\). Ekkor \(\displaystyle A\oplus B\) pontosan akkor ad megfelelő előállítást, ha \(\displaystyle f(x)g(x)=1+x+x^2+\dots+x^{35}\). Ehhez az \(\displaystyle 1+x+x^2+\dots+x^{35}=\frac{x^{36}-1}{x-1}\) polinom olyan szorzatként való előállításait kell megkeresnünk, ahol mindkét tényezőnek hat nemnulla együtthatója van, melyek mindegyike 1. Jelölje \(\displaystyle \Phi_k\) a \(\displaystyle k\)-adik körosztási polinomot, ezek mind irreducibilisek és bármely \(\displaystyle n\)-re \(\displaystyle x^n-1=\prod\limits_{d\mid n} \Phi_d(x)\). Így kapjuk a következő előállítást irreducibilis polinomok szorzatára:

\(\displaystyle 1+x+x^2+\dots+x^{35}=\Phi_2(x)\Phi_3(x)\Phi_4(x)\Phi_6(x)\Phi_9(x)\Phi_{12}(x)\Phi_{18}(x)\Phi_{36}(x),\)

azaz

\(\displaystyle 1+x+x^2+\dots+x^{35}=(x+1)(x^2+x+1)(x^2+1)(x^2-x+1)(x^6+x^3+1)(x^4-x^2+1)(x^6-x^3+1)(x^{12}-x^6+1).\)

A jobb oldalon minden tényező 1 főegyütthatójú egész együtthatós irreducibilis polinom, így \(\displaystyle f(x)\) és \(\displaystyle g(x)\) úgy áll elő, hogy a tényezőket két csoportba osztjuk, az egyikbe kerülők szorzata lesz \(\displaystyle f(x)\), a másikba kerülőké \(\displaystyle g(x)\). Azt is tudjuk, hogy \(\displaystyle f(1)=g(1)=6\), a jobb oldalon szereplő tényezőkbe 1-et helyettesítve pedig rendre a \(\displaystyle 2,3,2,1,3,1,1,1\) értékeket kapjuk.

Ahhoz, hogy \(\displaystyle f(1)=g(1)=6\)-ot kapjunk, az \(\displaystyle x+1\) és \(\displaystyle x^2+1\) polinomok különböző csoportba kell kerüljenek, és az \(\displaystyle x^2+x+1\) és \(\displaystyle x^6+x^3+1\) polinomok is.

Vizsgáljuk először azt az esetet, ha \(\displaystyle x+1\) és \(\displaystyle x^2+x+1\) egy csoportba, mondjuk \(\displaystyle f(x)\)-hez kerül. Mivel az összes konstans tag 1, ezért az \(\displaystyle f(x)\)-et adó szorzatban \(\displaystyle x\) együtthatója úgy áll elő, hogy a tényezőkben nézzük \(\displaystyle x\) együtthatóját, és ezeket összeadjuk. Ez \(\displaystyle x+1\) és \(\displaystyle x^2+x+1\) esetében \(\displaystyle 1+1=2\), a többi polinom közül \(\displaystyle x^2-x+1\)-ben \(\displaystyle -1\), a többiben pedig 0. Mivel \(\displaystyle f(x)\)-ben csak 0 és 1 együtthatók lehetnek, ezért \(\displaystyle x^2-x+1\)-nek mindeképpen \(\displaystyle f\)-hez kell kerülnie. Tehát \(\displaystyle f(x)\)-et osztja a \(\displaystyle \Phi_2(x)\Phi_3(x)\Phi_6(x) =(x+1)(x^2+x+1)(x^2-x+1)=(x^3+1)(x^2+x+1)=x^5+x^4+x^3+x^2+x+1\) szorzat, \(\displaystyle g(x)\)-et pedig a \(\displaystyle \Phi_4(x)\Phi_9(x)=(x^2+1)(x^6+x^3+1)=x^8+x^6+x^5+x^3+x^2+1\) szorzat.

A \(\displaystyle \Phi_{12}(x)=x^4-x^2+1,\Phi_{18}(x)=x^6-x^3+1,\Phi_{36}(x)=x^{12}-x^6+1\) polinomokat kell még szétosztanunk. A nyolc lehetőséget végignézve kapjuk, hogy az alábbi három esetben kapunk megfelelő polinomokat (vagyis olyanokat, melyekben 6-6 darab nemnulla együttható van, melyek mind 1-esek):

\(\displaystyle f=\Phi_2\Phi_3\Phi_6, \quad g=\Phi_4\Phi_9\Phi_{12}\Phi_{18}\Phi_{36};\)

\(\displaystyle f=\Phi_2\Phi_3\Phi_6\Phi_{12}, \quad g=\Phi_4\Phi_9\Phi_{18}\Phi_{36};\)

\(\displaystyle f=\Phi_2\Phi_3\Phi_6\Phi_{18}, \quad g=\Phi_4\Phi_9\Phi_{12}\Phi_{36}.\)

Ezek rendre az alábbi felbontásokat adják:

\(\displaystyle \{0,1,2,3,4,5\}\oplus \{0,6,12,18,24,30\},\)

\(\displaystyle \{0,1,4,5,8,9\}\oplus \{0,2,12,14,24,26\},\)

\(\displaystyle \{0,1,2,9,10,11\}\oplus \{0,3,6,18,21,24\}.\)

Végül vizsgáljuk azt az esetet, amikor \(\displaystyle x+1\) és \(\displaystyle x^6+x^3+1\) egy csoportba, mondjuk \(\displaystyle f(x)\)-hez kerül. Ekkor \(\displaystyle x^2+1\) és \(\displaystyle x^2+x+1\) mindeképpen \(\displaystyle g\)-hez kerül. Tehát \(\displaystyle f(x)\) osztható a \(\displaystyle \Phi_2(x)\Phi_9(x)=(x+1)(x^6+x^3+1)=x^7+x^6+x^4+x^3+x+1\) szorzattal, \(\displaystyle g(x)\) pedig a \(\displaystyle \Phi_3(x)\Phi_4(x)=(x^2+x+1)(x^2+1)=x^4+x^3+2x^2+x+1\) szorzattal. Azt, hogy \(\displaystyle f(x)\)-ben és \(\displaystyle g(x)\)-ben mi lesz \(\displaystyle x^2\) együtthatója nem befolyásolja, hogy \(\displaystyle \Phi_{18}\) és \(\displaystyle \Phi_{36}\) hova kerülnek. Ha \(\displaystyle \Phi_{12}\) is \(\displaystyle f\)-hez kerülne, akkor \(\displaystyle f\)-ben \(\displaystyle x^2\) együtthatója \(\displaystyle -1\) lenne (akár oda kerül \(\displaystyle \Phi_6\) is, akár nem). Tehát \(\displaystyle \Phi_{12}\) biztosan \(\displaystyle g\)-hez kerül, tehát \(\displaystyle g\) osztható kell legyen a \(\displaystyle \Phi_3(x)\Phi_4(x)\Phi_{12}(x)=x^8+x^7+x^6+x^2+x+1\) polinommal.

A \(\displaystyle \Phi_{6}(x)=x^2-x+1,\Phi_{18}(x)=x^6-x^3+1,\Phi_{36}(x)=x^{12}-x^6+1\) polinomokat kell még szétosztanunk. A nyolc lehetőséget végignézve kapjuk, hogy az alábbi négy esetben kapunk megfelelő polinomokat (vagyis olyanokat, melyekben 6-6 darab nemnulla együttható van, melyek mind 1-esek):

\(\displaystyle f=\Phi_2\Phi_9\Phi_{18}, \quad g=\Phi_3\Phi_4\Phi_{12}\Phi_6\Phi_{36};\)

\(\displaystyle f=\Phi_2\Phi_9\Phi_6\Phi_{18}\Phi_{36}, \quad g=\Phi_3\Phi_4\Phi_{12};\)

\(\displaystyle f=\Phi_2\Phi_9\Phi_{18}\Phi_{36}, \quad g=\Phi_3\Phi_4\Phi_{12}\Phi_6;\)

\(\displaystyle f=\Phi_2\Phi_9\Phi_6\Phi_{18}, \quad g=\Phi_3\Phi_4\Phi_{12}\Phi_{36}.\)

Ezek rendre az alábbi felbontásokat adják:

\(\displaystyle \{0,1,6,7,12,13\}\oplus \{0,2,4,18,20,22\},\)

\(\displaystyle \{0,3,12,15,24,27\}\oplus \{0,1,2,6,7,8\},\)

\(\displaystyle \{0,1,12,13,24,25\}\oplus \{0,2,4,6,8,10\},\)

\(\displaystyle \{0,3,6,9,12,15\}\oplus \{0,1,2,18,19,20\}.\)

Tehát polinomok segítségével is megkaptuk a megfelelő felbontásokat

Statistics:

49 students sent a solution.
6 points:	Argay Zsolt, Bán-Szabó Áron, Baski Bence, Csizmadia Miklós, Duchon Márton, Hegedűs Dániel, Kalocsai Zoltán, Kercsó-Molnár Anita, Kovács 129 Tamás, Kökényesi Márk Péter, Móricz Benjámin, Nádor Benedek, Németh Márton, Seres-Szabó Márton, Szanyi Attila, Török Ágoston.
5 points:	Andó Viola, Bencsik Dávid, Fekete Richárd, Mácsai Dániel, Varga Boldizsár, Wiener Anna.
4 points:	4 students.
3 points:	4 students.
2 points:	4 students.
1 point:	5 students.
0 point:	10 students.

Problems in Mathematics of KöMaL, January 2021