Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 749. feladat (2019. április)

A. 749. Adott két poliominó. Az egyik egy három négyzetből álló L-alak, a másik legalább két négyzetből áll. Bizonyítsuk be, hogy ha \(\displaystyle n\) és \(\displaystyle m\) relatív prímek, akkor az \(\displaystyle n\times n\)-es és az \(\displaystyle m\times m\)-es tábla közül legfeljebb az egyik rakható ki a két poliominó eltoltjaival.

Javasolta: Imolay András, Matolcsi Dávid, Schweitzer Ádám és Szabó Kristóf (Budapest)

(7 pont)

A beküldési határidő 2019. május 10-én LEJÁRT.


Megoldás. A táblákhoz, és a fedéshez használt csempékhez is kétváltozós polinomokat rendelünk. Koordinátázzuk meg a rácsnégyzeteket egész számpárokkal. Ha \(\displaystyle A\) rácsnégyzetek egy halmaza, akkor ehhez a

\(\displaystyle \sum_{(a,b)\in A} x^a y^b \)

polinomot rendeljük.

Az \(\displaystyle n\times n\)-es és az \(\displaystyle m\times m\)-es tábláknak megfelelő polinomok

\(\displaystyle T_n(x,y) = \sum_{0\le j<n}\sum_{0\le k<n}x^jy^k = \frac{(1-x^n)(1-y^n)}{(1-x)(1-y)}, \qquad\text{ill.}\quad T_m(x,y) = \frac{(1-x^m)(1-y^m)}{(1-x)(1-y)}. \)

A csempézéshez használt két poliominó polinomja \(\displaystyle 1+x+y\), illetve valamilyen \(\displaystyle 0/1\) együtthatós, nem konstans \(\displaystyle Q(x,y)\). A tábla kicsempézése azt jelenti, hogy valamilyen \(\displaystyle 0/1\) együtthatós \(\displaystyle A,B,C,D\) polinomokkal

\(\displaystyle A(x,y)(1+x+y) + B(x,y)Q(x,y) = T_n(x,y), \qquad C(x,y)(1+x+y) + D(x,y)Q(x,y) = T_m(x,y). \)\(\displaystyle (1) \)

A két poliominó méretéből leolvashatjuk, hogy \(\displaystyle \deg A\le 2n-4\), \(\displaystyle \deg B\le 2n-3\), \(\displaystyle \deg C\le 2m-4\) és \(\displaystyle \deg D\le 2m-3\).

Az (1)-be helyettesítsünk \(\displaystyle y=(-1-x)\)-et:

\(\displaystyle B(x,-1-x) Q(x,-1-x) = T_n(x,-1-x), \)\(\displaystyle (2) \)
\(\displaystyle D(x,-1-x) Q(x,-1-x) = T_m(x,-1-x). \)\(\displaystyle (3) \)

A \(\displaystyle T_n(x,-1-x)\) és a \(\displaystyle T_m(x,-1-x)\) komplex gyökeinek halmaza

\(\displaystyle Z_n = \Big\{e^{k\cdot 2\pi i/n}: k=1,2,\ldots,n-1\Big\} \cup \Big\{-1-e^{k\cdot 2\pi i/n}: k=1,2,\ldots,n-1\Big\}, \)

illetve

\(\displaystyle Z_m = \Big\{e^{k\cdot 2\pi i/m}: k=1,2,\ldots,m-1\Big\} \cup \Big\{-1-e^{k\cdot 2\pi i/m}: k=1,2,\ldots,m-1\Big\}, \)

A gyökök egy \(\displaystyle 0\), illetve egy \(\displaystyle -1\) középpontú egységkörvonalon vannak; a két kör metszéspontjai harmadik egységgyökök; ebből leolvasható, hogy \(\displaystyle Z_n\) és \(\displaystyle Z_m\) diszjunkt.

A \(\displaystyle T_n(x,-1-x)\) és \(\displaystyle T_m(x,-1-x)\) polinomoknak tehát nincs közös komplex gyöke, de a \(\displaystyle Q(x,-1-x)\) polinom közös osztójuk, tehát \(\displaystyle Q(x,-1-x)\) nemnulla konstans. Ez viszont ellentmondás, mert \(\displaystyle \deg B(x,-1-x)<2n-2=\deg T_n(x,-1-x)\) és ugyanígy \(\displaystyle \deg D(x,-1-x)<2m-2=\deg T_m(x,-1-x)\).

Alternatív befejezés:

Az \(\displaystyle m,n\) szerepe szimmetrikus, és relatív prímek, ezért feltehető, hogy \(\displaystyle n\) nem osztható \(\displaystyle 3\)-mal; ekkor \(\displaystyle |Z_n|=2n-2\).

A (3) jobboldalának nincs gyöke \(\displaystyle Z_n\)-ben, tehát \(\displaystyle Q(x,-1-x\))-nek sincs. Ezért \(\displaystyle B(x,-1-x)=0\) minden \(\displaystyle x\in Z_n\)-re. Ekkor viszont

  • \(\displaystyle B(x,-1-x)\) nem a \(\displaystyle 0\) polinom, mert osztója a nemnulla \(\displaystyle T_n(x,-1-x)\) polinomnak;
  • \(\displaystyle \deg B\le 2n-3\),
  • \(\displaystyle B(x,-1-x)\)-nek minden \(\displaystyle Z_n\)-beli komplex szám gyöke.

Ez így ellentmondás, mert a nemnulla \(\displaystyle B(x,-1-x)\) polinomnak több gyöke van, mint a foka.


Statisztika:

Az A. 749. feladat értékelése még nem fejeződött be.


A KöMaL 2019. áprilisi matematika feladatai