Fórum: Héttusa feladatok

A 6. kérdést – Legfeljebb hány királynő helyezhető el a sakktáblán úgy, hogy mindegyik legfeljebb egy másikat tartson ütés alatt? – láttam feladva \(\displaystyle 20\times20\)-as táblára itt.

A Harvard-MIT Mathematics Tournament (February, 2004) Guts Round — Solutions pdf-ben keressétek, a 44. feladat az. Bizonyítják, hogy legfeljebb 26 királynő állhat a táblán, és 23 királynőt el tudnak helyezni.

Ezzel zárul a megoldásuk: The best possible number of queens is not known to us; the following construction gives 23.

Tudunk-e jobbat? 23-nál többet, vagy szorosabb korlátot 26-nál.

15. kérdés: Legfeljebb hány királynő helyezhető el a \(\displaystyle 20\times20\)-as sakktáblán úgy, hogy mindegyik legfeljebb egy másikat tartson ütés alatt?

12/b kérdés. Az összeg bármi lehet a két korlát között. Jelöljük \(\displaystyle \pi_{k}\)-val azt a permutációt, ami az első \(\displaystyle n-k\) elemet fixen hagyja, az utolsó \(\displaystyle k\) elemet pedig tükrözi: \(\displaystyle \pi_k(n-k+i)=n+1-i\)  (\(\displaystyle i=1,\ldots,k\)). Könnyű látni, hogy ha a sorozat vége egyesével nő vagy fogy, akkor a \(\displaystyle \pi_{k}\) permutációt alkalmazva az eltérésösszeg éppen \(\displaystyle (k-1)\)-gyel nő, és a sorozatvég monotonitása – eggyel rövidebb szakaszon – megmarad. Ezért ilyen permutációk alkalmas sorozatával megoldható, hogy az eltérések összege egyesével változzon, \(\displaystyle n-1\)-től kezdve egészen \(\displaystyle n(n-1)/2\)-ig:

1 2 3 4 5 6 7  <<<
1 2 3 4 5 7 6
1 2 3 4 7 6 5
1 2 3 7 6 5 4
1 2 7 6 5 4 3
1 7 6 5 4 3 2  <<<
1 7 6 5 4 2 3
1 7 6 5 2 3 4
1 7 6 2 3 4 5
1 7 2 3 4 5 6  <<<
1 7 2 3 4 6 5
1 7 2 3 6 5 4
1 7 2 6 5 4 3  <<<
1 7 2 6 5 3 4
1 7 2 6 3 4 5  <<<
1 7 2 6 3 5 4

Az eltérésösszeg az utolsó permutációban még nem maximális, mert – ahogyan a kitűzésben is szerepelt – az alternáló tulajdonság mellett az is kell ehhez, hogy a szélső elemek minimális abszolút értékűek legyenek (a sorozatot 0 körülinek gondolva). Ez a jobb szélen teljesül, mert oda a sorozatvég monotonitásának megszűntével az átlag (,,nulla") kerül. A bal szélső helyre viszont az 1-et a többi \(\displaystyle \lfloor n/2\rfloor-1\) darab, átlagnál kisebb (,,negatív") számmal felcserélve az alternáló tulajdonság megmarad, és rendre megkapjuk a hiányzó, egyre nagyobb összegeket adó permutációkat:

2 7 1 6 3 5 4
3 7 2 6 1 5 4

Érdemes megnézni a módszert nagyobb elemszámmal, például a százelemű permutációkon. Itt az eltérésösszeg 99 és 4999 (=4950+49) közé eshet. Keressünk először olyan sorrendet, ahol az eltérésösszeg 1234. Mivel \(\displaystyle 1234=99+98+\ldots+87+25\), ezért a keresett permutáció \(\displaystyle id\circ\pi_{99}\circ\pi_{98}\circ\ldots\circ\pi_{88}\circ\pi_{26}\) (a kompozíciókat balról jobbra haladva végezve). Mivel

\(\displaystyle id\circ\pi_{99}\circ\pi_{98}\circ\ldots\circ\pi_{88}= \langle 1,100,2,99,\ldots,6,95,7,8,9,\ldots,94\rangle,\)

