Cím: A 2009. évi Kürschák József Matematikai Tanulóverseny feladatainak megoldása
Szerző(k):  Fleiner Tamás 
Füzet: 2010/február, 68 - 71. oldal  PDF file
Témakör(ök): Kürschák József (korábban Eötvös Loránd)

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.

1. feladat. 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!

 
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.  
 
2. feladat. Határozzuk meg azokat a pozitív egészekből álló (a,b) számpárokat, amelyekre igaz az alábbi állítás: a pozitív egészek halmaza felbontható két diszjunkt halmaz, H1 és H2 uniójára úgy, hogy sem a, sem b nem írható fel sem két H1-beli, sem két H2-beli szám különbségeként.
 
Megoldás. Tekintsük az 1,1+a,1+2a,1+3a,..., illetve az 1,1+b,1+2b,1+3b,... sorozatokat. E két sorozat bármelyikére igaz, hogy két szomszédos elemének különbsége a vagy b, ezért semelyik két szomszédos elem sem lehet a H1 és H2 halmazok közül ugyanabban. Más szóval mindkét sorozat felváltva tartalmaz H1 és H2-beli elemeket. Azt kaptuk tehát, hogy az 1+ka és az 1+b egészek pontosan akkor vannak ugyanabban a halmazban, ha k és paritása megegyezik (hiszen mindkét sorozat első eleme 1).
Legyen n, illetve m az a, illetve b kanonikus alakjában a 2 prímtényező kitevője, azaz a=2na' és b=2mb', ahol a', illetve b' páratlan számok. Az általánosság megszorítása nélkül feltehetjük, hogy nm teljesül. Tekintsük az x:=1+2na'b' számot. Mivel x=1+b'a ugyanabban a halmazban van, mint x=1+a'2n-mb, a fenti megfigyelésünkből az adódik, hogy b' és a'2n-m paritása megegyezik, vagyis a'2n-m páratlan, ami csak úgy lehetséges, ha n-m=0, azaz ha n=m. Azt kaptuk tehát, hogy ha lehetséges a pozitív egészeket két halmaz uniójára bontani a feladatban leírt módon, akkor a és b kanonikus alakjában a 2 prímtényező ugyanazon a kitevőn szerepel.
A megoldást annak megmutatásával fejezzük be, hogy ebben az esetben (tehát ha n=m) megadható a kívánt felbontás. Legyen ugyanis

H1:={kZ:k>0  és  k2n  páratlan},   illetveH2:={kZ:k>0  és  k2n  páros}.
2

Ez a választás megfelelő, hiszen ha x-y=a, akkor x=y+a, tehát
x2n=y+a2n=y2n+a2n=y2n+a'=y2n+a'.
Mivel a' páratlan, ez azt jelenti, hogy x és y egyike H1-beli, a másik pedig H2 eleme. Hasonlóan látható, hogy ha két pozitív egész különbsége b, akkor azok különböző halmazokból valók:
x-y=bx=y+bx2n=y+b2n=y2n+b2n=y2n+b'=y2n+b'.

Azt kaptuk tehát, hogy pontosan akkor létezik a feladatban leírt felbontás, ha a és b prímtényezős felbontásában a 2 prím ugyanazon a kitevőn szerepel.  
 
