Kezdőlap


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 \| MathML
Témakör(ök):	Kürschák József (korábban Eötvös Loránd), Matematika, Szakmai cikkek

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 \times 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

n \geq 2

. A táblázat minden sorában a beírt számok összege

1 + 2 + ... + k = \frac{1}{2} k (k + 1)

, így a táblázatbeli számok összege

\frac{1}{2} n k (k + 1)

. A

k

oszlop valamelyikében tehát az összeg legalább

\frac{1}{2} n (k + 1)

, vagyis

S \geq \frac{1}{2} n (k + 1)

. Ebből

\begin{matrix} S \geq ⌈ \frac{1}{2} n (k + 1) ⌉ \end{matrix}

¹

következik, tekintve, hogy

S

a definíciójából adódóan egész szám. Megmutatjuk, hogy

n \geq 2

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

\begin{matrix} ⌈ \frac{1}{2} n (k + 1) ⌉ . \end{matrix}

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

\begin{matrix} \frac{n}{2} i + \frac{n}{2} (k + 1 - i) = \frac{1}{2} n (k + 1) \end{matrix}

lesz. Ha

n

páratlan (és

n \geq 3

), 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

\frac{1}{2} (n - 3) (k + 1)

lesz. Ahhoz tehát, hogy minden oszlopban az összeg legfeljebb

\begin{matrix} ⌈ \frac{1}{2} n (k + 1) ⌉ \end{matrix}

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

\begin{matrix} ⌈ \frac{1}{2} n (k + 1) ⌉ - \frac{1}{2} (n - 3) (k + 1) = ⌈ \frac{1}{2} n (k + 1) - \frac{1}{2} (n - 3) (k + 1) ⌉ = ⌈ \frac{3}{2} (k + 1) ⌉ \end{matrix}

legyen. Ez pedig éppen azt jelenti, hogy az utolsó

3

sorba egy a feladatban leírt

3 \times k

méretű táblázatot kell elhelyeznünk. A továbbiakban tehát az

n = 3

esetre szorítkozunk.
Ha

k = 2 m + 1

páratlan, azaz

S = \frac{3 (k + 1)}{2} = 3 (m + 1)

, akkor az alábbi módon kitöltött táblázat megfelel a célnak:

\begin{matrix} \begin{matrix} 1 & 2 & ... & i & ... & m + 1 & m + 2 & ... & j & ... & 2 m + 1 \\ 2 m + 1 & 2 m - 1 & ... & 2 m + 3 - 2 i & ... & 1 & 2 m & ... & 4 m + 4 - 2 j & ... & 2 \\ m + 1 & m + 2 & ... & m + i & ... & 2 m + 1 & 1 & ... & j - m - 1 & ... & m \end{matrix} \end{matrix}

Ha pedig

k = 2 m

páros szám és

\begin{matrix} S = ⌈ \frac{3 (k + 1)}{2} ⌉ = ⌈ \frac{6 m + 3}{2} ⌉ = 3 m + 2, \end{matrix}

akkor például az alábbi módon tölthetjük ki a

3 \times k

méretű táblázatot:

\begin{matrix} \begin{matrix} 1 & 2 & ... & i & ... & m & m + 1 & ... & j & ... & 2 m \\ 2 m & 2 m - 2 & ... & 2 m + 2 - 2 i & ... & 2 & 2 m - 1 & ... & 4 m + 1 - 2 j & ... & 1 \\ m + 1 & m + 2 & ... & m + i & ... & 2 m & 1 & ... & j - m & ... & m \end{matrix} \end{matrix}

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,

H_{1}

és

H_{2}

uniójára úgy, hogy sem

a

, sem

b

nem írható fel sem két

H_{1}

-beli, sem két

H_{2}

-beli szám különbségeként.

Megoldás. Tekintsük az

1,1 + a,1 + 2 a,1 + 3 a, ...,

illetve az

1,1 + b,1 + 2 b, 1 + 3 b, ...

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

H_{1}

és

H_{2}

halmazok közül ugyanabban. Más szóval mindkét sorozat felváltva tartalmaz

H_{1}

és

H_{2}

-beli elemeket. Azt kaptuk tehát, hogy az

1 + k a

é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

a

, illetve

b

kanonikus alakjában a

2

prímtényező kitevője, azaz

a = 2^{n} a'

és

b = 2^{m} b'

, ahol

a'

, illetve

b'

páratlan számok. Az általánosság megszorítása nélkül feltehetjük, hogy

n \geq m

teljesül. Tekintsük az

x : = 1 + 2^{n} a' b'

számot. Mivel

x = 1 + b' a

ugyanabban a halmazban van, mint

x = 1 + a' 2^{n - m} b

, a fenti megfigyelésünkből az adódik, hogy

b'

és

a' 2^{n - m}

paritása megegyezik, vagyis

a' 2^{n - 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

