Kezdőlap


Feladat:	2010. évi Nemzetközi Matematika Diákolimpia 22. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Dankovics Attila
Füzet:	2010/október, 391 - 392. oldal		PDF \| MathML
Témakör(ök):	Kombinatorika, Teljes indukció módszere
Hivatkozás(ok):	Feladatok: 2010/szeptember: 2010. évi Nemzetközi Matematika Diákolimpia 22. 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.

Dankovics Attila megoldása. Vezessük be a következő jelöléseket.
Kapcsos zárójelbe tett rendezett számhatosok jelölik az állásokat: ${1; 1; 1; 1; 1; 1}$ az alapállás (az első pár üreset elhagyva: ${0; 0; 0; 1; 1; 1} = {1; 1; 1}$ ).
Zárójelbe tett rendezett számpárok jelölik a lépéseket: például $(1; 2)$ azt jelenti, hogy az első dobozból egy 2. típusú lépést hajtottunk végre. Végül jelölje például $n \cdot (k; 1)$ azt, hogy a $(k; 1)$ lépést $n$ -szer végezzük el.
Legyen $v = 2010^{2010^{2010}}$ .

1. Lemma. Az

{a; b; c; x; 0; 0}

állásból elérhető az

{a; b; c; 0; 2^{x}; 0}

állás.

Bizonyítás. Teljes indukció

x

szerint:

x = 1

-re

(4; 1)

lépés után elértük az állást.
Indukciós lépés:

{a; b; c; 0; 2^{x - 1}; 0}

az indukciós feltevés szerint elérhető. Ez után

2^{x - 1}

-szer az

(5; 1)

, majd a

(4; 2)

lépéseket végrehajtva elértük a kívánt állást.
Hajtsuk végre egymás után a következő lépéseket:

{1; 1; 1; 1; 1; 1}

-re

(1; 1)

;

(2; 1)

;

(3; 1)

;

(4; 1)

;

(5; 1)

, az így kapott

{0; 2; 2; 2; 2; 3}

-re

2 \cdot (5; 1)

;

(4; 2)

;

7 \cdot (5; 1)

;

(3; 2)

, majd

{0; 2; 1; 14; 0; 0}

-re az 1. Lemma szerint létező lépéssorozattal kapott

{0; 2; 1; 0; 2^{14}; 0}

-re

(3; 2)

;

(2; 2)

;

(2; 1)

;

2 \cdot (3; 1)

adja

{0; 0; 2^{14}; 4; 0; 0}

-t, amire az 1. Lemma eljárását és (3;2)-t felváltva ismételgetve 2

^{14}

-szer a

{0; 0; 0; {\underset{︸}{2^{2^{2^{\cdot^{\cdot^{\cdot^{2^{2}}}}}}}}}_{2^{14} + 2 db}^{}; 0; 0}

álláshoz jutunk.
Legyen a

B_{4}

dobozban lévő érmék aktuális száma mindig

h

. Megjegyzendő, hogy

h

paritása tetszőlegesre beállítható (szükség esetén a

(4; 2)

lépés alkalmazásával); ezt később fogom kihasználni.
Az előbbi helyzetből a

3 \cdot ((4; 1); 2 \cdot (5; 1))

átalakítás után a

{h; 0; 12}

állást kapjuk. Jelölje a

B_{6}

-ban lévő érmék számát mindig

y

(mely jelenleg 3-mal osztható, lévén 12). Legyen végül a

B_{5}

-ben lévő érmék száma

x

.
Ekkor a

(4; 2)

;

x \cdot (5; 1)

lépéssorozat

y

értékét duplázza és

h

értékét 1-gyel csökkenti (ezután

h

még pozitív marad, mert

h > v

; továbbá

y

3-mal osztható marad; továbbá

h

paritása tetszőleges marad). Duplázzuk

y

-t míg

2 y \leq v < 4 y

teljesül. Legyen az ekkor aktuális

y

értéke

c

. A

(4; 2)

lépés után ismételjük az

(5; 1)

lépést addig, amíg

x + 2 y = v

nem teljesül (előbb-utóbb teljesülni fog, mert

x + 2 y

minden lépésben 3-mal nő, így

c

és

4 c

között minden 3-mal osztható értéket felvesz, és

v

is ilyen). Ezt követően a

(4; 2)

;

x \cdot (5; 1)

lépéssorozat után a

{h; 0; v}

állást kapjuk. Ez az állás tetszőleges paritású

h

-val elérhető, legyen

h

páros. Ekkor

h \cdot (4; 2)

után az állás:

{0; 0; 0; 0; 0; v}

, ami megegyezik az elérendő állással.
Tehát a kérdéses állás elérhető.