így \(\displaystyle \pi_{26}\)-tal az utolsó 26 elemet még tükrözve az eredmény:

\(\displaystyle \langle 1,100,2,99,\ldots,6,95,7,8,9,\ldots,68,94,93,92,\ldots,69\rangle.\)

Másik példa egy 4950 feletti eredményhez, pl. 4987-hez. Mivel \(\displaystyle 4987=4950+37\), ezért a teljesen alternáló \(\displaystyle \pi_{99}\circ\pi_{98}\circ\ldots\circ\pi_2\) permutációban a 38-at kell az 1-gyel felcserélni ahhoz, hogy az összeg 37-tel nőjön:

\(\displaystyle \matrix{ \langle 1,100,2,99,3,98,\ldots,37,64,38,63,39,62,\ldots,49,52,50,51\rangle \\ \Downarrow \\ \langle 38,100,2,99,3,98,\ldots,37,64,1,63,39,62,\ldots,49,52,50,51\rangle. }\)

Lemaradt: a 14. kérdéshoz.

Egy 18 átlót használó változat.

A Héttusa (ematlap.hu) legutóbbi fordulójában volt ez a feladat:

33. Egy 12-oldalú szabályos sokszögnek legfeljebb hány átlóját tudjuk megrajzolni úgy, hogy bármelyik legfeljebb egy másikat metszhet a sokszög belsejében?

A feladatsor, az 5. forduló itt van.
A kérdésre 14 a válasz. A megoldások már kint vannak az Érintő Facebook oldalán.

Ehhez kapcsolódva van egy új kérdésem.

14. kérdés: Egy 12-oldalú szabályos sokszögnek legfeljebb hány átlóját tudjuk megrajzolni úgy, hogy bármelyik legfeljebb két másikat metszhet a sokszög belsejében?

Rajzolgattam, az első próbálkozások 15 átlót adtak, majd találtam 17 átlót is, melyek teljesítik a feltételt.
A válasz talán 17?

A Kürschák verseny feladata volt 1962-ben:
Bizonyítsuk be, hogy egy konvex \(\displaystyle n\)-szög átlói közül nem lehet \(\displaystyle n\)-nél többet úgy kiválasztani, hogy bármely kettőnek legyen közös pontja.
A versenyen ez volt a legnehezebb feladat.
Megoldás: A konvex \(\displaystyle n\)-szög alakja nem számít. Feltehető tehát, hogy szabályosról van szó. Ebben az átlók iránya \(\displaystyle n\)-féle lehet, legfeljebb ennyi tehát a páronként metszők száma is.

Hoppá, 12/b túl könnyű lett, 6.5 trivi ellenpélda. Legyen

12/b' kérdés: a magasságkülönbségek összege lehet-e bármilyen egész szám 6 és 23 között?

12. kérdés: Legyenek a gyerekek magasságai \(\displaystyle M = \{m_i\}_i = \{-3,-2,-1,0,1,2,3\}\).

Egy üléssorrend során a magasságkülönbségek abszolút összege valami összeg amiben ezek a számok szerepelnek valamilyen előjelekkel; akik a szélén ülnek azok egyszer, akik középen, azok kétszer.

Világos, hogy \(\displaystyle 2 \cdot (0+1+1+2+2+3+3) - 1 - 0 = 23 \) -nál több nem lehet. (Mindenki pozitívan járul az összeghez 2x, a legkisebb abszolútértékűek meg csak 1x.) Az meg előáll úgy, hogy a két szélén a 0 és 1 ül, a többiek meg előjel szerint váltakozva, vagy a két szélén a 0 és -1 ül, a többiek meg előjel szerint váltakozva. Ezek mind maximálisak, és csak ezek.

12/b kérdés: Azt könnyű látni hogy a magasságkülönbségek összegének legkisebb értéke 6: sorban ülnek. Lehet-e bármilyen szám 6 és 23 között?

> A feladatot lehetne variálni. A kártya egyszeri használata marad, ám használat után az ATM blokkot ad, és akkor kiderül, milyen összeg volt a kártyán. (Esetleg csak pénz kifizetése esetén adja a blokkot.)

Ezeket a kártya információs variánsokat leöli amit 71-ben írtam (kb amit 69-ben te írtál). Még azt a variánst is, hogy Dagobert kevesebbet tud, nem tudja hogy egy kártya el lett-e fogadva, csak a legvégén.

