Problem B. 5355. (December 2023)

B. 5355. We colored \(\displaystyle n\) squares red in a square lattice. We numbered the red squares from \(\displaystyle 1\) to \(\displaystyle n\), and calculated the sum of the numbers for each pair of squares that share a common side. Is it true that for all arrangements of the \(\displaystyle n\) squares it is possible to number the red squares in a way that we will get a different sum for all pairs that share a common side?

Submitted by András Imolay, Budapest

(5 pont)

Deadline expired on January 10, 2024.

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

Megoldás. Helyezzük el a kockás füzetlapot egy derékszögű koordinátarendszerben, melynek tengelyei párhuzamosak a füzet vonalaival, egysége megegyezik a füzet rácsnégyzeteinek oldalával és a rácspontok éppen egész pontokba esnek.

Nevezzük egy rácsmező koordinátáinak a bal alsó sarkában levő rácspont koordinátáit és nevezzük egy mező szintjének a mező koordinátáinak összegét. Az azonos szintű mezők középpontjait összekötő szintvonalak így balról jobbra lejtenek, \(\displaystyle -45^{\circ}\)-os meredekséggel. Jelölje \(\displaystyle \ell(m)\), \(\displaystyle x(m)\), \(\displaystyle f(m)\) rendre az \(\displaystyle m\) mező szintjét, \(\displaystyle x\)-koordinátáját és a mindjárt kiosztásra kerülő sorszámát.

A sorszámokat osszuk ki \(\displaystyle 1\)-től \(\displaystyle n\)-ig a piros mezők között úgy, hogy minél alacsonyabb szintű egy mező, annál kisebb sorszámot kapjon, míg az azonos szintű mezők közül a kisebb \(\displaystyle x\)-koordinátájú kapjon kisebb sorszámot. (Azaz \(\displaystyle f(m) < f(m')\) akkor és csak akkor teljesül, ha \(\displaystyle \ell(m) < \ell(m')\); vagy \(\displaystyle \ell(m) = \ell(m')\) és \(\displaystyle x(m) < x(m')\).)

A következőkben belátjuk, hogy ez a számozás eleget tesz a feladat feltételeinek.

Két élszomszédos mező szintje mindig 1-gyel különbözik, ez alapján két szomszédos mező esetén mindig megkülönböztethetünk egy alacsonyabb és egy magasabb (szintű) mezőt. Legyen most \(\displaystyle a_1\) és \(\displaystyle b_1\), illetve \(\displaystyle a_2\) és \(\displaystyle b_2\) két különböző élszomszédos piros mezőpár, mindegyik párban \(\displaystyle a_i\) az alacsonyabb és \(\displaystyle b_i\) a magasabb szintű mező.

Azt kell belátnunk, hogy \(\displaystyle f(a_1) + f(b_1) \neq f(a_2) + f(b_2)\).

1. Ha \(\displaystyle a_1\) és \(\displaystyle a_2\) ugyanaz a mező, akkor \(\displaystyle b_1\) és \(\displaystyle b_2\) különbözik (különben ugyanazt az élszomszédos mezőpárt vizsgáltuk volna kétszer), így persze \(\displaystyle f(a_1) + f(b_1) = f(a_2) + f(b_1) \neq f(a_2) + f(b_2)\), hiszen különböző mezők különböző sorszámokat kaptak.
2. Innentől az általánosság korlátozása nélkül feltehető, hogy \(\displaystyle f(a_1) < f(a_2)\).
   Elegendő belátnunk, hogy ekkor \(\displaystyle f(b_1) \leq f(b_2)\).
• Ha \(\displaystyle \ell(a_1) < \ell(a_2)\) akkor persze \(\displaystyle \ell(b_1) = \ell(a_1)+1 < \ell(a_2) + 1 = \ell(b_2)\), következésképpen \(\displaystyle f(b_1) < f(b_2)\).
• Ha \(\displaystyle \ell(a_1) = \ell(a_2)\), akkor persze \(\displaystyle \ell(b_1) = \ell(b_2)\) és \(\displaystyle x(a_1) +1 \leq x(a_2)\).
  Mivel \(\displaystyle x(b_i) \in \{ x(a_i),x(a_i)+1 \}\), ezért \(\displaystyle x(b_1) \leq x(a_1) + 1 \leq x(a_2) \leq x(b_2)\), tehát \(\displaystyle f(b_1) \leq f(b_2)\).

Ezzel beláttuk, hogy a megadott számozás eleget tesz a feladat feltételeinek.

Statistics:

53 students sent a solution.
5 points:	Ali Richárd, Aravin Peter, Bodor Mátyás, Csató Hanna Zita , Csonka Illés, Fórizs Emma, Görömbey Tamás, Hodossy Réka, Holló Martin, Keresztély Zsófia, Kocsis 827 Péter, Kovács Benedek Noel, Molnár István Ádám, Morvai Várkony Albert, Ozsváth Botond, Petrányi Lilla, Prohászka Bulcsú, Sági Mihály, Sárdinecz Dóra, Sha Jingyuan, Szabó 810 Levente, Szakács Ábel, Szemlér Bálint, Vigh 279 Zalán, Virág Lénárd Dániel, Wágner Márton, Zhai Yu Fan.
4 points:	Danka Emma, Horák Zsófia, Juhász-Molnár Erik, Kővágó Edit Gréta, Maróti Bálint, Varga 511 Vivien.
3 points:	3 students.
2 points:	4 students.
1 point:	3 students.
0 point:	8 students.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, December 2023