Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem A. 516. (October 2010)

A. 516. In each of five boxes B1, B2, B3, B4, B5 there is initially one coin. There are two types of operation allowed:

Type 1: Choose a nonempty box Bj with 1\lej\le4. Remove one coin from Bj and add two coins to Bj+1.

Type 2: Choose a nonempty box Bk with 1\lek\le3. Remove one coin from Bk and exchange the contents of (possibly empty) boxes Bk+1 and Bk+2.

Prove that for every integer 0\len\le22010 there is a finite sequence of such operations that results in boxes B1, B2, B3, B4 being empty and box B5 containing exactly n coins.

(5 pont)

Deadline expired on November 10, 2010.


Sorry, the solution is available only in Hungarian. Google translation

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 a1, a másodikban a2, a harmadikban a3, stb. érme van, akkor ezt a helyzetet jelölje [a1,a2,a3,...,ak].

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\lea 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,2k,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\ge0).

 

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,214,0]\to[0,0,214,0,0].

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

Most a egy (214-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,2a,0] állás. Hasonlóképpen egy D és egy C típusú lépéssel megvalósítható a [214,0,0]\to[a+2,0,0]\to[2,2a,0] és a [214,0,0]\to[a+3,0,0]\to[3,2a,0] átalakítás is.

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

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

Ez azt jelenti, hogy elérhető minden olyan állás, ahol az első négy doboz üres, és az utolsóban a 2a,2a+3,2a+6,...,2a+2, vagy a 2a+2,2a+5,2a+8,...,2a+2+8, vagy a 2a+4,2a+7,2a+10,...,2a+2+16 számok valamelyike van. Ezek a sorozatok együttesen az összes 2a+2 és 2a+2+2 közötti egész számot tartalmazzák. És mivel ez az eljárás minden 1\lea\le214-3 egész számra elvégezhető, ezért az utolsó dobozban lévő érmék száma tetszőleges 2+2=4 és 2214-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 21=2-t is előállította az utolsó dobozban, így (mert 2214-1+2>22010) már csak a 0, 1 és 3 van hátra.

A 0 elérhető, ha a [0,0,214,0,0] állásra egy D típusú lépést alkalmazunk, k=214 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\len\le2214-1+2 egész számra elérhető. Ezzel a feladat állítását bizonyítottuk.


Statistics:

13 students sent a solution.
5 points:Á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 points:Kiss 902 Melinda Flóra.
0 point:1 student.

Problems in Mathematics of KöMaL, October 2010