Dagobert konstans stratégiája nem használ információkat, a bank meg tudja garantálni, hogy annál többet ne tudjon felvenni semmilyen információ birtokában.

A válasz a 12. kérdésre: 23

Bocs, de az MI-vel írattam egy programot erre a feladatra, és közlöm azt, mivel eddig még nem volt beküldő.

Íme a válasza:

A program lefuttatása alapján a maximális különbségek összege: 23. Az alábbi 48 permutáció adja ezt az összeget:

(133, 135, 131, 136, 132, 137, 134)

(133, 135, 131, 137, 132, 136, 134)

(133, 135, 132, 136, 131, 137, 134)

(133, 135, 132, 137, 131, 136, 134)

(133, 136, 131, 135, 132, 137, 134)

(133, 136, 131, 137, 132, 135, 134)

(133, 136, 132, 135, 131, 137, 134)

(133, 136, 132, 137, 131, 135, 134)

(133, 137, 131, 135, 132, 136, 134)

(133, 137, 131, 136, 132, 135, 134)

(133, 137, 132, 135, 131, 136, 134)

(133, 137, 132, 136, 131, 135, 134)

(134, 131, 136, 132, 137, 133, 135)

(134, 131, 136, 133, 137, 132, 135)

(134, 131, 137, 132, 136, 133, 135)

(134, 131, 137, 133, 136, 132, 135)

(134, 132, 136, 131, 137, 133, 135)

(134, 132, 136, 133, 137, 131, 135)

(134, 132, 137, 131, 136, 133, 135)

(134, 132, 137, 133, 136, 131, 135)

(134, 133, 136, 131, 137, 132, 135)

(134, 133, 136, 132, 137, 131, 135)

(134, 133, 137, 131, 136, 132, 135)

(134, 133, 137, 132, 136, 131, 135)

(134, 135, 131, 136, 132, 137, 133)

(134, 135, 131, 137, 132, 136, 133)

(134, 135, 132, 136, 131, 137, 133)

(134, 135, 132, 137, 131, 136, 133)

(134, 136, 131, 135, 132, 137, 133)

(134, 136, 131, 137, 132, 135, 133)

(134, 136, 132, 135, 131, 137, 133)

(134, 136, 132, 137, 131, 135, 133)

(134, 137, 131, 135, 132, 136, 133)

(134, 137, 131, 136, 132, 135, 133)

(134, 137, 132, 135, 131, 136, 133)

(134, 137, 132, 136, 131, 135, 133)

(135, 131, 136, 132, 137, 133, 134)

(135, 131, 136, 133, 137, 132, 134)

(135, 131, 137, 132, 136, 133, 134)

(135, 131, 137, 133, 136, 132, 134)

(135, 132, 136, 131, 137, 133, 134)

(135, 132, 136, 133, 137, 131, 134)

(135, 132, 137, 131, 136, 133, 134)

(135, 132, 137, 133, 136, 131, 134)

(135, 133, 136, 131, 137, 132, 134)

(135, 133, 136, 132, 137, 131, 134)

(135, 133, 137, 131, 136, 132, 134)

(135, 133, 137, 132, 136, 131, 134)

Tehát a maximális különbség összege 23, és több különböző permutáció is elérheti ezt az összeget. ​

Valóban: A 13.a állítás igaz 3-, 4-, 5-szögre, de 6-szögre már nem, mint azt az ellenpélda is mutatja.

Ami a 13.b kérdést illeti: A problémát (angolul: diameter of the flip graph) már megoldották az összes konvex sokszögre. A megoldók: Daniel Sleator, Robert Tarjan, William Thurston és Lionel Pournin.

A megoldás 3-szögre 0, 4-szögre 1, 5-szögre 2, 6-szögre 4, 7-szögre 5, 8-szögre 7 stb. (OEIS A005152).

De még vannak ezzel kapcsolatos megoldandó problémák. Például, hogy mekkora a legkisebb átlócserés lépéstávolság (flip distance) két tetszőleges háromszögelés között. Érdekes, hogy nyitott kérdés még ennek a számítástechnikai komlexitása is (P, NP-komplett, NP-hard?).

