A B. 4988. feladat (2018. november)

B. 4988. Egy $\displaystyle (m+2)\times(n+2)$-es táblázatnak levágjuk a négy darab $\displaystyle 1\times1$ méretű ,,sarkát''. Az így kapott csonka táblázat első és utolsó sorának, illetve első és utolsó oszlopának minden mezőjére egy-egy (tetszőleges) valós számot írunk.

Igazoljuk, hogy a táblázat maradék $\displaystyle m\times n$-es ,,belseje'' egyértelműen kitölthető valós számokkal úgy, hogy minden ide eső szám megegyezzen a négy szomszédjának átlagával.

(Iráni feladat)

(6 pont)

A beküldési határidő 2018. december 10-én LEJÁRT.

Megoldás. Nevezzük a levágott sarkú $\displaystyle (m+2)\times (n+2)$-es táblázat egy kitöltését szabályosnak, ha teljesül a feltétel. Ha $\displaystyle A$ egy kitöltés, akkor jelölje $\displaystyle A_{ij}$ az $\displaystyle i$-edik sor $\displaystyle j$-edik mezőjébe írt számot ($\displaystyle 1\leq i\leq m+2,1\leq j\leq n+2$, a sarkokba nem kerül szám). Az első és utolsó sorban és oszlopban lévő mezőket (vagyis amikor $\displaystyle i\in \{1,m+2\}$ vagy $\displaystyle j\in\{1,n+2\}$) hívjuk szélső mezőknek, a többit pedig belső mezőknek. A feladat annak igazolása, hogy a szélső mezők bármely kitöltése egyértelműen terjeszthető ki a táblázat egy szabályos kitöltésévé.

Könnyen látható, hogy szabályos kitöltések összege és különbsége is szabályos, ahol az $\displaystyle A$ és $\displaystyle B$ kitöltések összegén (illetve különbségén) azt a $\displaystyle C$ kitöltést értjük, melyre minden (szóba jövő) $\displaystyle i,j$ mellett $\displaystyle C_{ij}=A_{ij}+B_{ij}$ (illetve $\displaystyle C_{ij}=A_{ij}-B_{ij}$), vagyis a kitöltéseket ,,mezőnként'' összeadjuk (kivonjuk).

Először az egyértelműséget igazoljuk. Tegyük fel, hogy a szélső mezők valamely kitöltése esetén $\displaystyle A$ és $\displaystyle B$ is szabályos kiterjesztés. Ekkor legyen $\displaystyle C$ az $\displaystyle A$ és $\displaystyle B$ kitöltések különbsége, ez egy olyan szabályos kitöltés, aminél a szélső mezők mindegyike 0-t tartalmaz. Megmutatjuk, hogy $\displaystyle C$-nél minden mezőbe 0-t kell írnunk (és így $\displaystyle A=B$). Legyen $\displaystyle C$-nél a(z egyik) legnagyobb abszolút értékű, belső mezőbe írt szám $\displaystyle C_{ij}=c$. Mivel $\displaystyle C_{ij}$ abszolút értéke maximális, ezért $\displaystyle C_{ij}$ csak úgy lehet a négy szomszédjának átlaga, ha mind a négy szomszédjába is $\displaystyle c$-t írtunk. Ezt folytatva azt kapjuk, hogy mindenhova, az összes belső és szélső mezőbe is $\displaystyle c$-t írtunk, vagyis $\displaystyle c=0$, és így $\displaystyle C$ az azonosan 0 kitöltés. Ezzel az egyértelműséget igazoltuk.

A létezést először abban az esetben igazoljuk, amikor a szélső sorokban/oszlopokban minden érték nemnegatív. Kezdetben írjunk minden belső mezőbe 0-t, legyen ez a $\displaystyle C^{(0)}$ kitöltés. Ha a $\displaystyle C^{(k)}$ kitöltést már definiáltuk, akkor ebből úgy kapjuk a $\displaystyle C^{(k+1)}$ kitöltést, hogy minden belső mezőbe a $\displaystyle C^{(k)}$-nál a szomszédjaiba írt számok átlagát írjuk:

(A szélső mezőkbe írt számok pedig végig változatlanok maradnak.)

Megmutatjuk, hogy minden $\displaystyle i,j$-re a $\displaystyle C^{(k)}_{ij}$ sorozat monoton növekedő:

$\displaystyle C^{(k)}_{ij}\leq C^{(k+1)}_{ij}.$

Ha $\displaystyle k=0$, akkor ez világos, hiszen kezdetben minden belső mezőben 0 volt, utána pedig mindenhova nemnegatív számok átlaga került. Innen indukcióval azonnal következik $\displaystyle (*)$ alapján, hogy a monoton növekedés továbbra is érvényben marad, hiszen mindig a korábbiaknál nagyobb(-egyenlő) számok átlagát vesszük a következő lépésben.

Ha $\displaystyle C^{(0)}$-nál a legnagyobb szám $\displaystyle M$, akkor világos, hogy $\displaystyle M$ felső korlát az összes $\displaystyle C^{(k)}_{ij}$ számra, hiszen $\displaystyle M$-nél nem nagyobb számok átlaga továbbra is $\displaystyle M$-nél nem nagyobb szám lesz. Vagyis rögzített $\displaystyle i,j$ mellett $\displaystyle C^{(k)}_{ij}$ egy monoton növekedő korlátos sorozat, ami így konvergens, legyen a határértéke $\displaystyle C_{ij}$. Ha $\displaystyle k\to \infty$, akkor $\displaystyle (*)$ bal és jobb oldala is konvergál ugyanahhoz a véges határértékhez, így: $\displaystyle C_{ij}=\frac{C_{i-1,j}+C_{i+1,j}+C_{i,j-1}+C_{i,j+1}}{4}$. Tehát $\displaystyle C_{ij}$ a táblázat egy megfelelő kitöltése.

Legyen most $\displaystyle A$ egy tetszőleges kitöltése a szélső mezőknek. Világos, hogy $\displaystyle A$ felírható a szélső mezők két olyan kitöltése különbségeként ($\displaystyle A=B-C$), amelyek csak nemnegatív értékeket tartalmaznak. Ha $\displaystyle A_{ij}$ valamelyik szélső mezőbe írt szám, akkor legyen $\displaystyle B_{ij}=\max(A_{ij},0)$ és $\displaystyle C_{ij}=max(0,-A_{ij})$. Ekkor $\displaystyle A_{ij}=B_{ij}-C_{ij}$, hiszen bármely valós $\displaystyle x$-re $\displaystyle x=\max(x,0)-\max(0,-x)$.

A korábbiak szerint $\displaystyle B$ és $\displaystyle C$ kiterjeszhető szabályos kitöltéssé, ezek különbsége pedig $\displaystyle A$ egy szabályos kiterjesztése.

Ezzel igazoltuk, hogy a szélső mezők bármely kitöltése esetén pontosan egyféle szabályos kitöltése létezik a táblázatnak.

Statisztika:

29 dolgozat érkezett.
6 pontot kapott:	Sebestyén Pál Botond, Tóth 827 Balázs, Weisz Máté.
5 pontot kapott:	Beke Csongor, Dobák Dániel, Mátravölgyi Bence, Szabó 417 Dávid.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	6 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	10 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2018. novemberi matematika feladatai