Állapotfüggvény (invariáns, monovariáns stb.) összeállította Surányi László

„Állapotfüggvény” (invariáns, monovariáns stb.) összeállította Surányi László

I) Olyan feladatok, ahol az állapotfüggvény állandó, ezért tudhatjuk egy eljárás végeredményét, vagy alkalmatlanságát adott végeredmény elérésére. A) BEVEZETŐ FELADATOK Nagyon egyszerű, „alapozó” feladatok. Itt még (magunktól) nem mondunk semmit állapotfüggvényről, invarianciáról stb. A 7-8. évfolyamra gondolunk. Főleg oszthatóság, és csak a legegyszerűbb állapotfüggvények: a – b, a + b jönnek elő. Itt tehát a diáktól nem várjuk el, hogy szabatosan megadjon egy állapotfüggvényt. Egyszerű oszthatóság A1. Vágó Alfréd 24 papírdarab közül néhányat tíz részre vágott, majd megint néhányat tíz részre vágott. Ezt folytatja. Egy ilyen munkaszakasz után valaki összesen 1978 papírdarabot számolt össze. Rábíznánk-e a bevásárlást? A2. Lehetséges-e, hogy az előbbi módon eljárva Vágó Alfréd egy papírdarabból indulva pontosan a) 201, b) 200, c) 199 papírdarabot állít elő? A3. Vágó Alfréd egy papírdarabot négy részre tép, majd az egyik darabot öt részre tépi. Ezután felváltva tép négy, ill. öt részre egy-egy papírdarabot. Kaphat-e így 1997 fecnit valamikor? És ha csak annyit tudunk, hogy minden lépésben négy vagy öt részre tép? A4. Az asztalon fekszik egy papírlap. Ezt tíz vagy tizenhat részre téphetjük, majd a kapott részek bármelyikét szintén tíz vagy tizenhat részre vághatjuk. Ilyen lépések egymás utáni alkalmazásával elérhetjük-e, hogy pontosan a) 400, b) 399, c) 22 darab papír legyen az asztalon? Általános megjegyzés: alapjában az invariancia-elvet, állapotfüggvényt stb. akarjuk tanítani. De azért jobban „modellezi” a valódi matematikai gondolkodásmódot, ha nem „sterilen” tanítjuk, hanem azt is láttatjuk, hogy „egészen közel” hozzá más jellegű feladatok is vannak. Tehát nem erőltetjük sem azt, hogy csak állapotfüggvényes feladatok legyenek, sem azt, hogy a diákok ne mondhassanak más jellegű megoldást egy-egy feladatra, amelyet mi állapotfüggvényes feladatnak szánunk. Erre később is lesznek példák. A5. Egy sárkánynak 2006 feje van, a vitéz egy kardcsapással 1, 17, 21 vagy 33 fejet vág le, miközben a sárkánynak rendre 10, 14, 0, 48 feje nő ki helyettük. El tudja- e távolítani a vitéz a sárkánynak minden fejét véges számú kardcsapással? A6. Két kupacban gyufák vannak. Egy-egy alkalommal valamelyik kupacból elveszünk néhány szálat, s a másik kupacba kétszer annyit helyezünk. Elérhető-e, hogy mindkét kupacban ugyanannyi gyufaszál legyen, ha kezdetben az egyes kupacokban a) 7 és 34, b) 1 és 3 gyufa van? A7. Az asztalon egy kupacban 1001 kavics van. Egy lépésben kiválaszthatunk egy kupacot, amelyben legalább három kavics van és egyet kidobunk közülük, a maradékot pedig két kupacra bontjuk. Eljuthatunk-e így olyan helyzethez, amikor minden kupacban pontosan három kavics van? A8. Annának 11, Balázsnak 7 üveggolyója van. Ha az egyikük vesz valahány új üveggolyót magának, a másik háromszor annyit vesz. Elképzelhető-e, hogy néhány ilyen vásárlás után mindkettőjüknek 50 üveggolyója lesz? A9. A 8x8-as sakktáblán letakartunk két szemközti sarokmezőt (pl. az A1 és a H8-as mezőt). Lefedhető-e a többi mező átfedés nélkül 2x1-es dominókkal? B) AZ ÁLLAPOTFÜGGVÉNY BEVEZETÉSE A korábbi a – b állapotfüggvényt folytatja az alábbi néhány feladat. Ezek során már kimondjuk (ha a diákok eddig nem mondták ki), hogy a – b maradéka nem változik. A végére bevezethetjük az állapotfüggvény fogalmát. Lényegében három különböző feladatot látok alkalmasnak erre. Az egyik a B1 és B2-vel előkészített B2’, a másik a B6, a harmadik a B5. Úgy érdemes csinálni, hogy ezeket – valamilyen nekünk kézre jövő sorrendben – sorra vesszük és valahol tárgyalásuk közben megemlítjük az

