Problem A. 749. (April 2019)
A. 749. Given are two polyominos, the first one is an L-shape consisting of three squares, the other one contains at least two squares. Prove that if \(\displaystyle n\) and \(\displaystyle m\) are co-prime then at most one of the \(\displaystyle n\times n\) and \(\displaystyle m\times m\) boards can be tiled by translated copies of the two polyominos.
Proposed by: András Imolay, Dávid Matolcsi, Ádám Schweitzer and Kristóf Szabó, Budapest
(7 pont)
Deadline expired on May 10, 2019.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
3 students sent a solution. 7 points: Schrettner Jakab. 2 points: 1 student. 0 point: 1 student.
Problems in Mathematics of KöMaL, April 2019