\begin{matrix} H_{1} & : = {k \in Z : k > 0 és ⌊ \frac{k}{2^{n}} ⌋ páratlan}, illetve \\ H_{2} & : = {k \in Z : k > 0 és ⌊ \frac{k}{2^{n}} ⌋ páros} . \end{matrix}

²

Ez a választás megfelelő, hiszen ha

x - y = a

, akkor

x = y + a

, tehát

\begin{matrix} ⌊ \frac{x}{2^{n}} ⌋ = ⌊ \frac{y + a}{2^{n}} ⌋ = ⌊ \frac{y}{2^{n}} + \frac{a}{2^{n}} ⌋ = ⌊ \frac{y}{2^{n}} + a' ⌋ = ⌊ \frac{y}{2^{n}} ⌋ + a' . \end{matrix}

Mivel

a'

páratlan, ez azt jelenti, hogy

x

és

y

egyike

H_{1}

-beli, a másik pedig

H_{2}

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:

\begin{matrix} x - y = b \Rightarrow x = y + b \Rightarrow ⌊ \frac{x}{2^{n}} ⌋ = ⌊ \frac{y + b}{2^{n}} ⌋ = ⌊ \frac{y}{2^{n}} + \frac{b}{2^{n}} ⌋ = ⌊ \frac{y}{2^{n}} + b' ⌋ = ⌊ \frac{y}{2^{n}} ⌋ + b' . \end{matrix}

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

2^{n}

szerinti maradékosztályok elemeit ,,felváltva'' tesszük

H_{1}

-be és

H_{2}

-be.
2. Ha a

H_{1}

-ben, illetve

H_{2}

-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 (

H_{1}

H_{2}

és

H_{3}

) 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

H_{i}

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

H_{1}

H_{2}

és

H_{3}

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;

(i i)

f (z)

racionális szám minden

z

egész szám esetén;

(i i i)

f (x) < c < f (y)

és

c

racionális, akkor

f

felveszi a

c

értéket; és

(i v)

x

y

z

egészek és összegük nulla, akkor

\begin{matrix} f (x) + f (y) + f (z) = f (x) f (y) f (z) \end{matrix}

teljesül.

Megoldás. Vegyük észre, hogy az

f \equiv 0

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

(i v)

feltételből

x = y = z = 0

helyettesítéssel adódik, hogy

3 f (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

(i i)

-nek, így

f (0) = 0

. Ezek után

y = - x

és

z = 0

helyettesítéssel

(i v)

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 = - 2 x

helyettesítéssel

(i v)

-ből azt kapjuk, hogy

2 f (x) - f (2 x) = - f {(x)}^{2} f (2 x)

, azaz

\begin{matrix} 2 f (x) = f (2 x) (1 - f {(x)}^{2}) . \end{matrix}

(1)

Tegyük fel tehát, hogy

f ≢ 0

, azaz van olyan

x

egész, amire

f (x) \neq 0

. Ekkor (1) bal oldala nemnulla, így a jobb oldal sem lehet zérus, tehát

| f (x) | \neq 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

(i i i)

miatt

| f (n) | < 1

teljesül minden

n

egészre. Ha tehát

0 < | f (x) | < 1

, akkor (1) miatt

\begin{matrix} | f (2 x) | = | \frac{2 f (x)}{1 - f {(x)}^{2}} | = \frac{| 2 f (x) |}{| 1 - f {(x)}^{2} |} > \frac{2 | f (x) |}{1} = 2 | f (x) | \end{matrix}

adódik, azaz

| f (2^{n} x) | > 2^{n} | f (x) |

, ha

n > 1

egész. Legyen

n

olyan pozitív egész, amire

2^{n} > \frac{1}{| f (x) |}

teljesül. Ekkor

\begin{matrix} | f (2^{n} x) | > 2^{n} | f (x) | > \frac{1}{| f (x) |} | f (x) | = 1, \end{matrix}

márpedig ez ellentmond a fenti megfigyelésnek, ami szerint

| f | < 1

. Tehát

f \equiv 0

az egyedüli olyan függvény, ami teljesíti az

(i)

‐

(i v)

feltételeket.

□

Megjegyzés. Többen észrevették, hogy a feladat

(i v)

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

(i v)

tulajdonság, akkor

α : = arcctg (f (1))

választással tetszőleges

n

pozitív egészre

f (n) = tg (n \cdot α)

adódik. Mivel

tg (\pm \frac{π}{2})

nem értelmes, azért

n \cdot α = \pm \frac{π}{2} + 2 k π

semmilyen egész

n

k

esetén sem teljesülhet, így olyan egész

m

sem létezik, amire

tg (m α) = \pm 1

áll. A

(i i i)

feltétel miatt ekkor

| f | < 1

, márpedig ha

tg (α) \neq 0

, akkor az

α

alkalmas többszörösének tangense

1

-nél nagyobb abszolút értékű lesz.

⌈ x ⌉

x

szám felső egész része; a legkisebb egész szám, amely nem kisebb

x

-nél.

²Egy $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.