Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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