 |
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:
| \(\displaystyle C_{ij}^{(k+1)}=\frac{C^{(k)}_{i-1,j}+C^{(k)}_{i+1,j}+C^{(k)}_{i,j-1}+C^{(k)}_{i,j+1}}{4}. \) | \(\displaystyle {(*)}\) |
(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