Bocs: 13.b a feladat... :)

Nem igaz, hogy \(\displaystyle n-3\) átlócsere elég lenne. A mellékelt ábra a példa rá. Ebben ugyanis a két háromszögelésben nincs közös átló, így az \(\displaystyle n-3\) lépés mindegyikében egy-egy átlónak a helyére kellene kerülnie. Viszont nincs olyan átlócsere (mondjuk a pirosból indulva), ami egy kék átlót hozna be. Úgyhogy akkor felmerül egy új kérdés (31.b): maximum hány átlócsere kell egy \(\displaystyle n\)-szög egyik háromszögelésének egy másikba való átalakítására?

A 13. kérdéshez csatlakozva, azt szigorítva, lehetne a 13.a kérdés:

Igaz-e, hogy a konvex n-szögben legfeljebb n-3 átlócserével bármely háromszögelésből bármely háromszögelést megkapjunk?

13. kérdés: A válasz igen.

Bizonyítás: Nyilván nincs jelentősége, hogy a sokszög szabályos legyen, elegendő az is, ha konvex, hogy tényleg belső háromszögek alakuljanak ki az átlók behúzásával. Azt fogjuk belátni teljes indukcióval, hogy minden háromszögelés átlócserékkel átvihető egy olyan háromszögelésbe, ahol az egyik kijelölt csúcsból induló átlókkal (és csak azokkal) háromszögeltük a sokszögünket. És ez elegendő a feladat állításának belátásához is, hiszen ha az első háromszögelést átalakítjuk így, akkor a második háromszögelés hasonló átalakítását visszafelé lejátszva megkapjuk a két háromszögelés egymásba alakítását.

Háromszögre az állítás triviálisan igaz. Tegyük fel, hogy \(\displaystyle n\)-szögekig igaz az állítás (\(\displaystyle n\geq 3\)). Jelöljük ki egy csúcsot egy \(\displaystyle (n+1)\)-szögben. Ha abból indul ki átló, az két részre bontja az \(\displaystyle (n+1)\)-szöget, az indukciós feltevés szerint azok átalakíthatóak úgy, hogy csak a kijelölt csúcsból induló átlók legyenek behúzva. Ha a kijelölt csúcsból nem indul átló, akkor a két szomszédos csúcs kell legyen átlóval összekötve, erre alkalmazzuk az átlócserét, és máris indul ki átló a kijelölt csúcsból. Ezzel beláttuk az állításunkat \(\displaystyle (n+1)\)-szögekre is.

Várhattam volna a Dagobert bácsis feladat megoldásával (69. hsz.), talán a 34. hozzászólásommal is ...

Most vannak válasz nélküli, megoldatlan kérdések, ha ezek elfogynak, hozok újakat.
Kíváncsi vagyok mi a válasz a 4 sakkos feladatra (8–11. kérdések), és azt hogyan indokoljátok. Én nem ismerem a válaszokat. A 12–13. megoldását ismerem, de csendben leszek ...

Hátha lesz még hozzászólás Dagoberthez is.

"Nézzük a bank startégiáját (Sinobi Gonosz manója)."

Ilyen is volt? Most valamiről lemaradtam.

Kicsit kár, hogy lelőtted, még mielőtt érkezett volna (jó) megoldás. (Engem különösen zavarnak a beküldött megoldásokban a feltevések a stratégiákat illetően, de ez lehet hogy csak az én vesszőparipám, hogy szeretem őket kimondva és belátva látni.) Biztosan van még másik bizonyítás is, szerintem például amit nadorp csinált is javítható.

Ez a bizonyítás működik kártyák tetszőleges \(\displaystyle d_1 >= d_2 >= .. >= d_n \) sorozatára. Jelölje \(\displaystyle A(d_i)\) azt az értéket, amit a Dagobert kap (a bank fizet), ha Dagobert minden körben \(\displaystyle d_i\)-t kér. (\(\displaystyle d_i\) egy kártyaérték.) Világos, hogy Dagobert el tudja érni \(\displaystyle A(d_i)\) maximumát a bank tetszőleges stratégiája esetén: minden körben \(\displaystyle d_i\)-t kér. Az is világos, hogy \(\displaystyle A(d_i)\) egy fix \(\displaystyle d_i\)-re úgy néz ki, hogy a \(\displaystyle d_i\)-nél nagyobbegyenlő értékű kártyák száma (jelölje \(\displaystyle N(d_i)\)), szorozva \(\displaystyle d_i\)-vel.

