Problem A. 826. (April 2022)
A. 826. An antelope is a chess piece which moves similarly to the knight: two cells \(\displaystyle (x_1, y_1)\) and \(\displaystyle (x_2, y_2)\) are joined by an antelope move if and only if
\(\displaystyle \big\{|x_1-x_2|, |y_1-y_2|\big\} = \{3, 4\}. \)
The numbers from \(\displaystyle 1\) to \(\displaystyle 10^{12}\) are placed in the cells of a \(\displaystyle 10^6 \times 10^6\) grid. Let \(\displaystyle D\) be the set of all absolute differences of the form \(\displaystyle |a-b|\), where \(\displaystyle a\) and \(\displaystyle b\) are joined by an antelope move in the arrangement. How many arrangements are there such that \(\displaystyle D\) contains exactly four elements?
Proposed by Nikolai Beluhov, Bulgaria
(7 pont)
Deadline expired on May 10, 2022.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Válasz: Egybevágóság erejéig az egyetlen lehetséges elrendezés az, ha sorban felsoroljuk a számokat, azaz az \(\displaystyle i\). sorba balról jobbra \(\displaystyle (i-1) \cdot 10^6+1\)-től \(\displaystyle i \cdot 10^6\)-ig írjuk be a számokat. Ezt el tudjuk forgatni háromféleképpen, és tudjuk négyféleképpen tükrözni, így összesen \(\displaystyle 8\) megfelelő elrendezés van.
Tekintsünk egy tetszőleges elrendezést, amelyben \(\displaystyle |D|=4\). Legyen \(\displaystyle D=\{p,q,r,s\}\). A megoldás során a táblázat mezőire kétféleképpen hivatkozunk, vagy egy számmal, ami a beleírt szám, vagy egy számpárral, ami azt írja le, hogy hanyadik sorban és hanyadik oszlopban van a mező. Két mezőt szomszédosnak nevezek, ha el lehet jutni az egyikből a másikba antilopugrással.
Figyeljük meg, hogy egy olyan mezőnek, amely nincs a táblázat valamelyik szélső 4 sorában vagy oszlopában, \(\displaystyle 8\) szomszédja van, ami csak úgy lehetséges, hogy ha \(\displaystyle u\) a mezőhöz rendelt szám, akkor a szomszédai valamilyen sorrendben \(\displaystyle u-p, u+p, u-q, u+q, u-r, u+r, u-s, u+s\).
Lemma: Legyen \(\displaystyle abcd\) egy rombusz, amelynek minden oldala antilopugrás. Ekkor \(\displaystyle a+c=b+d\).
Bizonyítás: Legyen \(\displaystyle a-b=k\), \(\displaystyle b-c=l\), \(\displaystyle a-d=m\) és \(\displaystyle d-c=n\). Ekkor \(\displaystyle k \neq m\), \(\displaystyle l \neq n\) és \(\displaystyle k+l=m+n\), továbbá világos, hogy \(\displaystyle |k|, |l|, |m|\) és \(\displaystyle |n|\) mind a \(\displaystyle p,q,r,s\) számok valamelyikével egyenlőek.
Legyen \(\displaystyle u\) egy olyan mező, amelynek \(\displaystyle 8\) antilopszomszédja van, és a szomszédainak is \(\displaystyle 8\) antilopszomszédja van. Ekkor \(\displaystyle u\) egy szomszédja \(\displaystyle u-k\), és neki egy szomszédja \(\displaystyle v=u-k-l\), ami nem egyezhet meg \(\displaystyle u\)-val, mert akkor \(\displaystyle k+l=a-c=0\) lenne, ami nem lehet. Tudjuk, hogy \(\displaystyle u\) szomszédai között vannak az \(\displaystyle u-k, u-l, u-m, u-n\) mezők, és \(\displaystyle v\) szomszédai között vannak a \(\displaystyle v+l, v+k, v+n, v+m\) mezők, ráadásul ez a két négyes megegyezik, mivel \(\displaystyle k+l=m+n\). De az \(\displaystyle u\)-nak és \(\displaystyle v\)-nek legfeljebb két közös szomszédja lehet, így az \(\displaystyle u-k, u-l, u-m, u-n\) értékek között csak két különböző lehet. Megint a \(\displaystyle k+l=m+n\) miatt nem lehet, hogy \(\displaystyle k=l\) és \(\displaystyle m=n\), mert akkor \(\displaystyle k=m\) volna, így csak az lehet, hogy \(\displaystyle k=n\) és \(\displaystyle l=m\), ami pont azt jelenti, hogy \(\displaystyle a-b=d-c\), és ezzel ekvivalens a lemma állítása.
Lemma: Minden olyan \(\displaystyle a\) és \(\displaystyle b\) szomszédos mezők esetén, melyre az \(\displaystyle a\)-ból \(\displaystyle b\)-be a \(\displaystyle (3,4)\) vektorral lehet eljutni, az \(\displaystyle a-b\) érték konstans.
Bizonyítás: Legyen \(\displaystyle a\), \(\displaystyle b\) és \(\displaystyle a'\), \(\displaystyle b'\) két olyan pár, amiről a lemma szól. Hagyjuk el a felső 4 sort és jobb oldali 3 oszlopot, és tekintsük csak az olyan antilopugrásokat, amelyek nem \(\displaystyle (3,4)\) irányúak. Figyeljük meg, hogy még ekkor is összefüggő marad a szomszédsági gráf, és \(\displaystyle a\) és \(\displaystyle a'\) beleesik a táblázat ezen részébe, mivel a \(\displaystyle (3,4)\)-gyel eltoltjuk is a táblázatban van, így van egy olyan \(\displaystyle a=c_1, c_2, \ldots , c_k=a'\) sorozat, hogy \(\displaystyle c_ic_{i+1}\) antilopugrás minden \(\displaystyle 1 \leq i<k\) esetén, és nem \(\displaystyle (3,4)\)-gyel párhuzamos irányú, továbbá egyik \(\displaystyle c_i\) sincs a felső \(\displaystyle 4\) sorban vagy jobb oldali 3 oszlopban. Legyen \(\displaystyle d_i\) a \(\displaystyle c_i\) mezőtől \(\displaystyle (3,4)\) vektorral eltolt mező, ekkor \(\displaystyle d_i\) is a táblázatban van minden \(\displaystyle 1 \leq i \leq k\)-ra. Figyeljük meg, hogy \(\displaystyle c_id_id_{i+1}c_{i+1}\) rombusz minden \(\displaystyle 1 \leq i <k\) esetén, így az előző lemma szerint
\(\displaystyle a-b=c_1-d_1=c_2-d_2= \ldots =c_k-d_k=a'-b',\)
és pont ezt akartuk bizonyítani.
Világos, hogy az előző lemma \(\displaystyle (3,4)\) irány helyett bármelyik más antilop ugrásra is pont ugyanígy igaz.
Lemma: Minden \(\displaystyle a\) és \(\displaystyle b\) mezőre, ahol \(\displaystyle b\) a jobb szomszédja az \(\displaystyle a\)-nak, az \(\displaystyle a-b\) érték ugyanaz.
Bizonyítás: Az előző lemma bizonyításához hasonlóan, ha \(\displaystyle a\), \(\displaystyle b\) és \(\displaystyle a'\), \(\displaystyle b'\) két olyan pár, hogy \(\displaystyle b\) és \(\displaystyle b'\) rendre az \(\displaystyle a\) és \(\displaystyle a'\) jobb szomszédja, akkor világos, hogy van \(\displaystyle a=c_1, c_2, \ldots c_k=a'\), hogy minden ugrás antilopugrás, és semelyik \(\displaystyle c_i\) nincs a jobb oszlopban. Ekkor a jobb szomszédaik, \(\displaystyle d_1, d_2, \ldots d_k\) is egy antilopugrás sorozatot alkotnak, így az előző lemma szerint
\(\displaystyle a-b=c_1-d_1=c_2-d_2= \ldots =c_k-d_k=a'-b',\)
és pont ezt akartuk.
Természetesen ugyanígy igaz a lemma, ha nem a jobb oldali szomszédra mondjuk ki, hanem a baloldalira, fentire vagy lentire. Legyen \(\displaystyle b-a=y\), ha \(\displaystyle b\) az \(\displaystyle a\)-nak a jobb szomszédja, és \(\displaystyle d-c=z\), amennyiben \(\displaystyle d\) a \(\displaystyle c\)-nek a felső szomszédja. Tegyük fel, hogy \(\displaystyle y\) és \(\displaystyle z\) is pozitív. Ekkor soronként és oszloponként is monoton nőnek a számok, így az 1 csak az \(\displaystyle (1,1)\) mezőbe kerülhet.
Ekkor ha \(\displaystyle (i-1)\)-t lépünk jobbra, és \(\displaystyle (j-1)\)-t felfele, akkor az érték \(\displaystyle (i-1)y+(j-1)z\)-vel nő, azaz minden \(\displaystyle 1 \leq i,j \leq 10^6\) esetén az \(\displaystyle (i,j)\) mezőbe az \(\displaystyle (i-1)y+(j-1)z+1\) számot kell írnunk.
Speciálisan a \(\displaystyle (10^6,10^6)\) mezőbe a \(\displaystyle (10^6-1)(y+z)+1\) kerül, ám ugyanúgy ahogy a bal alsó sarokba az \(\displaystyle 1\) került, ide a legnagyobb számnak, azaz \(\displaystyle 10^{12}\)-nek kell kerülnie. Ezek alapján \(\displaystyle y+z=10^6+1\).
Tegyük fel, hogy \(\displaystyle \{y,z\} \neq \{1,10^6\}\). Ekkor mindkettő kisebb, mint \(\displaystyle 10^6\), így az \(\displaystyle (1,y+1)\) és a \(\displaystyle (z+1,1)\) mezőkbe az \(\displaystyle yz+1\) kerül, ami nem lehet, mert nem kerülhet két mezőbe ugyanaz a szám. Emiatt tényleg csak az lehet, hogy az egyik \(\displaystyle 1\) és a másik \(\displaystyle 10^6\), ami pont az a konstrukció, amit az elején leírtunk.
Világos, hogy hasonlóan működik a gondolatmenet, ha \(\displaystyle y\) és \(\displaystyle z\) nem mindegyike pozitív, csak ekkor egy másik sarokba kerül az \(\displaystyle 1\)-es, de onnan ugyanígy elmondható a fenti okoskodás. Emiatt tényleg \(\displaystyle 8\) lehetőség van, megválaszthatjuk az \(\displaystyle y\) előjelét, a \(\displaystyle z\) előjelét, és hogy melyikük legyen \(\displaystyle 1\) abszolút értékű. Ezek természetesen ugyanazokat a konstrukciókat adják, amelyek a megoldás elején szerepeltek.
Statistics:
1 student sent a solution. 3 points: 1 student.
Problems in Mathematics of KöMaL, April 2022