Kezdőlap


Feladat:	F.2670	Korcsoport: 18-	Nehézségi fok: átlagos
Füzet:	1988/október, 303 - 305. oldal		PDF \| MathML
Témakör(ök):	Valós számok és tulajdonságaik, Páros gráfok, Indirekt bizonyítási mód, Feladat
Hivatkozás(ok):	Feladatok: 1988/január: F.2670

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.

A szóban forgó számok közül nevezzük $a$ -t és $b$ -t egymás ismerőseinek, ha található számaik között olyan

\begin{matrix} a = c_{0}, c_{1}, c_{2}, ..., c_{n - 1}, c_{n} = b, \end{matrix}

hogy

\begin{matrix} ∣ c_{0} - c_{1} ∣ = 3^{k_{1}}, ∣ c_{1} - c_{2} ∣ = 3^{k_{2}}, ..., ∣ c_{n - 1} - c_{n} ∣ = 3^{k_{n}}, \end{matrix}

ahol

k_{1}, k_{2}, ..., k_{n}

egész számok. A

(c_{0}, c_{1}, c_{2}, ..., c_{n})

számok között lehetnek egyenlők is. Az ismerős

a

b

számokat (egymáshoz) barátságosnak, ill. ellenségesnek fogjuk hívni aszerint, hogy a fenti

n

páros vagy pedig páratlan. (Speciálisan, ha

∣ a - b ∣

3^{k}

alakú, akkor

a

és

b

ellenséges.) Igen könnyen látható, hogy ekkor érvényesek a következő szabályok:
(1) Ha

a

és

b

ismerősök, és

b

és

c

is ismerősök, akkor

a

és

c

ugyancsak ismerősök.
(2) Ha

a

és

b

barátságos, továbbá

a

és

c

is barátságos, akkor

b

és

c

is barátságos.
(3) Ha

a

és

b

ellenséges, valamint

a

és

c

is ellenséges, akkor

b

és

c

barátságos.
Korántsem ennyire nyilvánvaló az alábbi állítás:
(4) Ha

a

és

b

barátságos, akkor nem lehet ellenséges.
Tételezzük fel ugyanis, hogy

a

és

b

barátságos és ugyanakkor ellenséges is. Ez azt jelenti, hogy a megadott számok közül kiválasztható

c_{1}, c_{2}, ..., c_{2 m - 1}

és

d_{1}, d_{2}, ..., d_{2 t}

úgy, hogy

\begin{matrix} ∣ a - c_{1} ∣ = 3^{k_{1}}, ∣ c_{1} - c_{2} ∣ = 3^{k_{2}}, ..., ∣ c_{2 m - 1} - b ∣ = 3^{k_{2 m}}, \\ ∣ a - d_{1} ∣ = 3^{l_{1}}, ∣ d_{1} - d_{2} ∣ = 3^{l_{2}}, ..., ∣ d_{2 t} - b ∣ = 3^{l_{2 t + 1}} \end{matrix}

(alkalmas

k_{i}

l_{j}

egészekkel). Ekkor azonban

\begin{matrix} ∣ a - c_{1} ∣ = s_{1} \cdot 3^{k_{1}}, ..., ∣ c_{2 m - 1} - b ∣ = s_{2 m} \cdot 3^{k_{2 m}}, \\ ∣ d_{1} - a ∣ = f_{1} \cdot 3^{l_{1}}, ..., ∣ d_{2 t} - b ∣ = f_{2 t + 1} \cdot 3^{l_{2 t + 1}}, \end{matrix}

ahol

s_{i}

f_{j}

mindegyike

1

vagy

(- 1)

. A fenti egyenlőségeket összeadva

\begin{matrix} 0 = \sum_{i = 1}^{2 m} s_{i} \cdot 3^{k_{i}} + \sum_{j = 1}^{2 t + 1} f_{j} \cdot 3^{l_{j}} \end{matrix}

(5)

adódik. Jelölje

M

k_{i}

l_{j}

egészek abszolút értékének maximumát. Az (5) összefüggés mindkét oldalát

3^{M}

-nel megszorozva azt kapjuk, hogy

\begin{matrix} 0 = \sum_{i = 1}^{2 m} s_{i} \cdot 3^{k_{i} + M} + \sum_{j = 1}^{2 t + 1} f_{j} \cdot 3^{l_{j} + M} . \end{matrix}

(6)

Mivel itt

k_{i} + M

l_{j} + M ≧ 0

, ezért a (6)-ban szereplő összegek minden tagja páratlan egész szám. A tagok száma,

2 n + 2 t + 1

azonban szintén páratlan, így az összeg nem lehet páros (tehát

0

sem); ez ellentmondás, amivel (4)-et igazoltuk.
Ahhoz, hogy számainkat a kívánt módon két csoportra oszthassuk, előbb osztályokba soroljuk őket a következőképpen. Válasszunk ki közülük tetszőlegesen egy

a_{1}

számot, és soroljuk az első osztályba

a_{1}

-et és

a_{1}

ismerőseit. Ha ezeken kívül marad még szám, akkor ezek közül válasszunk egy

a_{2}

-t, és soroljuk a második osztályba

a_{2}

-t és

a_{2}

ismerőseit. Az eljárást folytatva végül valamennyi számot besorolhatjuk

r

osztály valamelyikébe, ahol az osztályok rendre

a_{1}, a_{2}, ..., a_{r}

-ből és ezek ismerőseiből állnak. Különböző osztályokba tartozó számok különbsége sohasem

3^{k}

alakú; ha ugyanis

a

i

-edik,

b

pedig a

j

-edik osztályban van, és

∣ a - b ∣ = 3^{k}

(i \neq j

k

egész), akkor

a

és

b

ismerősök. Azonban

a_{i}

és

a

, valamint

b

és

a_{j}

is ismerősök, ezért (1) miatt

a_{i}

és

a_{j}

szintén ismerősök, ami lehetetlen.
Elegendő tehát az azonos osztályba tartozó számokat a kívánt módon két csoportra osztani. A

p

-edik osztály esetében alkossa az első csoportot

a_{p}

és az

a_{p}

-vel barátságos számok, míg a második csoportba az

a_{p}

-vel ellenséges számokat soroljuk. (2) szerint bármely két (különböző), az első csoportba tartozó szám barátságos, és (3) szerint ugyanez mondható a második csoport bármely két számáról is. (4) miatt tehát azonos csoportban levő számok nem lehetnek ellenségesek, így különbségük biztosan nem

3^{k}

alakú.

Megjegyzések. 1. A feladat állítása

3^{k}

helyett

a^{k}

-ra is igaz, tetszőleges páratlan

a

-val. A közölt bizonyítás némi módosításával belátható továbbá, hogy nemcsak véges sok, hanem akárhány (pl. az összes!) valós szám is két csoportra osztható a kívánt módon.
2. Tekintsük azt a gráfot, amelynek csúcsai a feladatban szereplő valós számok, és két csúcsot akkor köt össze él, ha a megfelelő számok különbsége

3^{k}

alakú. A feladat szerint ekkor a kapott gráf páros. Ismeretes, hogy egy gráf akkor és csak akkor páros, ha minden körében páros sok él van. A fenti bizonyítás során is tulajdonképpen azt mutattuk meg, hogy ebben a gráfban nincs páratlan sok élből álló kör (l. (4)), majd ennek felhasználásával igazoltuk a gráf párosságát.