„állapotfüggvény” szót. Tapasztalatom szerint a diákok egy idő után rájönnek, milyen kényelmes kifejezési mód és örömmel használják. Definiálnunk nem kell (nem is volna célra vezető), de arra ügyelnünk kell, hogy egyre inkább pontosan mondják meg, milyen állapotfüggvényre gondolnak, még ha nem is formalizálják. És persze mindeközben már a II. részt is előkészítjük! B1. Egy asztal körül hatan ülnek, közülük kettő előtt egy-egy tányér van. A többiek előtt nincs tányér. A két „tányéros” ember között egy ember ül. Egy lépésben két szomszédos személy elé egy-egy újabb tányért helyezünk. Elérhető-e néhány lépéssel, hogy mindenki előtt ugyanannyi tányér legyen? B2. Egy asztal körül hatan ülnek, egyikük előtt van mind a hat tányér. Egy lépésben bárki, aki előtt legalább két tányér van, megfog kettőt és odaadja egyik szomszédjának, vagy mindkét szomszédjának ad egyet. Elérhető-e így, hogy egy idő után mindegyikük előtt legyen tányér? B2’. Körben áll n fa, mindegyiken egy-egy mókus ül. Egy lépés: két mókus átugrik egy-egy az övével szomszédos fára. Elérhető-e, hogy minden mókus ugyanazon a fán gyűljön össze? Később jönnek még ennek a feladatnak más változatai (lásd a B7-es AD feladatot). Egyelőre pár gyakorló feladat jön az invarianciára. B3. Egy táblára felírtuk az 1,2,3, …, 2014, 2015 számokat. Egy lépésben letörölhetünk két számot és a helyükre a különbségüket írjuk. Ezt mindaddig folytatjuk, amíg egy szám marad. Lehet-e az utoljára maradt szám a 0? B4. (B3 folytatása.) Most a letörölt két szám helyére a különbségük a) 18-es maradékát, b) 17-es maradékát írjuk. Lehet-e most az utoljára maradó szám a 0? Milyen szám maradhat utoljára? B4’. Most a letörölt két szám helyére az összegük 17-es maradékát írjuk. Mi lehet az utoljára maradt szám? B5. Egy táblára 6 db nullát, 7 db egyest és 8 db kettest írunk. Egy lépésben két különböző számot letöröltünk, és a helyükre a harmadikat írtuk. A lépéseket úgy hajtottuk végre, hogy a végén csak egy szám maradt. Mi lehet ez a szám és mi nem lehet? B5’. Elképzelhető-e, hogy az előző eljárásunk a) sohasem ér véget? b) úgy ér véget, hogy több azonos szám marad a táblán? B5’’. BBH hogy mindig elérhető, hogy a fenti eljárással csak egyetlen szám – esetleg több példányban – maradjon a táblán. B5’’’. Választhatók-e úgy az a, b és c pozitív egészek, hogy a db nullát, b db egyest és c db kettest írva a táblára, az eljárásunkat nem tudjuk úgy végrehajtani, hogy a végén csak egyetlen szám maradjon a táblán? B6. Egy kocka csúcsaiba számokat írtunk. Egy lépés abból áll, hogy egy élének két végpontjában álló két szám mindegyikét eggyel növeljük. Azt akarjuk elérni, hogy minden csúcsban ugyanaz a szám álljon. Lehetséges-e ez, ha a kiinduló helyzetben a) az egyik él két végpontjában egyes, a többiben nulla áll? b) az egyik testátló két csúcsában egyes, a többiben nulla áll? c) egy csúcsban egyes, a többiben nulla áll? d) az egyik lapátló két csúcsában egyes, a többiben nulla áll? Megjegyzés: A c) és d) feladatot érdemes bonyolultabb páros gráfra is feladni. B7. Egy négyzet négy csúcsába gyufákat helyezünk. Kezdetben az egyik csúcsán van egyetlen gyufa, a többin egy sincs. Egy lépésben elvehetünk egy csúcsról néhány gyufát és az egyik szomszédos csúcsba kell tennünk kétszer annyit. Elérhetőe ilyen lépések sorozatával, hogy a csúcsoknál – valamilyen körüljárási irányban – rendre 1,9,8,9 szál gyufa legyen? (AD döntő, 1989) Megjegyzés: 1. 1989-ben ez még döntős feladatnak számított, ma már „közkincs”, csakúgy, mint a D6’ „törpés” feladat. 2. Esetleg érdemes bonyolultabb (páros) gráfon is feladni.

