Kezdőlap


Feladat:	2001. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Kiss Demeter , Kocsis Albert Tihamér
Füzet:	2002/február, 69 - 72. oldal		PDF \| MathML
Témakör(ök):	Binomiális együtthatók, Számhalmazok, Részhalmazok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 2002/február: 2001. évi Kürschák matematikaverseny 2. feladata

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.

I. Megoldás. Tegyük fel, hogy az állítás nem igaz, vagyis az $a_{i} + b_{i}$ , $a_{i} + c_{i}$ , $b_{i} + c_{i}$ számok között legfeljebb $k$ különböző szám található, ezek halmazát jelölje $T$ . Világos, hogy minden $1 \leq i \leq n$ esetén az $a_{i} + b_{i}$ , $a_{i} + c_{i}$ , $b_{i} + c_{i}$ számok páronként különbözők, vagyis $T$ -nek egy 3-elemű részhalmazát alkotják. Továbbá, ha $a_{i} + b_{i} = x$ , $a_{i} + c_{i} = y$ és $b_{i} + c_{i} = z$ , akkor $a_{i} = (x + y - z) / 2$ , $b_{i} = (x + z - y) / 2$ és $c_{i} = (y + z - x) / 2$ . Az ${x, y, z}$ halmaz ismeretében az ${a_{i}, b_{i}, c_{i}}$ halmaz tehát egyértelműen meghatározható. Minthogy

\begin{matrix} (\binom{| T |}{3}) \leq (\binom{k}{3}) < n, \end{matrix}

léteznek

1 \leq i < j \leq n

indexek úgy, hogy

{a_{i}, b_{i}, c_{i}} = {a_{j}, b_{j}, c_{j}}

, ami azonban lehetetlen.
A második állítás bizonyításához tekintsük a

T = {t_{1}, t_{2}, ..., t_{k}}

halmazt, ahol

t_{i} = 4^{i}

. Legyen

n = (\binom{k}{3})

, és jelölje

T_{1}, T_{2}, ..., T_{n}

T

halmaz 3-elemű részhalmazait. Ha

T_{i} = {4^{u}, 4^{v}, 4^{w}}

, ahol

1 \leq u < v < w \leq k

egész számok, akkor legyen

a_{i} = (4^{u} + 4^{v} - 4^{w}) / 2

b_{i} = (4^{u} + 4^{w} - 4^{v}) / 2

és

c_{i} = (4^{v} + 4^{w} - 4^{u}) / 2

, ekkor nyilván

a_{i} + b_{i}, a_{i} + c_{i}, b_{i} + c_{i} \in T

. Ezért elegendő megmutatni, hogy az

a_{i}, b_{i}, c_{i}

(

1 \leq i \leq n

) számok mind különbözők.

a_{i} = b_{j}

vagy

a_{i} = c_{j}

semmilyen

i, j

esetén nem állhat fenn, hiszen az

a_{i}

számok mind negatívak, míg a

b_{j}

c_{j}

számok mind pozitívak. Az sem lehet, hogy

b_{i} = c_{j}

, hiszen a

b_{i}

számok mindegyike valamelyik

(2^{2 s - 2}, 2^{2 s - 1})

alakú intervallumba esik, míg a

c_{i}

számok mindegyike valamelyik

(2^{2 s - 1}, 2^{2 s})

alakú intervallumba esik, ahol

3 \leq s \leq k

egész szám.
Legyen most

T_{i} = {4^{u}, 4^{v}, 4^{w}}

és

T_{j} = {4^{x}, 4^{y}, 4^{z}}

, ahol

1 \leq u < v < w \leq k

és

1 \leq x < y < z \leq k

egész számok. Tegyük fel, hogy

c_{i} = c_{j}

, ekkor

\begin{matrix} 4^{v} + 4^{w} - 4^{u} = 4^{y} + 4^{z} - 4^{x} . \end{matrix}

Mivel

4^{w} < 4^{v} + 4^{w} - 4^{u} < 4^{w + 1}

és

4^{z} < 4^{y} + 4^{z} - 4^{x} < 4^{z + 1}

, ez csak úgy lehet, ha

w = z

, következésképpen

4^{v} - 4^{u} = 4^{y} - 4^{x}

. Itt

4^{v - 1} < 4^{v} - 4^{u} < 4^{v}

és

4^{y - 1} < 4^{y} - 4^{x} < 4^{y}

, ezért az egyenlőség csak úgy állhat fenn, ha

v = y

, és ekkor szükségképpen

u = x

i = j

is igaz. A

c_{i}

számok tehát mind különbözők.
Ugyanilyen gondolatmenettel megállapíthatjuk azt is, hogy mind az

