Feladat: 2009. évi Kürschák matematikaverseny 1. feladata Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 2010/február, 68 - 69. oldal  PDF file
Témakör(ök): Kürschák József (korábban Eötvös Loránd), Egész számok összege, Számelrendezések, Szélsőérték-feladatok differenciálszámítás nélkül
Hivatkozás(ok):Feladatok: 2010/február: 2009. évi Kürschák matematikaverseny 1. feladata

Egy n×k-as táblázatba úgy írunk be egész számokat, hogy mind az n sorban szerepeljen 1-től k-ig minden egész szám. Jelöljük S-sel a kapott k oszlopösszeg legnagyobbikát. Minden n-re és k-ra adjuk meg S lehetséges legkisebb értékét!

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. A feladat szövegéből adódóan n és k pozitív egészek. Világos, hogy n=1 esetén S=k, ezért a továbbiakban feltesszük, hogy n2. A táblázat minden sorában a beírt számok összege 1+2+...+k=12k(k+1), így a táblázatbeli számok összege 12nk(k+1). A k oszlop valamelyikében tehát az összeg legalább 12n(k+1), vagyis S12n(k+1). Ebből

S12n(k+1)1
következik, tekintve, hogy S a definíciójából adódóan egész szám. Megmutatjuk, hogy n2 esetén ez lesz az S pontos értéke. Ehhez azt kell igazolni, hogy létezik olyan táblázatkitöltés, amiben minden oszlopösszeg legfeljebb
12n(k+1).

Ha n páros, akkor könnyű ilyet találni: a páratlanodik sorokba növekvő, a páros sorszámúakba csökkenő sorrendben írjuk be az egészeket. Ezáltal az i-edik oszlopösszeg
n2i+n2(k+1-i)=12n(k+1)
lesz. Ha n páratlan (és n3), akkor is megtehetjük, hogy az első n-3 sort a fentiek szerint töltjük ki (hiszen páros számú sorról van szó), és ezáltal minden oszlopban az első n-3 elem összege 12(n-3)(k+1) lesz. Ahhoz tehát, hogy minden oszlopban az összeg legfeljebb
12n(k+1)
legyen, az szükséges, hogy a táblázat utolsó három sorát úgy töltsük ki, hogy minden oszlop utolsó három elemének összege legfeljebb
12n(k+1)-12(n-3)(k+1)=12n(k+1)-12(n-3)(k+1)=32(k+1)
legyen. Ez pedig éppen azt jelenti, hogy az utolsó 3 sorba egy a feladatban leírt 3×k méretű táblázatot kell elhelyeznünk. A továbbiakban tehát az n=3 esetre szorítkozunk.
Ha k=2m+1 páratlan, azaz S=3(k+1)2=3(m+1), akkor az alábbi módon kitöltött táblázat megfelel a célnak:
12...i...m+1m+2...j...2m+12m+12m-1...2m+3-2i...12m...4m+4-2j...2m+1m+2...m+i...2m+11...j-m-1...m

Ha pedig k=2m páros szám és
S=3(k+1)2=6m+32=3m+2,
akkor például az alábbi módon tölthetjük ki a 3×k méretű táblázatot:
12...i...mm+1...j...2m2m2m-2...2m+2-2i...22m-1...4m+1-2j...1m+1m+2...m+i...2m1...j-m...m

Könnyen ellenőrizhető, hogy mindkét táblázatban minden sorban szerepel 1 és k között az összes egész, továbbá, hogy egyetlen oszlopösszeg sem nagyobb S-nél.  
1x  az  x  szám felső egész része; a legkisebb egész szám, amely nem kisebb  x-nél.