B8. Visszatérünk az A9-es feladathoz. Mi a helyzet, ha a 8x8-as sakktáblán letakarunk egy sarokmezőt, és a többit 3x1-es dominókkal akarjuk lefedni? És mi a helyzet általában, NxN-es, b) NxM-es „sakktáblán”? B9. Felírtuk a táblára a 2, √2, 1/√2 számokat. A táblán szereplő számok közül bármely kettőt letörölhetjük, ha a helyükre az összegük, illetve a különbségük 1/√2-szeresét írjuk. Elérhető-e ilyen cserékkel, hogy a táblán az 1, √2, 1+√2 számok álljanak? B10. a) Egy szigeten 13 szürke, 15 barna és 17 zöld kaméleon él. Ha két különböző színű kaméleon találkozik, akkor mindketten annyira megijednek, hogy a harmadik színűre változnak. Két azonos színű kaméleon nem ijed meg egymástól, így nem is változtatnak színt, ha találkoznak. Lehetséges-e, hogy egy idő után minden kaméleon ugyanolyan színű lesz? b) Mi a helyzet, ha kezdetben 13 szürke, 25 barna és 17 zöld kaméleon él a szigeten? B10’. a) Lehetséges-e az előző feladat b) esetében, hogy minden kaméleon barna/zöld lesz a végén? b) Milyen kiindulás esetén lehetséges, hogy végül minden kaméleon zöld/barna/szürke legyen? D5. (idevaló!!!!) Van egy n × n -es táblázatunk, és sakktábla-szerűen kiszíneztük fekete és fehér mezőkre. Egy lépésben egy 2 × 2-es négyzet minden mezőjét átszínezhetjük az ellentétes színre. Milyen n-re lehet elérni, hogy az összes mező egyszínű legyen? (A feladatot a „kis” Lovász Laci hozta egy matektáborba.) B11. Négyzetek mindkét irányban végtelen szalagján néhány (véges sok) négyzetre köveket helyeztünk. Ha van olyan négyzet, amelyen legalább két kő van, akkor közülük egyet-egyet áttolunk a következő, illetve az előző négyzetre. Visszajuthatunk-e a kiindulási állapothoz véges sok lépés után? B12. (Kvant) Az 1, 0, 1, 0, 1, 0, 3, 5, … sorozatban a hetedik tagtól kezdve mindegyik egyenlő az előző hat összegének utolsó jegyével. BBH ebben a sorozatban nem léphet föl közvetlenül egymás utáni tagokként a 0, 1, 0, 1, 0, 1 részsorozat. B13. Legyen p egy 1 főegyhós, n > 1 fokú polinom. Tekintsük a grafikonját és azokat az x tengellyel párhuzamos egyeneseket, amelyeknek n metszéspontjuk van a grafikonnal. Tekintsük minden ilyen egyenesen a metszéspontok súlypontját. BBH ezek egy egyenesen vannak. B13’. Az előző feladaton most annyit változtatunk, hogy n > 3 és az egyenes tetszőleges irányú lehet, csak legyen továbbra is n metszéspontja p grafikonjával. Igaz-e most is az állítás? B14. Tekintsük a p(x) = xn + pxn-1 + qxn-2 +… n-edfokú polinomot (n > 1) és legyen valamely a valós számra p(x + a) = xn + Pxn-1 + Qxn-2 +…. BBH (n – 1)p2 – 2nq = (n – 1)P2 – 2nQ. B14’. Mi a geometriai jelentése a fenti kifejezésnek n = 3 esetén? Általában is érdekes kérdés, hogy milyen kifejezések invariánsak az y illetve az x tengely eltolására. A másodfokú (1 főegyütthatós) polinom esetében ilyen kifejezés a diszkrimáns, ami éppen a két gyök különbségének a négyzete. A harmadfokú polinom esetét a B14’ feladatban tárgyaltuk. A negyedfokú polinom esetében is van egy érdekes, geometriailag is értelmezhető invariáns. Erről szól a következő feladat, amelyet az 1980-as – az olimpiát „kiváltó” finn versenyen adtak fel (lásd Reiman István: Nemzetközi matematikai diákolimpiák 1959-1994, Typotex, 1998, 508-510): B15. Tekintsünk egy 1 főegyütthatós negyedfokú függvényt. Egy, az x tengellyel párhuzamos egyenest jó egyenesnek nevezünk, ha a függvény grafikonját négy pontban metszik. Legyen e négy metszéspont balról jobbra sorra A, B, C és D. Az egyenest trianguláris egyenesnek nevezzük, ha az AB, AC és AD szakaszokból mint oldalhosszakból szerkeszthető háromszög. BBH vagy minden jó egyenes trianguláris, vagy egy sem. C) PERMUTÁCIÓK: INVERZIÓK SZÁMA A permutációk párossága is egy invariáns, amit érdemes bevezetni. Erről Hegedüs Pál anyagában részletesen van szó, itt csak azt jelzem, hogyan épülhet be az invariánsok tanításába. A megoldásokat is ott lehet elolvasni. A permutációk párosságának bevezetésére a következő két feladat lehet alkalmas (bár az első nem invariánsos):

