Az A. 516. feladat (2010. október)

A. 516. A B₁, B₂, B₃, B₄, B₅ dobozok mindegyikében kezdetben egy érme van. Kétféle megengedett lépés van:

1. típusú lépés: Választunk egy B_j nemüres dobozt, ahol 1 $\le$ j $\le$ 4. Elveszünk egy érmét a B_j dobozból, és hozzáadunk két érmét a B_j+1 dobozhoz.

2. típusú lépés: Választunk egy B_k nemüres dobozt, ahol 1 $\le$ k $\le$ 3. Elveszünk egy érmét a B_k dobozból, és kicseréljük a B_k+1 (esetleg üres) doboz tartalmát a B_k+2 (esetleg üres) doboz tartalmával.

Bizonyítsuk be, hogy tetszőleges 0 $\le$ n $\le$ 2²⁰¹⁰ egész szám esetén ilyen lépések valamilyen véges sorozata segítségével elérhető, hogy a B₁, B₂, B₃, B₄ dobozok mindegyike üres legyen, a B₅ doboz pedig pontosan n érmét tartalmazzon.

(5 pont)

A beküldési határidő 2010. november 10-én LEJÁRT.

Megoldás (Ágoston Tamás megoldása). Jelöljük a néhány (k db) szomszédos dobozban lévő érmék eloszlását a következőképpen. Ha az első dobozban a₁, a másodikban a₂, a harmadikban a₃, stb. érme van, akkor ezt a helyzetet jelölje [a₁,a₂,a₃,...,a_k].

Ekkor az 1. típusú lépéssel valamely két szomszédos doboz [a,b] állásából [a-1,b+2] érjük el, ha a>0. A 2. típusú lépés pedig a>0 esetén [a,b,c]-ből [a-1,c,b]-t készít. Ezekből összetettebb lépéseket hozunk létre.

Az A típusú lépés legyen az, hogy valamely [a,b] helyzetből kiindulva az 1. típusú lépést alkalmazzuk a-szor; így a [0,2a+b] álláshoz jutunk.

A B típusú lépés legyen az, hogy egy [a,b,c] helyzetben, ahol a>0, a második és a harmadik dobozra egy A típusú lépést, majd a három dobozra egy 2. típusú lépést alkalmazunk. Ezzel a [a-1,2b+c,0] állást érjük el.

A C típusú lépés az legyen, hogy ha van egy [a,0,0] állás, ahol a>0, és k $\le$ a pozitív egész, akkor először az első két dobozra egy 1. típusú lépést majd (k-1)-szer a B típusú lépést alkalmazzuk:

[a,0,0] $\to$ [a-1,2,0] $\to$ [a-2,4,0] $\to$ [a-3,8,0] $\to$ ... $\to$ [a-k,2^k,0].

Végül a D típusú lépés legyen az, amikor egy [a,b,b] állásból k db 2. típusú lépés alkalmazásával erre a három dobozra az [a-k,b,b] álláshoz jutunk (k $\ge$ 0).

Most már hozzákezdhetünk a kért állások létrehozásának. Először alkalmazzuk kiinduló 5 dobozunkra az 1., 1., 1., B, B, 1., 2., C, 2. lépéseket:

[1,1,1,1,1] $\to$ [1,0,3,1,1] $\to$ [1,0,3,0,3] $\to$ [1,0,2,2,3] $\to$ [1,0,1,7,0] $\to$ [1,0,0,14,0] $\to$

$\to$ [0,2,0,14,0] $\to$ [0,1,14,0,0] $\to$ [0,1,0,2¹⁴,0] $\to$ [0,0,2¹⁴,0,0].

Innen kezdve csak az utolsó 3 dobozzal foglalkozunk, mindig csak azoknak az állását írjuk föl.

Most a egy (2¹⁴-3)-nál nem nagyobb pozitív egész szám. Ekkor egy D típusú lépéssel elérhető az [a+1,0,0] állás, ahonnan pedig egy C típusú lépéssel az [1,2^a,0] állás. Hasonlóképpen egy D és egy C típusú lépéssel megvalósítható a [2¹⁴,0,0] $\to$ [a+2,0,0] $\to$ [2,2^a,0] és a [2¹⁴,0,0] $\to$ [a+3,0,0] $\to$ [3,2^a,0] átalakítás is.