És az is teljesül, hogy ha a bank az általad felvázolt mohó stratégiát követi, akkor, Dagobert bármely stratégiájára valami \(\displaystyle A(d_i)\) értéknél nem többet fizet ki. Speciálisan az \(\displaystyle A(d_i)\) értékek maximumánál nem többet.

Még egyszer, a bank stratégiája: ha el tud utasítani, elutasít, ha el kell fogadnia, akkor a legnagyobb kártyával fogad el.

Ez elsőre furán néz ki, Dagobert 2-vel indít, és a bank ahelyett hogy kifizetné a 10-essel, inkább kidobja az 1-es kártyát. Mindenesetre ez egy jó stratégiája a banknak.

Bizonyítás: legyen G egy tetszőleges lejátszott játék, amit a bank e szerint a stratégia szerint játszott. Legyen \(\displaystyle d_i\) a legkisebb olyan kártya értéke, amellyel a bank fizetett valamennyit. Ekkor a bank nem használt \(\displaystyle d_i\)-nél kisebb kártyákat (mert \(\displaystyle d_i\) a legkisebb), és a bank nem fizetett \(\displaystyle d_i\)-nél többet (azt csak korábbi kártyával tehette volna meg, de akkor még megvolt a \(\displaystyle d_i\) értékű kártya, szóval el tudta volna utasítani a kérést). Tehát a bank maximum \(\displaystyle N(d_i)\)-szer fizetett egyáltalán, és minden körben maximum \(\displaystyle d_i\)-t, ez nem nagyobb, mint \(\displaystyle N(d_i) \cdot d_i = A(d_i)\).

És akkor nem is kellett számolni, mert csak azzal operáltunk, hogy milyen alakú Dagobert maxminje és a bank minmaxa.

Két új kérdés, a Héttusa feladataihoz csatlakozva.

Sokféle szép megoldás érkezett a 28-as feladatra.
28. A hét törpe körbeüli az asztalt, és Hófehérke mindegyiknek annyi cukorkát ad, ahány hüvelyk a különbség a törpe két szomszédjának magassága között. Legfeljebb hány cukorkát oszthat szét közöttük Hófehérke, ha a törpék magassága 31, 32, 33, 34, 35, 36 és 37 hüvelyk?

(Hasonló feladat a KöMaL-ban F.2280. és P.364.)

Mi a válasz, ha nem körben, hanem sorban állnak?

12. kérdés: Hét gyerek ül egy mozi nézőterén az első sorban egymás mellett. Ha kiszámoljuk a szomszédos gyerekek közti (pozitív) magasságkülönbséget, és ezeket összeadjuk, megkapjuk az ülésrend magasságát. Mekkora lehet ennek a magasságnak a legnagyobb értéke, ha a gyerekek magassága valamilyen sorrendben 131, 132, 133, 134, 135, 136 és 137 cm?

A Héttusa 33-as feladata:
33. Egy 12-oldalú szabályos sokszögnek legfeljebb hány átlóját tudjuk megrajzolni úgy, hogy bármelyik legfeljebb egy másikat metszhet a sokszög belsejében?

Várható egy hasonló kérdés a következő fordulóban is, most azt nézzük, hogy két háromszögelés között van-e 'átjárás'.

13. kérdés: Egy 12-oldalú szabályos sokszög egy háromszögelését megkapjuk úgy, hogy egymást nem metsző átlókat rajzolunk, összesen 9 átlót, és így a sokszöget háromszögekre daraboltuk.
Ha töröljük két szomszédos háromszög közös oldalát (egy átlót), akkor a két háromszög helyén egy négyszög keletkezik. Rajzoljuk meg a négyszög másik átlóját, így az előző háromszögelésből kaptunk egy új háromszögelést. Nevezzük ezt a műveletet átlócserének.
Igaz-e, hogy alkalmas átlócserékkel a sokszög bármelyik háromszögeléséből bármely másik háromszögelést megkaphatjuk?

