Levelezős csapatverseny – 1. feladatsor – megoldások

IX. feladat – 8 pont

– Megérkeztünk. Az évszám 2060 – mondta a Mágus.
– Furcsa, azt gondoltam, hogy minden teljesen megváltozik, az emberek repülő autókkal járnak. Ehelyett sétálókat és biciklizőket látok – lepődött meg Jancsi.
– Az emberiség idővel rájött, hogy nem jó, ha minden fejlesztés az egyén életét teszi kényelmesebbé – az emberek ugyanis végletesen ellustultak. De hogy válaszoljak a kérdésére, nézzünk be egy múzeumba.

A múzeumba belépve Jancsi megpillantott egy érdekes táblát:

„A 2008-as gazdasági válság megrázta a fejlett világot, azt követően ugyanis évekig nem tudott helyreállni a hitelezés és a gazdasági növekedés. Azonban, hogy visszahozzák és biztosítsák a piacok pénzbőségét 2015-ben brit közgazdászok megalkották a Pénzkiadó Automatát. Ennek működési elve röviden a következő:

Vásárolva a boltban egy új Pénzkiadó Automatát kapunk hozzá egy érmét. Ezt bedobva az automata végtelen sok érmét dob ki (a természetes számokkal megszámozva). A továbbiakban a kiadott érmék közül bármelyik érmét bedobva ismét végtelen sok érmét kapunk és így tovább. Az automata minden kiadott érmére két természetes számot ír rá: az egyik azt jelöli, hogy hányadik bedobás után esett ki az adott érme, a másik pedig, hogy a kidobott érmék közül hányadikként.

Múzeumunk őrzi néhány példányát az így gyártott érméknek.

Sajnálatos azonban, hogy a világgazdaság állapota nem javult a Pénzkiadó Automaták bevezetése után sem. A kapzsi tulajdonosok ugyanis nem elégedtek meg egyszeri használattal – egyre többször dobálták be érméiket illetve igyekeztek ezt minél gyorsabban tenni és automatizálni. Megalkották a pénzbedobó robotokat, melyek tetszőlegesen kis idő alatt képesek voltak bedobni egy érmét.
Nagy meglepetésükre azonban miután a robotok minden n természetes számra bedobták az n-edik érmét, az összes pénznek nyoma veszett. A vitrin jobboldalán látható a TIME magazin 2016 októberi különszáma, melynek címe ’Where is the money’?...”

– Mágus, ezt nem értem. Bedobva egy pénzérmét végtelen sok érmét ad ki a gép. Hogy lehet, hogy mégis elfogy az összes pénz? – hitetlenkedett János.
– A lényeges különbség abban van, hogy a robotok, mivel egyre kevesebb idő alatt dobták be a pénzt, véges idő alatt végtelen sokszor tudtak újra bedobni – válaszolta a Mágus.

IX. Hogyan lehetséges ez? Mi lehetett a robotok programja, amely ezt eredményezte?

Megoldás: Minden érméhez társítsunk egy természetes (m,n) számpárt a szerint, hogy hanyadik lépésben hullt ki (m), illetve abban a lépsében hanyadik érme volt (n) (lásd a feladatban megadott képen). A kezdetben kapott érméhez tartozzon a (0,0) pár.

Legyen a robot programja az, hogy a nála lévő érmék közül mindig azt az érmét dobja be, melyre az m+n összeg minimális, ha több ilyen is van, akkor azt, amelyre m a legkisebb.

Belátjuk, hogy ekkor a játék végére nem marad érme nála.
Indirekt. Tegyük fel, hogy mégis marad valamennyi. Ezek mindegyikéhez tartozik számpár. A megmaradt érmék közül válasszuk ki azokat, melyekre az m+n minimális, ezek közül pedig azt, melyre az első szám az. Legyen az ehhez tartozó pár (m',n').
Legyen A azon (m,n) érmék halmaza, hogy m+n<m'+n' vagy m+n=m'+n' és m<m'. Ekkor A nyilván véges és (m',n') választása miatt minden A-beli érme be lett dobva. Akkor tekintsük azt a lépést, melyben az utolsó A-beli érmét bedobta a robot. A következő lépésben valamely (m'',n'') érmét dobott be, amelyre m''+n''<m'+n' vagy m''+n''=m'+n' és m''<m', hiszen nem (m',n')-t dobta be. De akkor (m'',n'') is A-beli volna. Ez ellentmond a feltételezésünknek, ami azt jelenti, hogy minden érmét bedob a robot előbb-vagy utóbb.

– Á, kezdem kapizsgálni. Hát igen, az emberiségnek még sokat kell tanulni a hibáiból – sóhajtott Jancsi. – Menjünk inkább haza. Egy kicsit elfáradtam.
Pár pillanat múlva már az Euklideszi téren voltak megint, a nap épp úgy sütött a sárguló levelekre, mint először.
– Kedves János! Örültem, hogy Önnel utazhattam, térben és időben.
– Köszönöm, sok tapasztalatot szereztem. Mágus, milyen nap van ma?
– Vasárnap van, az a bizonyos, amelyiken először találkoztunk. Naivitás lett volna azt hinni, hogy nem tudom, hogy nincs iskolai szünet – nevetett a Mágus – remélem, még találkozunk!

A Mágus a következő pillanatban már nem volt ott. János egyedül találta magát az Euklideszi téren, amely most a szokásosnál is sokkal tágasabbnak tűnt. Egy keveset várt még, majd hazafelé vette az irányt.

A verseny kereteit a TÁMOP - 4.2.2/B-10/1-2010-0030
„Önálló lépések a tudomány területén” pályázat biztosította.