Matematikai játékok Svetoslav Bilchev, Emiliya Velikova 1. rész –Matematikai tréfák A következő matematikai játékokban – matematikai tréfákban a végső eredmény a játék kiindulási feltételeitől függ, és nem a játékosok stratégiáitól. 1.1. Feladat. Legyen m pont adott a síkon! Két játékos egymásután összeköt bármely két még összekötetlen pontot egy ívvel úgy, hogy ez az ív egyetlen korábbi ívet se metsszen el. Az a játékos nyer, aki behúzza az utolsó ívet. Megoldás. Ha m = 2 , akkor a kezdő játékos a nyerő. Legyen m > 2 . Ebben az esetben a következőt fogjuk felhasználni: Euler-tétele. Legyen m pont adott a síkon és n darab egymást nem metsző ív, amelyek mind valamely két pontot kötik össze, de nem haladnak át a visszamaradó m − 2 ponton. Legyen az így megadott sík l részre osztva. Ha bármely pontból lehetséges eljutni bármely másik pontba a megadott ívek mentén, akkor következik, hogy m − n + l = 2 . A játék végén ( m > 2 ) egy olyan “térképet” kapunk, amelyen bármely két pont ívekből álló lánccal van összekötve. A térkép minden része 3 ívvel van határolva, azaz 2n = 3l . Eulertétele alapján következik, hogy az n szám, az ívek száma egy ilyen térképen a következővel egyenlő: 3 m − 2 . De az ívek száma egy ilyen térképen megegyezik a lépések számával a játékban. Így, ha m egy páratlan (páros) szám és m > 2 , akkor az első (második) játékos a nyerő.
(
)
2. Rész SZIMMETRIA Itt olyan matematikai játékokat fogunk megnézni, ahol a nyerő játékos alapvetően a szimmetria ötletét használja fel. 2.1. Feladat. Egy kupacban 1992 darab kő van. Két játékos vesz részt a következő játékban: egy lépésben mindkettejük csak olyan számú követ vehet el, ami osztója az előző játékos által elvett kövek számának. A kezdő játékos első lépésben bármennyi követ elvehet, de nem az összeset. Az a játékos nyer, aki elveszi az utolsó követ. Megoldás. A kezdő játékos a nyerő. Az első lépésében 8 követ vesz el, és így
1984 = 64 × 31 kő marad vissza. Ezután megismétli a második játékos minden lépését. A második játékos csak 1, 2, 4 vagy 8 követ vehet el. Az is igaz, hogy 16 osztja az 1984-et. Ezért a lépések száma egy páros szám lesz (az első lépést leszámítva). Így a kezdő játékos fogja megtenni az utolsó lépést.
2.2. Feladat. Egy körön
n pont van beszámozva a következő módon: 1, 2 ,..., n . Két
játékos egymás után összeköt két, azonos paritású pontot egy húrral. Egyik húrnak sincsen közös pontja egy már létező másik húrral (még a csúcspontjuk sem). Az a játékos veszít, akinek nincs több lépése. Megoldás. A második játékos a nyerő, ha
n = 4k + 2 . A kezdő játékos a nyerő minden
más esetben. Tekintsük úgy, hogy a megadott pontok egy szabályos n-szög csúcsai. 1. Eset Legyen
n = 4k . A kezdő játékos először berajzolja az első lépésében a kör
átmérőjét, és ezután minden lépésében az átmérőre szimmetrikusan követi a második játékos lépéseit. 2. Eset Legyen
n = 4k + 2 . Ekkor a második játékos az első játékos minden lépését
a kör középpontjára szimmetrikusan követi. Itt azt a legfontosabb felismerni, hogy az átlósan ellentétes pontok ellentétes paritásúak. 3. Eset Legyen az
n = 4k + 1 . Ekkor a körön van két szomszédos páratlan pont: az 1
n . A kezdő játékos első lépésében összeköti az 1 és 3 számozású pontokat, és így
tulajdonképpen átalakítja a játékot az
n = 4(k − 1) + 2
esetre, ahol a kezdő játékos a
vesztes. 4. Eset Legyen és
2k + 3
n = 4k + 3 . A kezdő játékos az első lépésében összeköti a 2k + 1
számozású pontokat. Ezután ha megpróbáljuk képzeletben a visszamaradó
4k + 1 pontot úgy mozgatni, hogy egy szabályos (4k + 1) –szöget alkosson, akkor az átlósan ellentétes pontok ellentétes paritásúak lesznek, és ebben a játékban a második játékos a vesztes.
és
2.3. Feladat. Adott egy m × n kiterjedésű, egységnégyzetekből álló mező. A játékosok egy lépésben egy tetszőleges egységnégyzetet színezhetnek be a következő szabály szerint: nem lehet kettőnél több négyzetet beszínezni akármelyik olyan négy darab négyzetből, amelyek két tetszőleges sor és két tetszőleges oszlop metszésében helyezkednek el. Az a játékos veszít, akinek nincsen több lépése. Ki fog nyerni egy becsületes játék esetén? A következő eseteket vegyük fontolóra: i) 4 × 6 ; ii) 5 × 5 ; iii) 4 × 7 ; iv) m × n . Megoldás. Az ii) esetben, és minden egyéb esetben, ahol az m és n számok páratlan számok, ott a kezdő játékos fog nyerni. A következő szimmetrikus stratégiát kell követnie: az elején beszínezi a középpontban elhelyezkedő egységnégyzetet, és ezután a második játékos lépéseit követi szimmetrikusan. Amikor a mezőnek legalább az egyik oldala „páros oldal”, akkor forgassuk el gondolatban a mezőt úgy, hogy a sorok száma páros legyen. A kezdő játékos minden lépése után a második játékosnak ugyanabban az oszlopban kell beszíneznie egy egységnégyzetet. A két sor, ahol a játékosok már beszíneztek, most már „zárt”. A második játékosnak ezután egy új fog kell beszíneznie, a második játékos erre szintén egy ugyanabban az oszlopban történő beszínezéssel válaszol, és további két sor „zárt” lett. De a sorok száma páros, és így a kezdő játékos nem fog tudni többször lépni. A második játékos fog nyerni.
3. Rész JÁTÉKOK POLINOMOKKAL Az ilyen típusú játékokra az jellemző, hogy a polinomok együtthatóit kell speciálisan úgy megválasztanunk, hogy aztán a polinom gyökei megfelelő tulajdonságúak legyenek. Ehhez a következő tételt szükséges felhasználnunk. Tétel. Ha az f x függvény folytonos az a ,b intervallumon és f ( a ) ⋅ f (b) < 0 akkor
( )
létezik egy olyan
c
pont, hogy
f (c ) = 0 .
[ ]
3.1. Feladat. Egy táblára fel van írva a következő egyenlet:
f ( x ) = x 3 + a1x 2 + a2 x + a3 = 0
. Két játékos játssza a következő játékot – az első játékos egy valós számot ír az egyenlet egyik együtthatójának a helyére, aztán a második játékos ugyanezt elvégzi egy másik együtthatóval. Végül a kezdő játékos ugyanezen módon megváltoztatja az utolsó együtthatót. A kezdő játékos a nyerő, ha az egyenletnek három különböző valós gyöke van. Ellenkező esetben a második játékos a nyerő. Megoldás. A kezdő játékos nyerheti meg a játékot a következő stratégiával: Az első lépése az, hogy úgy változtassa meg az a 2 együtthatót, hogy 1 + a 2 < 0 legyen. Továbbá, a
második játékos lépése után úgy választja meg az utolsó visszamaradó együtthatót, hogy a1 + a3 = 0 legyen. Ekkor
f (1) = 1 + a1 + a 2 + a3 < 0 és f (− 1) = −1 + a1 − a2 + a3 > 0 .
A Tételt felhasználva arra a következtetésre jutunk, hogy az gyöke van rendre a
f (x )
függvénynek három valós
(− ∞ , − 1), (− 1,1), (1, ∞ ) intervallumokon.
3.2. Feladat. Egy táblára fel van írva a következő egyenlet:
∗ x 2 + ∗x + ∗ = 0 amiben minden csillag egy valós együttható jelent. Két játékos a következő játékot játssza: A kezdő játékos kiválaszthat bármely három valós számot, és a második játékos elhelyezi őket a csillagok helyére, olyan sorrendben, ahogy akarja. A kezdő játékos a nyerő, ha az így kapott egyenletnek két különböző racionális gyöke van. Megoldás. A kezdő játékos lesz mindig a nyerő, ha úgy választ három különböző a, b, c egész számot az együtthatóknak, hogy a + b + c = 0 . Ekkor az egyenlet gyökei a következők lesznek:
x1 = 1, x2 =
c , ( c ≠ a ). a
3.3. Feladat. Egy táblára fel van írva a következő egyenlet:
f ( x ) = x 3 + a1x 2 + a2 x + a3 = 0 . Két játékos egymás után felcseréli az egyenlet együtthatóit (nem feltétlenül az a1 , a2 , a3
( )
sorrendben) nem nulla egész számokkal. A kezdő játékos a nyerő, ha az f x függvénynek van legalább két különböző egész gyöke. A második játékos a nyerő bármely más esetben. Megoldás. A kezdő játékos a nyerő, ha az első lépése
a 2 = −1
és a második lépése
(harmadik lépés a játékban) – a második játékos lépésének ellentettje. Így az függvény a következő kétféle módon fejezhető ki:
( ) x 3 − ax 2 − x + a = ( x − a )(x 2 − 1) x 3 + ax 2 − x − a = ( x + a ) x 2 − 1
f (x )
vagy
.
Ezért az így kapott
f ( x ) függvénynek lesz két különböző egész gyöke: + 1
és
−1 .
3.4. Feladat. Adott az
f ( x ) = x 4 + a1x 3 + a2 x 2 + a3 x + a4 = 0
egyenlet. A játék a következő: az első játékos az egyik együtthatót lecseréli egy nem nulla egész számra, aztán a második játékos választ nem nulla egész számokat a maradék három együttható helyére. Ha az f x függvénynek van legalább kettő különböző egész gyöke, akkor a második játékos a nyerő, ellenkező esetben a kezdő játékos fog nyerni.
( )
Megoldás. A kezdő játékos a nyerő, ha
a4 = −1 -t választja. Ekkor az
x 4 + a1 x 3 + a2 x 2 + a3 x − 1 = 0 egyenlet egész gyökei már csak (+1)-gyel vagy (-1)-gyel lehetnek egyenlők. De ha ezek az f x függvény gyökei, akkor
( )
ahonnan
a2 = 0
a1 + a2 + a3 = 0 − a1 + a2 − a3 = 0
és ,
, ami lehetetlen a játék szabályai alapján.
3.5. Feladat. Egy táblára fel van írva a következő egyenlet:
f (x ) = x 3 + ∗x 2 + ∗x + ∗ = 0 .
A kezdő játékos mond egy valós számot és a második játékos elhelyezi ezt bármelyik csillag helyére. Ezután a kezdő játékos megint mond egy valós számot, amit a második játékos elhelyez a visszamaradó két csillag egyikére. Végezetül a kezdő játékos az utolsó csillag helyére elhelyez egy valós számot. A kezdő játékos a nyerő, ha az így kapott egyenletnek három különböző egész gyöke van. Bármely más esetben a második játékos a nyerő. Megoldás. A kezdő játékosnak van nyerő stratégiája. Az első számnak, amit mond, a 0-nak kell lennie. 1. Eset Ha a második játékos a 0-t az utolsó csillag helyére teszi, akkor
f (x ) = x 3 + ∗x 2 + ∗x
at . Ekkor
. Ezután a kezdő játékos a 2-es számot választja, majd végül a -3-
f ( x ) = x( x − 1)( x − 2 ) vagy f ( x ) = x( x − 1)( x + 3) .
2. Eset Ha a második játékos a 0-t az első csillag helyére teszi, akkor következik, hogy
f ( x ) = x 3 + bx + c .
Ezután a kezdő játékos a − ( 3 ⋅ 4 ⋅ 5 ) számot mondja. Ha a második 2
c = 0,
játékos ezt a számot b helyére teszi, akkor játékos a
és ha c helyére teszi, akkor a kezdő
b = 32 4 2 − 325 2 − 4 25 2 számot választja. Így rendre f ( x ) = x ( x + 3 ⋅ 4 ⋅ 5 )( x − 3 ⋅ 4 ⋅ 5 ) és
(
)(
)(
f ( x ) = x + 32 x + 4 2 x − 5 2
)
. 3. Eset Ha a második játékos a 0-t a második csillag helyére teszi, akkor következik, hogy
f ( x ) = x 3 + ax 2 + c . Ezután a kezdő játékos a következő számot mondja: 6 27 3
ezután a következő lépést választja:
a = −7 2
vagy
és
c = −687 6 . Így rendre
f ( x) = ( x + 2 ⋅ 7 )( x − 3 ⋅ 7 )( x − 6 ⋅ 7 )
és
f ( x ) = ( x − 2 ⋅ 6 2 7 2 )( x + 3 ⋅ 6 2 7 2 )( x + 6 2 7 2 ) . 3.6. Feladat. Két játékos egymás után megváltoztatja a következő polinom együtthatóit egész számokra:
P( x ) = a0 + a1 x + a2 x 2 ... + a1000 x1000 .
A kezdő játékos a nyerő, ha az így kapott polinom mindig ugyanannyi maradékot ad 6-tal osztva minden egész x számra. Ellenkező esetben a második játékos a nyerő. Megoldás. Vegyük észre, hogy bármely kifejezéseket:
k 3 − k = (k − 1)k (k + 1)
következő polinom
k és
egész szám esetén a 6 osztja a következő
k 4 − k 2 = k ⋅ ( k − 1) k ( k + 1)
Q( x ) = ax + bx 2 + cx 3 + dx 4
. Ezért, hogy a
minden k egész szám esetén osztható legyen 6-tal, elegendő, hogy a következő feltételek teljesüljenek:
a+c=0
és b + d = 0 . Egyesítsük a P x polinomban a tagokat az első hatványtól a negyedik hatványig, az ötödik hatványtól a nyolcadik hatványig és így tovább. A végén azt kapjuk, hogy
( )
P ( x ) = a0 + az
f k (x )
k = 249
∑ x 4k f k ( x )
,
k =0
függvényeknek általános alakja ugyanaz, mint a
Q ( x ) függvényé.
Így a kezdő játékos a következő stratégiát választhatja:
a0 helyére a kívánt maradékot teszi, és ezután pedig mikor a második játékos kiválasztja az f k ( x ) függvény egyik együtthatóját, úgy kell válaszolnia, hogy az együtthatók kielégítsék a megfelelő egyenlőségeket: a + c = 0 és b + d = 0 . Az így kapott egész együtthatójú P ( x ) polinom bármely x egész szám esetén a kiválasztott a 0 maradékot fogja adni 6-tal osztva. 3.7. Feladat. Adott a
P( x ) = x10 + * x 9 + * x8 + ..... + * x 2 + * x + 1 polinom. Két játékos egymás után lecseréli a polinom csillagait egész számokra (általánosan - 9 lépés). A kezdő játékos a nyerő, ha az így kapott polinomnak nincsen valós gyöke. Ha a polinomnak van legalább egy valós gyöke, akkor a második játékos nyer. Lehetséges-e, hogy mindig a második játékos nyerjen a kezdő játékos lépéseitől függetlenül? Megoldás. A válasz: Igen, neki van nyerő stratégiája, bárhogyan is játszik a kezdő játékos! 9 csillagot kell megváltoztatni – 5 páratlan hatványhoz és 4 páros hatványhoz tartozót. Ha a kezdő játékos egy páros (páratlan) hatvány melletti kitevőt változtat meg, akkor a második játékosnak egy páratlan (páros) hatvány melletti együtthatót kell megváltoztatnia. Így 7 lépés
k
l
után két csillag marad hátra az x és x hatványok mellett, ahol a k és l számoknak legalább az egyike páratlan szám, és a második játékos lépése következik. A hét lépés után legyen a következő a polinom:
P ( x ) = Q ( x ) + αx k + β x l
.
Két eset létezik: i)
k
- páros szám,
l
- páratlan szám. Ekkor:
P (1) = Q (1) + α + β , P (− 1) = Q (− 1) + α − β , P (1) + P (− 1) = Q (1) + Q (− 1) + 2α . A 1 második játékosnak a következőt kell választania: α = − [Q(1) + Q(− 1)] . Ezért a kezdő 2 játékos lépéseitől függetlenül azt fogjuk kapni, hogy: P(1) + P(− 1) = 0 . Így, vagy P(1) = P(− 1) = 0 és a P ( x ) polinomnak már van két valós gyöke: (+1) és (-1), vagy P(1) = − P(− 1) , azaz P (1) ⋅ P ( −1) < 0 és ekkor a P ( x ) polinomnak legalább egy valós gyöke lesz a [− 1,1] intervallumon, (lásd az ábrát ennek a résznek az elején).
ii)
k
és
l
- páratlan számok. Ekkor:
P(−1) = Q(−1) − α − β ahonnan:
,
P (2) = Q (2) + α ⋅ 2k + β ⋅ 2l ,
2l ⋅ P(−1) + P(2) = 2l ⋅ Q(−1) + Q(2) + ( 2k − 2l ) ⋅ α .
A második játékosnak ekkor a következőt kell választania: α = −
2l ⋅ Q(−1) + Q(2) . 2 k − 2l
a kezdő játékos utolsó lépésétől függetlenül azt fogjuk kapni, hogy: Így, vagy vagy
P(− 1) = P(2) = 0
2 ⋅ P(−1) = − P(2) l
egy valós gyöke a
és a
azaz
P(x )
Ezért
2l ⋅ P(−1) + P(2) = 0 .
polinomnak van két valós gyöke: (-1) és (+2),
P (−1) ⋅ P (2) < 0
és a
P(x )
polinomnak lesz legalább
[− 1, 2] intervallumon, (lásd az ábrát ennek a résznek az elején).
4. Rész MINIMAX Ebben a részben olyan játékokat fogunk megnézni, amiben minden játékos nyereménye változtatható bizonyos számokkal, és ezek a számok a játékosok lépéseitől függenek, és mindkét játékos növelni szeretné a nyereményét. A játékokban a két játékos által megszerezhető nyeremény összege konstans lesz, független a játékosoktól. A játékosok érdekei ellentétesek, mivel ha az egyik játékos jutalma megnő, akkor a másiké csökken. 4.1. Feladat. Egy fiú és egy lány eloszt egymás között 10 csomagot a következő módon: a fiú szétosztja őket két halomba és lány elviszi az egyik kupacot. Mennyi csomagot vihet el a lány, illetve a fiú? Megoldás. Mindketten pontosan 5 csomagot fognak elvinni. Ugyanis a fiú nem fogja őket két eltérő kupacba osztani, mert akkor a lány a nagyobbat fogja elvinni. A fiú érdeke az, hogy a lány részét olyan kicsire állítsa be, amennyire csak lehet. Az ilyen típusú stratégiákat hívjuk “minimax” stratégiának. 4.2. Feladat. Az
( )
( )
1, 2 , 3,..., 20
számokat felírtuk egy táblára. Két játékos egymás után
a + vagy − jelet teszi minden szám elé. Minden még szabad szám elé rakható jel. A kezdő játékos a végén a lehető legkisebb abszolútértékű összeget akarja kapja, de a második játékos a lehető legnagyobb abszolút értékű összeget akarja elérni. Mekkora értéket érhet el a második játékos? Megoldás. A második játékos által elérhető legnagyobb összeg a 30. Most tekintsük a második játékos stratégiáját, hogy elérje a lehető legnagyobb összeget. A számokat 10 párra osztjuk: 1, 2 , 3, 4 ,..., 19 , 20 . A kezdő játékos minden lépésében valamilyen jelet fog tenni minden párban a nagyobb szám elé, a második játékos erre az ellentétes jellel fog válaszolni a számpár másik tagjánál. Csak egyetlen esetben, mikor a kezdő játékos egy jelet tesz az utolsó számpár egyik tagja elé, akkor kell a második játékosnak ugyanazt a jelet tennie ugyanannak a számpárnak a másik tagja elé. Nyilvánvaló, hogy az így kapott összeg abszolútértéke nem kevesebb, mint: 19 + 20 − 1 − 1 − ... − 1 = 30 .
( )(
) (
)
Most be fogjuk bizonyítani, hogy a kezdő játékosnak megvan a lehetősége, hogy a második játékos összegét nem többre, mint 30-re korlátozza. A visszamaradó számok közül a legnagyobb elé ellentétes előjelet kell tennie, mint ami az összeg előjele abban a pillanatban (ha az összeg 0, akkor a kezdő játékos + jelet tesz). Tekintsük a játék egyik példáját és legyen a k-lépés az utolsó lépés, amikor az összeg előjelet cserél (beleértve azokat a lépéseket is, amikor az összeg 0). Az első k − 1 lépésben nyilvánvalóan fel lesznek használva a 20 , 19 , 18 ,...,20 − k − 1 számok. Ekkor a lehetséges legnagyobb abszolútértékű összeg a k-lépés után: 20 − k − 1 + 20 − k = 41 − 2k .
( )
(
(
)
)
Ezután a következő minden 10 − k lépésben az összeg minimum eggyel csökken, mivel az első játékos minden lépésben az összeg abszolútértékét a visszamaradó számok közül a legnagyobbal, m -mel csökkenti, és a második játékos ezt nem többel, mint m − 1-gyel tudja növelni. Így a végső eredmény nem lehet több, mint 41 − 2k − 10 − k = 31 − k ≤ 30 .
(
) (
)
5. Rész NYERŐ STRATÉGIÁK Az alább következő feladatokban a játékosok egyikének van nyerő stratégiája. 5.1. Feladat. Adott egy 3× 3 -as kiterjedésű táblázat és 9 egységnyi kiterjedésű kártya. Minden kártyára a következő számok egyike van felírva: a1 < a2 < ... < a9 . Két játékos egymás után a még felhasználatlan kártyák egyikét a táblázat egyik még szabadon lévő mezőjére helyezi. Miután felhasználták az összes kártyát, a kezdő játékos összeadja a legfelső és legalsó sorban lévő 6 számot, és a második játékos pedig összeadja a jobb és bal oldalon lévő oszlopokban található 6 számot. Az a játékos nyer, akinek nagyobb az összege. Megoldás. Vagy az első játékos nyer, vagy döntetlen a játszma. Ha a1 + a9 > a 2 + a8 , akkor a kezdő játékos az a9 -et helyezi az 1-es mezőre, és
a 2 -t vagy a1 -t tesz a 2-es vagy 3-as mezők egyikére. a1 + a9 < a 2 + a8 , akkor a kezdő játékos a1 -t tesz a 2-es mezőre és a második a9 -t vagy a8 -t tesz az 1-es vagy 4-es mezők valamelyikére. a1 + a9 = a2 + a8 , akkor a kezdő játékos a fentebb leírt stratégiák egyikét
a második lépésben Ha lépésben
Ha használhatja.
1 2
3
4 5.2. Feladat. Adott egy n ≥ 5 oldalú konvex poliéder. A poliéder minden csúcsából pontosan 3 darab él indul. Két játékos egymás után felírja a nevét az egyik szabad oldalra. Az a játékos nyer, aki először írja fel a nevét három olyan oldalra, amik egy csúcsban találkoznak. Megoldás. A kezdő játékos nyer. Szükséges, hogy bebizonyítsuk az elején, hogy létezik egy olyan csúcs, ami nem egy háromszög. Legyen minden oldal egy háromszög! Ekkor a poliédernek
3n éle van, mivel 2
minden csúcsból három él indul és minden él egyszerre két csúcshoz is tartozik. Felhasználva Euler tételét Csúcsok száma + Oldalak száma − Élek száma = 2 , azt
(
)
3n = 2 , azaz n = 4 , ami ellentmondásban áll a játék feltételeivel. 2 Így van egy olyan oldal, hívjuk ezt A1 -nek, ami nem egy háromszög. Az első játékosnak fel kell írnia a nevét A1 -re. A kezdő játékosnak a második lépésében fel kell írnia a nevét az A2 oldalra, ami az A1 oldallal határos, valamint szintén van közös éle az A3 és A4 szabad oldalakkal, amik szintén A1 mellett fekszenek (ez biztosan lehetséges, mivel a második játékos csak egy A1 mellett elhelyezkedő oldalt tud felhasználni). A harmadik lépése végén a kezdő játékos felhasználhatja az A3 vagy A4 oldalak egyikét, azt, amelyiket a második kapjuk, hogy
n+n−
játékos még nem használt fel. Így a kezdő játékos nyer. 6. Rész SZÁMELMÉLET 6.1. Feladat. Két játékos egy 2 p -jegyű számot ír fel az 1, 2, 3, 4, 5 számjegyek felhasználásával. A kezdő játékos írja fel az első jegyet, a második írja fel a második jegyet, a kezdő játékos írja fel a harmadik jegyet és így tovább… Ha a kapott szám osztható 9-cel, akkor a második játékos nyer. Ellenkező esetben az első játékos nyer. Megoldás. Jelöljük a kezdő játékos által felírt számjegyeket a következőkkel a1 , a 2 ,..., a p , a második játékos által felírt jegyeket pedig a b1 , b2 ,...,b p számokkal és
S = a1 + a2 + ... + a p + b1 + b2 + ... + b p . 1. Eset Ha p = 3m , akkor a második játékos a nyerő a következő bi = 6 − ai , ekkor az összeg S = (a1 + b1 ) + (a2 + b2 ) + ... + a p + b p = 6 p = 18m
legyen
(
stratégiával:
)
, ami osztható 9-cel, azaz a kapott szám osztható 9-cel. 2. Eset Ha p = 3m + 1 vagy p = 3m + 2 , akkor a kezdő játékos a nyerő a
= 3 és ezután ai = 6 − bi −1 , ekkor az összeg S = a1 + (a2 + b1 ) + (a3 + b2 ) + ... + a p + b p −1 + b p = 3 + 6( p − 1) + b p
következő stratégiával: a1 Ha
(
(
p = 3m + 1 , akkor az S = 18m + 3 + b p
és 8 között van.
)
) összeg nem osztható 9-cel, mivel 3 + b p 4
Analóg módon, ha mivel
bp
p = 3m + 2 ,
akkor az
S = 18m + 9 + b p
összeg nem osztható 9-cel,
1 és 5 között van.
6.2. Feladat. Két játékos egy 2 p -jegyű számot ír fel a 6, 7, 8, 9 számjegyek felhasználásával. A kezdő játékos írja fel az első számjegyet, a második játékos a másodikat, a kezdő játékos a harmadikat, és így tovább… Ha az így kapott szám osztható 9cel, akkor a második játékos nyer. Ellenkező esetben a kezdő játékos nyer. Megoldás. 1. Eset Ha p = 3n , akkor a második játékos nyer. A kezdő játékos minden lépése után egy olyan számjegyet ír, ami a kezdő játékos által előtte felírt számjeggyel összeadva 6-os maradékot ad 9-cel osztva. (6 után a második játékos 9-et ír, a további ilyen számpárok pedig: 7 − 8 , 8 − 7 , 9 − 6 .
)
2. Eset Legyen p = 3n + 1 . Ekkor a kezdő játékos nyer. A kezdő játékos lépése bármi lehet 9 kivételével. Ezután a második játékos minden lépése után egy olyan számjegyet ír fel, ami a második játékos által előtte felírt számjeggyel összeadva 6-os maradékot ad 9-cel osztva. A kezdő játékos ilyen stratégiája esetén a számjegyek összege az első és utolsó számjegy kivételével osztható lesz 9-cel. De az első számjegy nem 9, és így az összes számjegy összege nem osztható 9-cel. 3. Eset Ha p = 3n + 2 , akkor a kezdő játékosnak van nyerő stratégiája a következő módon: a kezdő játékos első lépése a 9-es számjegy. Ezután a második játékos minden lépését az utolsó kivételével hasonló módon válaszolja meg, mint a 2. Esetben. Ha a második játékos lépése, ami az utolsó előtt van, nem 9, akkor a kezdő játékos a 9-et választja. Ezzel a stratégiával a számjegyek összege az első nélkül és az utolsó 3 nélkül osztható 9-cel. A négy “rendkívüli” számjegy között pedig legalább egy van, ami különböző 9-től. Így ezen 4 számjegy összege nem osztható 9-cel és ugyanez igaz az összes számjegyre is. 6.3. Feladat. Néhány játékos, akik egy kör alakú asztal mellett ülnek, az óramutató járásával megegyező irányban vannak számozva. Az első játékosnak eggyel több eurója van, mint a másodiknak, a másodiknak eggyel több, mint a harmadiknak, és így tovább, minden játékosnak eggyel több eurója van, mint a rákövetkezőnek. Az első játékos egy eurót ad a második játékosnak, a második játékos 2 eurót ad a harmadiknak, és így tovább, minden játékos eggyel több eurót ad a rákövetkezőnek, mint amennyit ő kapott. A játék addig folytatódik, amíg lehetséges. A játék végén kiderül, hogy az egyik játékosnak négyszer annyi eurója van, mint a szomszédjai egyikének. Hányan vannak a játékosok, és hány eurója volt a játék elején a “legszegényebbnek”? Megoldás. Legyen n a játékosok száma és legyen közülük a “legszegényebbnek” (például az n. játékosnak) x eurója a legelején. A játék szabályai szerint az első “kör” után a játékosoknak (a számozásuk szerint) x + 2n − 2 , x + n − 3,..., x + 1, x , x − 1 eurója van. Ezután a játék x körön keresztül folytatódik, amíg az n. játékosnak elfogy az x eurója. Ekkor a játék végén a játékosoknak rendre x + x + 1 n − 1 , n − 2 , n − 3,..., 2 , 1, 0 eurója van.
(
)(
)
Mivel az 0 , 1, 2 ,..., n − 2 számok egymást követő természetes számok, ezért csak az első játékosnak lehet 4-szer annyi pénze, mint az egyik szomszédjának. De a szomszédjai a 2. és n. játékosok. Mivel az utolsó játékosnak 0 eurója van a játék végén, ezért a feltételek alapján a következő egyenletet kapjuk:
x + ( x + 1)( n − 1) = 4 ( n − 2 ) ,
azaz
x=
3n − 7 7 = 3− . n n
Ezért n a 7 osztója, és így csak 1 vagy 7 lehet. De ha n = 1 , akkor azt kapjuk, hogy x < 0 , ami lehetetlen. Így n = 7 és x = 2 , azaz 7 játékos van az asztal körül és közülük a „legszegényebbnek” 2 eurója volt a játék elején. Megjegyzés. A fenti érvelés azzal a feltételezéssel készült, hogy x ≠ 0 , de könnyen látható, hogyha x = 0 , akkor a feladatban leírt szituáció lehetetlen lenne.
k motorosnak (k ≥ 1) A -ból B -be kell utaznia. Az első napon az M i 1 részét tette meg, ahol ni egy pozitív egész motoros (i = 1,2 ,...,k ) a teljes távolság ni 1 szám. A második napon a visszamaradó út részét tette meg, ahol mi egy pozitív egész mi 1 szám. A harmadik napon a második nap után visszamaradó távolság részét tette meg, a ni 1 negyedik napon pedig a harmadik nap után visszamaradó távolság részét tette meg. Az mi (mi ,ni ) és m j ,n j természetes számokból álló számpárok különbözők, ha 6.4. Feladat.
(
)
i ≠ j , (i , j = 1,2 ,..., k ) . A negyedik 3 pontosan az út részét tette meg A 4
nap végén kiderült, hogy az összes és
Mi
motoros
B között.
i) Keressük meg a legnagyobb lehetséges pozitív k számot; ii) Melyik M i motoros lesz a győztes a fenti feltételek szerinti versenyben, ha az mi , ni számok mi ni szorzatának a lehető legnagyobbnak kell lennie? Megoldás. Jelöljük az motoros
1 S ni
S -sel
az
A
és
közötti távolságot. Az első napon az
B
utat tett meg, és a visszamaradó távolság:
⎛ 1 1⎞ S = ⎜⎜1 − ⎟⎟ S . ni ⎝ ni ⎠ 1 ⎛ 1⎞ ⎜⎜1 − ⎟⎟ S utat tett meg, és a visszamaradó távolság: mi ⎝ ni ⎠ S−
A második napon
⎛ ⎛ 1⎞ 1 ⎛ 1⎞ 1 ⎞⎛ 1 ⎞ ⎟⎟ S ⎜⎜1 − ⎟⎟ S = ⎜⎜1 − ⎟⎟⎜⎜1 − ⎜⎜1 − ⎟⎟ S − n m n n m i⎠ i⎝ i⎠ i ⎠⎝ i⎠ ⎝ ⎝
.
Hasonlóan folytatva arra jutunk, hogy a negyedik nap végén visszamaradó távolság:
⎛ 1⎞ ⎜⎜1 − ⎟⎟ ⎝ ni ⎠
2
2
⎛ 1 ⎞ ⎜⎜1 − ⎟⎟ S ⎝ mi ⎠
Így a következő egyenletet kapjuk:
.
Mi
2
2
2
2 ⎛ ⎡ (mi − 1)(ni − 1)⎤ 1⎞ 1 ⎞ 1 ⎛ ⎜⎜1 − ⎟⎟ S = S , azaz ⎢ ⎥ − ⎜ ⎟ = 0 , ahonnan 4 mi ni ⎝2⎠ ⎝ mi ⎠ ⎣ ⎦ ( mi − 1)( ni − 1) = + 1 ⎛ vagy = − 1 ⎞ ⎜ ⎟. 2 ⎝ 2⎠ mi ni Mivel mi ≥ 1 , ni ≥ 1 ezért következik, hogy (mi − 1)(ni − 1) 1 2 , azaz . =+ mi = 2 + mi ni 2 ni − 2 De mivel mi egy egész szám, ezért ni − 2 -nek 2 osztójának kell lennie. Felhasználva, hogy az ni számok szintén pozitív egészek, azt kapjuk, hogy ni vagy 3 vagy 4. Ekkor mi
⎛ 1⎞ ⎜⎜1 − ⎟⎟ ⎝ ni ⎠
vagy 4, vagy 3 rendre. Így csak két megoldást kapunk: az motorost az i) ii)
M1
motorost az
(m2 ,n2 ) = (4, 3) számokkal. Így
a legnagyobb lehetséges pozitív k szám a ilyen versenyben nincsen győztes, mivel:
(m1 ,n1 ) = (3, 4 ) számokkal és az M 2 k =2
.
m1n1 = m2 n2 = 3 ⋅ 4 = 4 ⋅ 3 = 12 . 6.5. Feladat. Adottak az 1, 2 , 3,..., 27 számok. Két játékos egymásután letöröl egy számot, amíg két szám marad. Ha ezek összege osztható 5-tel, akkor a kezdő játékos nyer. Ellenkező esetben a második játékos nyer. Ki fog nyerni becsületes játék esetén? Megoldás. Sokkal megfelelőbb, ha nem a megadott számokkal, hanem az 5-tel való osztási maradékaikkal dolgozunk. Ezek a maradékok: 5 darab 0, 5 darab 4-es, 5 darab 3-as, 6 darab 1-es és 6 darab 2-es. A kezdő játékos a nyerő. A kezdő játékos első lépése az, hogy letörölje az 1-es számot. Ezután olyan maradékú számokat kell letörölnie, hogy második játékos által letörölt és az általa letörölt számok maradékainak összege együtt 5-öt adjanak. Még pontosabban: i) ha a második játékos lépései a következők: 1, 2, 3, 4 , akkor az első játékos lépései 4, 3, 2, 1; ii) ha a második játékos lépése 0, akkor a kezdő játékos lépése 2, és ezután a második játékos minden 0 lépése után szintén 0 lesz a válaszlépése. Ezt a stratégiát használva a játék végén visszamaradó két szám maradékai a következők lehetnek: 0, 0 vagy 2, 3 vagy 1, 4. 6.6. Feladat. Adott egy körön n doboz. A dobozok egyikében két kő van – egy fehér és egy fekete. A többi doboz üres. Két játékos egymás után mozgatja a köveket – az első az óramutató járásával megegyező irányban mozgatja a fehér követ egy vagy két dobozon keresztül, a második játékos a fekete követ mozgatja ellentétes irányban szintén egy vagy két dobozon keresztül. Az a játékos nyer, aki a saját kövét a másik játékos kövét is tartalmazó dobozba teszi. Ki fog nyerni egy becsületes játék esetén? A következő eseteket vegyük fontolóra: i) n = 13 ; ii) n = 14 ; iii) n = 15 ; iv) n egy tetszőleges természetes szám. Ötlet. Fontos, hogy észrevegyük, hogy: a) ha 4 üres doboz van a kövek között, akkor ez egy “csapda” – az a játékos, akinek lépnie ekkor, az fog veszíteni; b) ha 3 üres doboz van a kövek között, akkor ez egy “átjáró” – a kövek át fognak haladni a következő lépésben
egymáson,
n = 5k + s ,
anélkül,
(s
hogy = 0 ,1, 2 , 3, 4 .
)
“harcolnának”.
Használjuk
a
következőt:
6.7. Feladat. Egy termék ára n euró. Két áruház-igazgató játszik. Mindegyikük megnöveli a termék árát egy lépésében m % -kal , ahol m egy természetes szám,
m ∈ [1,100 ) ,
de úgy, hogy a növekedés egész számú euró legyen. Az a játékos veszít, akinek nincsen több lépése. Melyik igazgató fog veszíteni? A következő eseteket vegyük fontolóra: i) n = 1000 ; természetes szám.
ii)
n = 880 ;
n = 600 ;
iii)
iv)
n = 2k ;
v)
n
egy tetszőleges
n = m ⋅ 2 k ⋅ 5s , ahol m = 10 p + q , (1, 3, 7,9) , k és s természetes számok oszthatók 3-mal.
Válasz. A második játékos fog nyerni, ha
p egy tetszőleges természetes szám, és a Minden egyéb esetben a kezdő játékos a nyerő.
7. Rész APPENDIX 7.1. Feladat. Egy kenguru ugrál az
(
)
x ≥ 0, y ≥ 0
irányban az
Oxy koordináta-síkon a (x + 1, y − 1) vagy (x − 5, y + 7 )
következő módon: az x , y pontból a kenguru az pontba ugorhat, de nem ugorhat olyan pontra, aminek van negatív előjelű koordinátája. Mely x , y kezdőpontokból nem juthat el a kenguru olyan pontba, aminek az Oxy koordinátasík
(
O
)
1000 egység. Rajzoljuk meg az ilyen ( x , y ) T halmazát és számítsuk ki a T halmaz F területét!
középponttól való távolsága nagyobb, mint
pontok
Válasz. F = 15 . A “lépcső” pontjai nélkül:
T ( x , y ) halmaz a következő:
egy lépcső-szerű háromszög a
T ( x , y ) ≡ {( x = k + α , 0 ≤ y < 5 − k , k = 0 ,1, 2 , 3, 4; 0 ≤ α ≤ 1 ) \
ahol
\ ( x = k , 5 − k < y < 6 − k , k = 1, 2 , 3, 4 , 5 )} ≡ { [x ] + [ y ] ≤ 4 , x ≥ 0 , y ≥ 0 }, [x] az egészrész-függvény, azaz ha a fenti esetben ha x = n ,... ,egy nemnegatív tizedes tört alakú számjegy, akkor [x ] = n egy természetes szám.
7.2. Feladat. Egy játékautomata a következő módon működik: miután bedobunk 5 centet, az automata megszorozza 3-mal az adott számot, és miután bedobunk 2 centet, az automata 4-et ad az adott számhoz. i)
Minimálisan hány cent szükséges ahhoz, hogy eljussunk az 1-es számtól az
n = 1979 -ig a megadott automata segítségével? ii) Hány cent szükséges minimálisan, ha Ötlet. Hátulról kell elindulnunk –
n = 2005 ?
n -től 1-ig !
i)
A minimálisan szükséges centek száma: sorozatot!
37 = 5 ⋅ 5 + 6 ⋅ 2 .
Lásd az alábbi
1979 ⇐ 1975 ⇐ 1971 ⇐ 657 ⇐ 219 ⇐ 73 ⇐ 69 ⇐ 23 ⇐ 19 ⇐ 15 ⇐ 5 ⇐ 1 n
n
7.3 Feladat. Válasszunk ki 2 darab különböző természetes számot az 1 és 3 számok között (ezeket is beleértve) úgy, hogy bármely két kiválasztott szám átlaga ne legyen benne a kiválasztott számok halmazában! Ötlet. Használjunk matematikai indukciót
n -re! A kiválasztott számok halmaza:
a1 = 1, a2 = 2, a3 = 7, a 4 = 8, ..., a2n−1 , a2n−1 +1 = a1 + 2 ⋅ 3n −1
a2n−1 + 2 = a2 + 2 ⋅ 3n −1 ,..., a2n = a2n−1 + 2 ⋅ 3n −1