7. kérdés, Dagobert bácsi.

Nézzük a bank startégiáját (Sinobi Gonosz manója). A bácsi megmondja mennyi pénzt akar felvenni, és odaad egy kártyát. A kártya értékét a bácsi nem tudja, így a bank választja meg, hogy azon milyen fedezet van.

(1) Ha a kért összegnél van kisebb értékű kártya, akkor azok egyike lesz a tranzakciónál használt kártya. Ez azt jelenti, hogy a bácsi nem kap pénzt, és ez a kártya már nem használható.

(2) Ha a kisebb értékű kártyák elfogytak, akkor a még érvényes kártyák közül a legnagyobb értékűt használjuk, és a bácsi megkapja a kért összeget.

A táblázat mutat egy példát a pénzfelvételre, a bank eljárására.

A kifizetett összegek közül válasszuk a legnagyobbat, \(\displaystyle m\)-et, és ha több ilyen összegű kifizetés van, akkor közülük az elsőt. Most \(\displaystyle m=5\).

Ez az \(\displaystyle m\) összeg kifizetésre került, tehát a nála kisebb értékű kártyák már elfogytak. (Ha lett volna ilyen kártya, akkor a bank ezt választja és nem fizet.)

A bank a kifizetéseknél a legnagyobb értékű kártyákat használja el, a (2)-es protokoll alapján. Tehát az \(\displaystyle m-1\) db kisebb értékű kártya felhasználásakor nem történt kifizetés.

Legfeljebb \(\displaystyle 10-(m-1)=11-m\) esetben történt kifizetés, és az ilyenkor fizetett összeg \(\displaystyle m\)-nél nem nagyobb.

Így az ATM-ből Dagobert bácsi legfeljebb \(\displaystyle (11-m)\cdot m\) ezer dollárt vehet ki. Mivel \(\displaystyle m\) egész szám, ezért a szorzat legnagyobb értékét \(\displaystyle m=5\), illetve \(\displaystyle m=6\) esetén kapjuk, ez a maximum 30 (ezer dollár).

A feladatot lehetne variálni. A kártya egyszeri használata marad, ám használat után az ATM blokkot ad, és akkor kiderül, milyen összeg volt a kártyán. (Esetleg csak pénz kifizetése esetén adja a blokkot.) Más változata az eredetinek, ha minden kártya kétszer használható.

Kiralynobol 14-et lehet felrakni (es szerintem ennyi a maximum is, de programmal vegignezve csak). Pelda 14-re:

*javítás:

Legyen inkább a susztermatt, mert azt a világos adja, és akkor n=4 lépésben van matt, 25 centet keresve. A lényeg ugyanaz.

Re64, re65.

Például legyen a tipp k=5 (ezer), és a még bent lévő kártyák 6,7,9 (ezer). Ekkor, ha a bank elfogad, akkor optimális stratégia szerint a 9 ezres kártyát használná fel a bank. Ha te azt mondod, hogy használjuk fel (mondjuk) a 6 ezrest, akkor tekintsd a még bent lévő kártyák rendezett sorrendjét, könnyen látható, ha nem opt stratégia szerint mész, akkor a te sorrendedben levő i-edik kártya legalább akkora mint az opt stratégia szerinti i-edik kártya, minden i-re. És minden lépésben csak veszítesz, legalábbis nem jársz jobban.

0 és 11 (ezres) tipp nem túl értelmes példa, ha 0-t mond akkor mindig el kell fogadni, 11 ezernél meg elutasítani. Ezt abból lehet könnyen látni, hogy 1-től 10 ezerig vannak a kártyák. Es ekkor persze a banknak sincs túl sok stratégiája, a játékos meg stabil nullát nyer. De mintha ezzel kezdtem volna az előző hozzászólásomat.

Meglepő, de értem a problémát. Ott van a hiba, hogy nagy ritkán teljesül az, hogy az optimális stratégia az a legjobb stratégia egy adott fix stratégia ellen. Példa1: fizetős gyors sakk játékomban a vesztes fizet \(\displaystyle \frac{1}{n}\) dollárt a győztesnek ha n-edik lépésben kap mattot, döntetlen esetén nincs fizetés. Gipsz Jakab ellen játszva észrevettem, hogy a bolondmattot nem ismeri, sőt mindig belemegy. Marha jó, n=2 lépésben mattot tudok adni, és betegre keresem magam a játékonkénti 50 centtel.