Megjegyzések. 1. Könnyen látható, hogy ha a és b pontosan ugyanazokkal a 2-hatványokkal osztható, akkor a pozitív egészeknek a feladat szerinti bármely felbontása úgy áll elő, hogy a 2n szerinti maradékosztályok elemeit ,,felváltva'' tesszük H1-be és H2-be.
2. Ha a H1-ben, illetve H2-ben fellépő különbségekből nem két számot (a-t és b-t) tiltunk meg, hanem többet, akkor a megoldásban leírt módszerrel igazolható, hogy pontosan akkor létezik a kívánt partíció, ha a tiltott számok mindegyikének kanonikus alakjában ugyanazzal a kitevővel szerepel a 2 prímosztó. A lehetséges halmazokba osztások itt is pontosan úgy kaphatók, ahogy azt az 1. megjegyzésben leírtuk.
3. Nagy Dániel azt figyelte meg, hogy három halmaz (H1, H2 és H3) uniójára mindig felbonthatók a pozitív egészek úgy, hogy semelyik halmazon belül se lépjen fel a vagy b különbség. Ez a tény a ,,mohó színezés'' erre az esetre történő alkalmazásával igazolható: sorra eldöntjük az 1,2,3,... számokról, hogy a Hi halmazok közül melyikbe tesszük. Konkrétan: a soron következő k pozitív egészhez úgy választjuk a k-t tartalmazó halmazt, hogy k ne legyen egy halmazban a korábban már valamelyik halmazba besorolt (k-a) és (k-b) számok egyikével sem. Mivel három halmazunk van, ezt mindig megtehetjük. Ezzel a módszerrel minden pozitív egészt a H1, H2 és H3 halmazok közül pontosan egyhez rendelünk, és a konstrukcióból adódóan az így kapott felbontás rendelkezik a kívánt tulajdonsággal. Az is könnyen látható, hogy ha a 2. megjegyzésben leírtak szerint több tiltott számunk van (mondjuk ), akkor a pozitív egészek halmaza bizonyosan felbontható +1 halmaz uniójára a feladatban leírt módon.

 
3. feladat. Határozzuk meg azokat az f függvényeket, amelyekre
(i) f az egész számok halmazán van értelmezve;
(ii) f(z) racionális szám minden z egész szám esetén;
(iii) ha f(x)<c<f(y) és c racionális, akkor f felveszi a c értéket; és
(iv) ha x, y, z egészek és összegük nulla, akkor
f(x)+f(y)+f(z)=f(x)f(y)f(z)
teljesül.
 
Megoldás. Vegyük észre, hogy az f0 függvény teljesíti a feladatban leírt feltételeket. Megmutatjuk, hogy ezen kívül nincs más ilyen tulajdonságú függvény.
A (iv) feltételből x=y=z=0 helyettesítéssel adódik, hogy 3f(0)=f(0)3, azaz f(0)(f(0)2-3)=0. Innen f(0)=0 vagy f(0)2=3 következik, ám az utóbbi lehetőség ellentmond (ii)-nek, így f(0)=0. Ezek után y=-x és z=0 helyettesítéssel (iv) f(x)+f(-x)=0 alakot ölt, tehát f(x)=-f(-x) teljesül minden x egész számra, vagyis f páratlan függvény. Végül az y=x és z=-2x helyettesítéssel (iv)-ből azt kapjuk, hogy 2f(x)-f(2x)=-f(x)2f(2x), azaz
2f(x)=f(2x)(1-f(x)2).(1)

Tegyük fel tehát, hogy f0, azaz van olyan x egész, amire f(x)0. Ekkor (1) bal oldala nemnulla, így a jobb oldal sem lehet zérus, tehát |f(x)|1 teljesül minden olyan x egészre, ami nem gyöke f-nek. Más szóval az f függvény nem veszi fel az 1 és -1 értékek egyikét sem. Láttuk, hogy f(0)=0, ezért (iii) miatt |f(n)|<1 teljesül minden n egészre. Ha tehát 0<|f(x)|<1, akkor (1) miatt
|f(2x)|=|2f(x)1-f(x)2|=|2f(x)||1-f(x)2|>2|f(x)|1=2|f(x)|
adódik, azaz |f(2nx)|>2n|f(x)|, ha n>1 egész. Legyen n olyan pozitív egész, amire 2n>1|f(x)| teljesül. Ekkor
|f(2nx)|>2n|f(x)|>1|f(x)||f(x)|=1,
márpedig ez ellentmond a fenti megfigyelésnek, ami szerint |f|<1. Tehát f0 az egyedüli olyan függvény, ami teljesíti az (i)(iv) feltételeket.  
 
Megjegyzés. Többen észrevették, hogy a feladat (iv) feltétele teljesül a tangens függvényre. Ez a megfigyelés, mint láttuk, nem szükséges a megoldáshoz, de ennek ismerete rávilágít annak ötletére. Ha ugyanis az f függvényre fennáll a (iv) tulajdonság, akkor α:=arcctg(f(1)) választással tetszőleges n pozitív egészre f(n)=tg(nα) adódik. Mivel tg(±π2) nem értelmes, azért nα=±π2+2kπ semmilyen egész n, k esetén sem teljesülhet, így olyan egész m sem létezik, amire tg(mα)=±1 áll. A (iii) feltétel miatt ekkor |f|<1, márpedig ha tg(α)0, akkor az α alkalmas többszörösének tangense 1-nél nagyobb abszolút értékű lesz.


1x az x szám felső egész része; a legkisebb egész szám, amely nem kisebb x-nél.

2Egy x szám x alsó egész része (vagy egész része) az a legnagyobb egész szám, amely nem nagyobb x-nél.