C1. Egy osztály tanulói ábécé sorrendben állnak. Minden lépésben kiválasztunk két tanulót és azok helyet cserélnek. Elérhető-e így, hogy végül nagyság szerinti sorrendben álljanak? C2. Egy osztály tanulói ábécé sorrendben állnak. Minden lépésben kiválasztunk két tanulópárt és mindkét pár helyet cserél. Elérhető-e így minden esetben, hogy végül nagyság szerinti sorrendben álljanak? Indíthatunk ezzel a feladattal is: C3. Felírtuk az 1, 2, 3, . . . , n számokat egymás után. Egy lépésben kiválaszthatunk két számot és egymás helyére írhatjuk őket. Visszakaphatjuk-e 2007 ilyen cserével, az eredeti sorrendet? Hegedüs Pálnál szerepelt C4. A 4x4-es “tologatós játék”. IIA) Az állapotfüggvény bizonyítja, hogy az eljárás véget ér, vagy adja meg a végeredményt D1. Egy csodálatos fán 25 alma és 30 körte van. Egy-egy alkalommal két gyümölcsöt szedhetünk le: ha egyformákat szedtünk le, akkor egy körte, ha különbözőket, akkor egy alma nő helyettük. Összesen hány gyümölcsöt tudunk leszedni a fáról? Utolsónak milyen gyümölcs marad? D2. Egy vázában 75 fehér és 150 fekete babszem van. A váza mellett van egy halom fekete babszem. Találomra kiveszünk két babszemet a vázából. Ha legalább az egyik fekete, akkor azt kitesszük a halomba, a másikat visszadobjuk a vázába, akár fekete volt, akár fehér. Ha mindkét babszem fehér, eldobjuk őket és a halomból egy fekete babszemet dobunk a vázába. Mi a valószínűsége annak, hogy a vázában utoljára maradó babszem fehér? Hányszor ismételhetjük meg az eljárást? Ugyanez másik megfogalmazásban: D3. Egy zsákban n fehér és n barna babszem van. A következő eljárást alkalmazzuk ismételten. Kiveszünk két babszemet, ha mindkettő fehér, akkor visszateszünk helyette egy barnát. Ha valamelyik barna, akkor a másikat visszatesszük (ha mindkettő barna, akkor az egyiket visszatesszük). Addig folytatjuk, amíg a zsákban egyetlen babszem marad. Milyen színű az utoljára maradó babszem? D4. Van egy kétkarú mérlegünk és 101 darab mérősúlyunk, melyek össztömege 200gr. Minden mérősúly gr-ban kifejezett tömege egész szám. A súlyokat csökkenő sorrendben rakjuk a mérlegre, és mindig abba a serpenyőbe helyezzük, ahol kisebb a már felrakott súlyok össztömege. BBH az összes mérősúly felhelyezése után a mérleg egyensúlyban lesz. D5-öt l. korábban. D6. Adott néhány piros és kék pont a síkon, néhány közülük össze van kötve szakasszal. Egy pontos speciálisnak nevezünk, ha a vele összekötött pontoknak több, mint a fele más színű. Választunk egy speciális pontot (ha van ilyen) és másik színűre festjük. BBH néhány ilyen lépés végrehajtása után nem lesz több speciális pont. Ugyanez az 1990-es a haladó AD döntőben így hangzott: D6’. Az erdőben 12 törpe él piros vagy kék házikóban. Minden év i-edik hónapjában az i-edik törpe felkeresi összes barátját, hogy eldöntse, átfesse-e a házát. Akkor és csak akkor fogja átfesteni (pirosról kékre vagy fordítva), ha a barátai többsége más színű házban lakik, mint ő. Bizonyítsuk be, hogy néhány év után már senki nem festi át házikóját. (A barátságok kölcsönösek és az évek során nem változnak.) D6’’. Igaz-e, hogy az előző feladatban a házikók végső színe egyértelműen meghatározott? D7. Véges sok feketére festett négyzet van egy fehér, végtelen négyzetrácsos papíron. A t = 1,2,3, … időpillanatokban minden egyes négyzet azt a színt veszi fel, amelyik többségben van a rajta, a felső és a jobb oldali szomszédján levő színek közül. BBH egy idő után nem lesz fekete négyzet. D8. Egy konkáv sokszöggel a következő műveletet végezhetjük. Ha A és B két nem szomszédos csúcs, és a sokszög teljes egészében az AB egyenes egyik oldalán fekszik, akkor egyik A és B közé eső részét tükrözzük az AB szakasz felezőpontjára. BBH e művelet bizonyos számú alkalmazása után a sokszög konvex lesz. D9. BBH a 0,1,1,2,… kezdetű Fibonacci-sorozatban minden n-re van olyan szám, amely n darab nullára és utána egy egyesre végződik (és az n darab nulla előtt van pozitív számjegy).