a_{i}

számok, mind a

b_{i}

számok különbözők, amivel a bizonyítás végére értünk.

II. Megoldás. A feladat első részére mutatunk egy másik indoklást, ez Kiss Demetertől származik. Tegyük fel ismét, hogy az állítással ellentétben a

3 n

összeg között legfeljebb

k

különböző szám található. Ekkor ezek közül valamelyik, jelöljük ezt

a

-val, legalább

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

alkalommal fordul elő. Ha valamilyen

i

-re az

a_{i} + b_{i}

b_{i} + c_{i}

és

a_{i} + c_{i}

összegek közül kettő is egyenlő lenne

a

-val, akkor az

a_{i}

b_{i}

c_{i}

számok között lenne két megegyező. Az általánosság megszorítása nélkül feltehetjük tehát, hogy minden

1 \leq i \leq (\binom{k - 1}{2}) + 1

esetén az

a_{i} + b_{i}

b_{i} + c_{i}

és

a_{i} + c_{i}

összegek közül pontosan egy lesz

a

-val egyenlő. Az ezen összegek közül fennmaradó

2 ((\binom{k - 1}{2}) + 1)

összeg most már csak

k - 1

különböző értéket vehet fel, van tehát egy olyan érték, jelöljük ezt

b

-vel, amely legalább

\begin{matrix} 2 ((\binom{k - 1}{2}) + 1) / (k - 1) > k - 2 \end{matrix}

alkalommal fordul elő. Az előző okoskodáshoz hasonlóan tehát feltehetjük, hogy minden

1 \leq i \leq k - 1

esetén az

a_{i} + b_{i}

b_{i} + c_{i}

és

a_{i} + c_{i}

összegek közül az egyik

a

-val, egy másik pedig

b

-vel egyenlő. A még megmaradó

k - 1

összeg pedig már csak legfeljebb

k - 2

különböző értéket vehet fel, lesz tehát köztük kettő, amelyik megegyezik. Ekkor azonban az ezekhez tartozó

a_{i}

b_{i}

c_{i}

számhármasok is megegyeznek, mely ellentmondás bizonyítja az állítást.

A továbbiakban a feladat második részére mutatunk több megoldást.

III. Megoldás. Tekintsük a

T = {t_{1}, t_{2}, ..., t_{k}}

halmazt, ahol

t_{i} = 3^{i}

. Legyen

{x, y, z}

és

{u, v, w}

{1,2, ... k}

halmaz két 3-elemű részhalmaza. Az I. megoldáshoz hasonlóan, annyit kell csak megmutatnunk, hogy ha

\begin{matrix} \frac{3^{x} + 3^{y} - 3^{z}}{2} = \frac{3^{u} + 3^{v} - 3^{w}}{2}, \end{matrix}

akkor a két részhalmaz szükségképpen megegyezik, és

z = w

. Valóban, ekkor

3^{x} + 3^{y} + 3^{w} = 3^{u} + 3^{v} + 3^{z} = A

. Ha az

A

számot hármas számrendszerben írjuk fel, akkor annak 0-tól különböző számjegyei között vagy három 1-es, vagy egy 1-es és egy 2-es számjegy szerepel, hiszen

x = y = w

nem lehetséges. A felírás egyértelműsége miatt az első esetben

{x, y, w}

és

{u, v, z}

{1,2, ... k}

halmaznak ugyanaz a 3-elemű részhalmaza. Mivel

x, y \neq z

, ebből

w = z

, majd

{x, y} = {u, v}

is következik, ahogyan azt bizonyítani kívántuk. A második esetben azt kapnánk, hogy

{x, y, w}

és

{u, v, z}

{1,2, ... k}

halmaznak ugyanaz a 2-elemű részhalmaza. Mivel

x \neq y

, ez meg kellene egyezzen az

{x, y}

halmazzal, ahonnan

z \in {x, y}

következne, ami nem lehetséges.

IV. Megoldás. Ahogyan azt az eddigi megoldások is sugallják, elegendő azt megmutatni, hogy minden

k

pozitív egész esetén létezik egy olyan

T_{k} = {t_{1}, t_{2}, ..., t_{k}}

halmaz, melyre

t_{x} + t_{y} + t_{z} = t_{u} + t_{v} + t_{w}

akkor és csak akkor teljesül, ha az

x

y

z

számok valamilyen sorrendben megegyeznek az

u

v

w

számokkal. Valóban, ekkor nem nehéz megmutatni, hogy a

(t_{x} + t_{y} - t_{z}) / 2

alakban felírható

3 (\binom{k}{3})

