A B. 5149. feladat (2021. január)

B. 5149. Hányféleképpen lehet kitölteni egy $\displaystyle 6\times 6$-os táblázat mezőit az $\displaystyle 1,2,\dots,36$ számokkal úgy, 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 legyen?

(6 pont)

A beküldési határidő 2021. február 15-én LEJÁRT.

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

Statisztika:

49 dolgozat érkezett.
6 pontot kapott:	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 pontot kapott:	Andó Viola, Bencsik Dávid, Fekete Richárd, Mácsai Dániel, Varga Boldizsár, Wiener Anna.
4 pontot kapott:	4 versenyző.
3 pontot kapott:	4 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	10 versenyző.

A KöMaL 2021. januári matematika feladatai