Az így kapott állásokból akarunk most továbblépni. Ha van egy [1,2^a,0] állás, akkor ebből k db 1. típusú lépéssel elérhető az [1,2^a-k,2k] állás, ahonnan pedig egy 2. és egy A típusú lépéssel elérhető a [0,2k,2^a-k], majd a [0,0,2^a+3k] állás tetsztőleges 0 $\le$ k $\le$ 2^a egész számra.

A [2,2^a,0] állásból egy 1. típusú lépéssel kaphatjuk [1,2^a+2,0]-t, és innen már az előző esethez hasonlóan elérhető a [0,0,2^a+2+3k] állás minden 0 $\le$ k $\le$ 2^a+2 egészre. Hasonlóképpen [3,2^a,0]-ból 2 db 1. típusú lépéssel kapjuk az [1,2^a+4,0] állást, és innen már minden 0 $\le$ k $\le$ 2^a+4 egészre elérhető [0,0,2^a+4+3k].

Ez azt jelenti, hogy elérhető minden olyan állás, ahol az első négy doboz üres, és az utolsóban a 2^a,2^a+3,2^a+6,...,2^a+2, vagy a 2^a+2,2^a+5,2^a+8,...,2^a+2+8, vagy a 2^a+4,2^a+7,2^a+10,...,2^a+2+16 számok valamelyike van. Ezek a sorozatok együttesen az összes 2^a+2 és 2^a+2+2 közötti egész számot tartalmazzák. És mivel ez az eljárás minden 1 $\le$ a $\le$ 2¹⁴-3 egész számra elvégezhető, ezért az utolsó dobozban lévő érmék száma tetszőleges 2+2=4 és 2^2¹⁴-1+2 közötti egész számnak választható, miközben a többi doboz üres. Az előbbi eljárásunk ezen kívül még a 2¹=2-t is előállította az utolsó dobozban, így (mert 2^2¹⁴-1+2>2²⁰¹⁰) már csak a 0, 1 és 3 van hátra.

A 0 elérhető, ha a [0,0,2¹⁴,0,0] állásra egy D típusú lépést alkalmazunk, k=2¹⁴ helyettesítéssel. Az 1 az alábbi átalakítások során érhető el:

[1,1,1,1,1] $\to$ [1,1,0,3,1] $\to$ [1,0,3,0,1] $\to$ [0,3,0,0,1] $\to$ [0,0,0,0,1].

(Itt a lépések típusa rendre: 1., 2., 2., D.) A 3-at pedig az alábbi módon érhetjük el:

[1,1,1,1,1] $\to$ [0,1,1,1,1] $\to$ [0,0,1,1,1] $\to$ [0,0,0,1,1] $\to$ [0,0,0,0,3].

(Itt a lépések típusa rendre: 2., 2., 2., 1.)

Tehát a [0,0,0,0,n] állás bármely 0 $\le$ n $\le$ 2^2¹⁴-1+2 egész számra elérhető. Ezzel a feladat állítását bizonyítottuk.

Statisztika:

13 dolgozat érkezett.

5 pontot kapott: Ágoston Tamás, Backhausz Tibor, Damásdi Gábor, Frankl Nóra, Janzer Olivér, Mester Márton, Nagy 235 János, Nagy 648 Donát, Strenner Péter, Viharos Andor, Weisz Ágoston.

4 pontot kapott: Kiss 902 Melinda Flóra.

0 pontot kapott: 1 versenyző.

A KöMaL 2010. októberi matematika feladatai

13 dolgozat érkezett.
5 pontot kapott:	Ágoston Tamás, Backhausz Tibor, Damásdi Gábor, Frankl Nóra, Janzer Olivér, Mester Márton, Nagy 235 János, Nagy 648 Donát, Strenner Péter, Viharos Andor, Weisz Ágoston.
4 pontot kapott:	Kiss 902 Melinda Flóra.
0 pontot kapott:	1 versenyző.

Már regisztráltál?
Új vendég vagy?