szám (ahol

{x, y, z}

{1,2, ... k}

halmaz tetszőleges 3-elemű részhalmaza) mind különböző.
Ha

k = 1

akkor a

t_{1} = 1

választás nyilván megfelelő. Elegendő megmutatni azt, hogy létezik olyan végtelen

t_{1}, t_{2}, ..., t_{i}, ...

sorozat, hogy minden

i \geq 2

esetén

t_{i}

nem írható fel

r_{1} t_{1} + ... + r_{i - 1} t_{i - 1}

alakban, ahol

r_{1}, ... r_{i - 1}

racionális számok. Tegyük fel ugyanis, hogy létezik ilyen sorozat, tekintsük a

T_{k}

halmazt, és tegyük fel, hogy

t_{x} + t_{y} + t_{z} = t_{u} + t_{v} + t_{w}

teljesül valamilyen

1 \leq x, y, z, u, v, w \leq k

esetén. Legyen

i

x

y

z

u

v

w

indexek között előforduló legnagyobb szám. Ha most

t_{i}

nem ugyanannyiszor szerepelne az egyenlőség két oldalán, akkor átrendezés után egy

t_{i} = r_{1} t_{1} + ... + r_{i - 1} t_{i - 1}

alakú egyenlőséghez jutnánk. Ezért

i

ugyanannyiszor szerepel az

x

y

z

számok között, mint az

u

v

w

számok között. Mindkét oldalról elhagyva a

t_{i}

-vel egyenlő tagokat, és az előbbi lépést megismételve végül azt kapjuk, hogy az

x

y

z

számok valamilyen sorrendben valóban megegyeznek az

u

v

w

számokkal.
Tegyük fel tehát, hogy

k > 1

, és a

t_{1}, ..., t_{k - 1}

számokat már meghatároztuk a fenti kívánalomnak megfelelően. Ekkor az

r_{1} t_{1} + ... + r_{k - 1} t_{k - 1}

alakban felírható számok halmaza megszámlálhatóan végtelen, míg az összes valós szám halmaza nem az, létezik tehát olyan

t_{k}

valós szám, mely nem írható fel

r_{1} t_{1} + ... + r_{k - 1} t_{k - 1}

alakban. Ezért a kívánt tulajdonságú sorozat létezése azonnal következik a teljes indukció elvéből.

Megjegyzések. 1. Az előző megoldásban nem konstruktív módon igazoltuk egy alkalmas

t_{1}, t_{2}, ..., t_{i}, ...

sorozat létezését. Megmutatható, hogy például a

t_{i} = \sqrt[]{p_{i}}

választással, ahol

p_{i}

i

-edik pozitív prímszámot jelöli, megfelelő sorozathoz jutunk. Ennek bizonyítása azonban már túl messzire vezetne.

2. Ahogyan azt Kocsis Albert Tihamér észrevette, a feladat átalánosítható a következő módon. Legyenek

k \geq t \geq 3

egész számok,

n > (\binom{k}{t})

. Ha

a_{i 1}, a_{i 2}, ..., a_{i t}

(

1 \leq i \leq n

)

t n

különböző valós szám, akkor a

\sum_{i = 1}^{t} a_{i} - a_{k}

(

1 \leq i \leq n

1 \leq k \leq t

) számok között legalább

k + 1

különböző szám található,

n = (\binom{k}{t})

esetén pedig ez nem mindig van így. Ennek igazolását az olvasó könnyen elvégezheti, nincsen szükség hozzá alapvetően új gondolatra.

3. Merőben más a helyzet, ha kéttagú összegeknél maradunk. Világos, hogy ha

k \geq 3

egész szám,

n > (\binom{k}{3})

, és

a_{i}

b_{i}

c_{i}

d_{i}

(

1 \leq i \leq n

)

4 n

különböző valós szám, akkor az

a_{i} + b_{i}

a_{i} + c_{i}

a_{i} + d_{i}

b_{i} + c_{i}

b_{i} + d_{i}

c_{i} + d_{i}

összegek között legalább

k + 1

különböző szám található. Meglepő módon ez az állítás lényegesen nem javítható. Érdemes elgondolkozni a következő feladaton: minden

k \geq 3

egész számra létezik

4 (\binom{k}{3})

különböző valós szám,

a_{i}

b_{i}

c_{i}

d_{i}

(1 \leq i \leq (\binom{k}{3}))

úgy, hogy az

a_{i} + b_{i}

a_{i} + c_{i}

a_{i} + d_{i}

b_{i} + c_{i}

b_{i} + d_{i}

c_{i} + d_{i}

összegek között legfeljebb

2 k

különböző szám található.