D10. (Stanford Putnam training 2007) Egy n x n-es sakktábla n2 kis négyzetéből n − 1 fertőzött. Minden pillanatban megfertőződik minden olyan négyzet, amelynek legalább két szomszédja fertőzött. BBH van legalább egy négyzet, ami nem fertőződik meg. IIB) Állapotfüggvény a megoldhatóság bizonyítására: A) NAGYON EGYSZERŰ, BEVEZETŐ FELADATOK E1. 2n általános helyzetű pont a síkon, van olyan egyenes, amelynek mindkét oldalán ugyanannyi van. E1’. Ugyanez, de adott még egy pont, amin át kell mennie az egyenesnek. E2. 2n + 1 pont a síkon, nincs három egy egyenesen és nincs négy egy körön. BBH van olyan kör, amelynek határán 3 adott pont van, és belsejében, külsejében ugyanannyi. Ne féljünk a folytonosságtól (szemléletes alapon nyugodtan használhatjuk): E3. Adott egy konvex, korlátos S alakzat a síkon és rajta kívül egy P pont. BBH húzható P-n keresztül olyan egyenes, amely felezi S területét (kerületét). E4. Adott egy konvex, korlátos S alakzat a síkon. BBH van olyan egyenes, amely felezi a területét is, a kerületét is. Még mindig ezzel az ötlettel (folytonosság nélkül) megy a „törött vonalas feladat” is: E5. Adott n pont a síkon, mindig van önmagát nem metsző törött vonal, amelynek pontosan e pontok a csúcsai. E6. BBH egy sík bármely 2n pontja tekinthető n diszjunkt (nem metsző) szakasz végpontjainak. E7. Adott n piros és n kék pont a síkon, semelyik három nem esik egy egyenesbe. BBH húzhatunk n diszjunkt szakaszt, amelyek mindegyike különböző színű pontok a végpontjai. E8. Adott a síkon n általános helyzetű pont (semelyik három nem esik egy egyenesbe), továbbá n egyenes, amelyek között nincsenek párhuzamosak. BBH húzhatunk merőlegest minden pontból egy-egy egyeneshez merőlegest úgy, hogy ne legyen két olyan merőleges, amely metszi egymást. B) KAPCSOLAT A „VEGYÜK A LEGNAGYOBBAT, A LEGKISEBBET, A SZÉLSŐT” GONDOLATTAL. E9. Adott egy n pontú egyszerű gráf, minden pont foka legfeljebb 11. BBH a pontok négy színnel színezhetők úgy, hogy legfeljebb n él lesz „egyszínű”. Hogyan általánosítható a feladat? E10. Adott n egyenes a síkon, bármely kettő metszi egymást, de nem megy át mind egy ponton. BBH, hogy van olyan pont a síkon, amelyre pontosan két adott egyenes illeszkedik. E11. Ha k > 2 és egy egyszerű gráfban minden pont foka legalább k, akkor van legalább k+1 hosszú kör. E12. Egy egyszerű gráfban van kör, akkor van olyan kör, amely egy pontot és annak összes szomszédját tartalmazza. E13. Dirac-tétel. Artúr király behívatott 2n lovagot az udvarába. Minden lovagnak legfeljebb n – 1 ellensége van a megjelent lovagok között. BBH a) bármely két ellenséges lovagnak van közös barátja (a gráf 2-átmérőjű); b) az előző állítás még 2n – 1 lovag esetén is igaz, de kevesebb lovag mellett már nem igaz; c) Merlin leültetheti úgy a lovagokat a Kerekasztalhoz, hogy ellenségek ne üljenek egymás mellett. Az ellenségesség kölcsönös és akik nem ellenségek, azok barátok. C) ISMERT BIZONYÍTÁSOK E14. Hol használjuk az állapotfüggvényt már ismert bizonyításokban? D) TOVÁBBI FELADATOK: E15. Nevezzük az x természetes szám utódjának azt a számot, amelyet a következő utasítás alapján kapunk belőle: ha 0-ra vagy 4-re végződik, letöröljük az utolsó jegyét. Minden más esetben megszorozzuk kettővel. A szám leszármazottja az utódja és minden leszármazott utódja. BBH a 4-es szám minden természetes számnak leszármazottja. (KöMaL Gy. 1433., Kvant ill. német versenyfeladat nyomán.)