Megkeresett pénzből fölhalmozok jó sok kvantumbitet, sakk problémáját megoldom, kiderül, hogy tényleg a fehérnek van nyerő stratégiája, de csak h3-mal kezdve, és legrövidebben n=50 lépésben. Kiprintelem a teljes játékfát, megtanulom, és Carlsent legyőzöm az 50-dik lépésben, 2 centet keresve. Legyőzném-e n=2 lépésben? Aligha, sőt, mivel nem h3-mal kezdenék akkor nem is biztosan győznék.

Példa2: kő-papír-ollóra dettó ugyanez, (ebből egyébként világbajnokság is van). Egy forintot fizessen a vesztes játékonként, döntetlen esetén nincs fizetés. Mi itt az optimális nyerő stratégia? Ez a legjobb stratégia az ellen a játékos ellen is, aki mindig papírt mutat ?

Bőven lehet, hogy Dagobert stratégiája mondjuk olyan, hogy ha az 5-ödik lépésben elfogadja a bank a kérését, akkor utána feladja, és csak 0-t vagy 11-et kér. A banknak ilyenkor megérheti nem ellőni az összes nagy kártyát az elején, hogy el tudja fogadni az 5-ik kérést, és ne kelljen elutasítania.

Amúgy ha ezt

> Mit csinálhat a bank (ATM)? (Gonosz manó stratégiával): Ha a játékos (Dagobert) k (ezer) dollárt kér és a bank elfogadja az igényelt összeget, akkor ezt tegye úgy, hogy a legnagyobb még nem felhasznált kártyának tekinti a betett kártyát, feltéve hogy ez legalább k ezer dollár, ha ilyen nincs akkor mindenképpen elutasít a bank.

> Vagy a bank elutasítja a kártyát, ekkor a legnagyobb, de még k ezernél kisebb összegű kártyának tekinti a betett kártyát, ha ilyen nincs akkor mindenképpen el kell fogadni az igényelt összeget.

kihasználtad, akkor meg kéne indokolnod, hogy miért használhatod ki...

7. feladat (Dagobert bácsi 10 bankkártyája). Programmal: n=10 kártyára a 30000 dollár a maximum, és nadorp tippje n=25-ig biztosan igaz.

Trivi módon Dagobert csak k=1,2,..,n (ezer) dollárokat fog kérni (például 2650 dollár helyett jobb kérni 3000-et).

Mit csinálhat a bank (ATM)? (Gonosz manó stratégiával): Ha a játékos (Dagobert) k (ezer) dollárt kér és a bank elfogadja az igényelt összeget, akkor ezt tegye úgy, hogy a legnagyobb még nem felhasznált kártyának tekinti a betett kártyát, feltéve hogy ez legalább k ezer dollár, ha ilyen nincs akkor mindenképpen elutasít a bank.

Vagy a bank elutasítja a kártyát, ekkor a legnagyobb, de még k ezernél kisebb összegű kártyának tekinti a betett kártyát, ha ilyen nincs akkor mindenképpen el kell fogadni az igényelt összeget.

Hogyan lép a bank? Azt választja (elfogad/eluasít), amivel minél kevesebbet kell fizetni.

A játékos pedig azt a k értéket választja k=1,2,..,n közül, amire neki maximális(!) lesz a nyereménye. És ekkor persze a bank a számára minimálisan kifizetendő esetet választja.

"Csak" \(\displaystyle 2^{n}\) eset van, hiszen n darab bankkártyának ennyi részhalmaza van. Az alapeset amikor nincs már kártyája ekkor 0 a nyeremény. Egyébként pedig dinamikus programozással megoldható.

Bank persze játszhat nem optimális módon, tehát mégsem tudnánk, hogy milyen kártyáink vannak még, de ez a játékosnak csak jó, hiszen ekkor még többet nyerünk. Ugye itt kevert stratégiák is elképzelhetőek, de ez a számolást nem befolyásolja, hiszen optimális tiszta stratégia itt mindig lesz.