Folytonossághoz jó az alábbi régi PVK feladat a KöMaL-ból: E16. Korlátos konvex alakzat köré írható érintőnégyszög ( = amelynek mind a négy oldala támaszegyenes). ?E17. Egy tanterem asztalán egy mérleg áll, serpenyőiben súlyok. Kezdetben a jobb oldali serpenyő a nehezebb. A súlyok közt nincs két egyenlő. Mindegyik súlyon néhány (legalább egy) tanuló neve áll. Amikor valaki belép a terembe, az ő nevét tartalmazó súly(oka)t – ha van egyáltalán ilyen – átteszi a mérleg másik serpenyőjébe. Igazoljuk, hogy be lehet küldeni valahány tanulót egymás után úgy, hogy végül a bal oldali serpenyő legyen a nehezebb. (KöMaL feladat volt.) Az alábbi feladat 1986/3 olimpiai feladat volt (lásd az idézett Reiman-könyvet, 395-6.). E18. Egy szabályos ötszög mindegyik csúcspontjához oly módon rendeltünk egy-egy egész számot, hogy ennek az öt számnak az összege pozitív legyen. Ha e közül az öt pont közül három egymás után következőt rendre X, Y, Z jelöli, a hozzájuk rendelt számokat x,y,z, és y<0, akkor e számok helyébe rendre x+y, -y, z+y írandó. Ezt mindaddig ismételjük, amíg van negatív szám valamelyik csúcson. Befejeződik-e az eljárás minden esetben véges sok lépésben? IIIB) Lépésszám becslésre használjuk az állapotfüggvényt: D6’’’. a) BBH a D6’ feladatban elképzelhető, hogy egy él többször is oka lesz átfestésnek. b) BBH (ennek ellenére) legfeljebb annyi lépés lesz, amennyi a törpék közötti barátságok (élek) száma. Lépésnek csak azt tekintjük, amikor egy törpe ténylegesen átfesti a házikóját. Mutassunk példát, ahol kevesebb lépés nem elég. F1. A 0 számból kiindulva két művelet megengedett: a) egyet adunk a számhoz, b) megszorozzuk kettővel. Legalább hány ilyen művelet kell, hogy eljussunk 10-hez, 11-hez, … n-hez? F2. n pingpong versenyző között egyértelmű erősorrendet feltételezünk (ha a megveri b-t és b megveri c-t, akkor a c-t is megveri). Ki akarjuk választani a legjobbat. Hány mérkőzést kell ehhez lejátszani? F2’. (Nehéz) n versenyző közül akarjuk a legjobbat és a leggyengébbet kiválasztani (egyértelmű erősorrend, tehát nincs körbeverés). Legalább 1,5n – 2 mérkőzés kell. F3. Adott egy véges gráf, amelyben minden pont foka legfeljebb a + b + 1, a és b pozitív egész. A pontjai szétvágandók két részre úgy, hogy az egyik részen belül minden fokszám legfeljebb a legyen, a másikon belül minden fokszám legfeljebb b legyen. A bamba algoritmus: Kezdetben minden pont az első halmazban van, a második halmaz üres. Egy lépés: keresünk egy pontot az első halmazban, amelynek ottani fokszáma nagyobb a-nál, vagy a másodikban, amelynek ottani fokszáma nagyobb b-nél. Ha ilyen nincs, kész vagyunk. Ha találunk ilyet, áttesszük a másik halmazba. Az eljárás tényleg bamba. Egy pontot „megjavít”, de akár az összes új szomszédját is elronthatja. Tehát még az sem világos, hogy az algoritmus véget ér. Két feladat: 1. BBH az algoritmus véget ér. 2. Adjunk becslést a szükséges lépésszámra. FÜGGELÉK Néhány nehezebb feladat angolul, megoldás nélkül – egy olimpiai előkészítő táborból: (IMO training camp, 1999) Recall the scenario of Sample Problem 1. Prove that any sequence of moves will lead to a position in which no further moves can be made, and moreover that this position is independent of the sequence of moves. Hint: Invariants are good for showing that any sequence of moves must terminate. Consider other techniques for uniqueness. (IMO 2000, #3) Let n ≥ 2 be a positive integer and λ be a positive real number. Initially, there are n fleas on a horizontal line, not all at the same point. We define a move as choosing two fleas, at some points A and B, with A to the left of B, and letting the flea from A jump to the point C to the right of B such that BC/AB = λ. Determine all values of λ such that, for any point M on the line and any initial position of the n fleas, there exists a sequence of moves that will take them all to positions right of M. Hint: If λ < 1/(n−1), there exists a constant C > 0 so that (n − 1 + C)λ = 1. Can you come up with an invariant depending on C? Plusz még egy:

(KöMaL, EGMO) Három urnában golyók vannak. Egy lépésben kiválasztunk két urnát, és ha az egyikben y, másikban x a golyók száma, továbbá y nem kisebb x-nél, akkor belőle x golyót áttehetünk a másikba (így a két uránban most y – x, ill. 2x a golyók száma). BBH véges sok lépésben egy urna kiüríthető.