Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Héttusa feladatok

  [1]    [2]    [3]    [4]    [5]  

Szeretnél hozzászólni? Jelentkezz be.
[95] Káli gúla2024-08-25 23:41:23

8. kérdés. Királyok pontosan 2 ütéssel kérdésre a válasz 32. Több nem lehet, ez valamennyire pepecselős, de megoldható kézzel. Tegyük fel, hogy 33 király van a táblán, és mindegyik 2 másikkal szomszédos. Ekkor például a bal oldali féltáblán 16-nál, és pl. a bal felső negyedben 8-nál több bábu van. Felosztjuk a táblát 2x2-es kis négyzetekre az ábra szerint. Egy háromkirályos négyzet bábui ciklust alkotnak, az ilyen királyokkal szomszédos mezők mindig üresek. Emiatt 2 háromelemű négyzet nem lehet egymás mellett, ha pedig csúcsban találkoznának (pl. \(\displaystyle A,D\)), akkor a másik két négyzet (\(\displaystyle B,C\)) legfeljebb egyelemű lehetne. Tehát a bal felső negyedben csak 9=3+2+2+2 kiosztásban lehetnek bábuk. Sem \(\displaystyle |B|=3\), sem \(\displaystyle |C|=3\) nem lehet, mert abból \(\displaystyle |A|=1\) következne az a8 különleges helyzete miatt. Tehát vagy \(\displaystyle |A|=3\), vagy \(\displaystyle |D|=3\).

A középső ábra mutatja az \(\displaystyle |A|=3\) esetet. \(\displaystyle B\) csak a második oszlopában tartalmazhatja a két királyt, ekkor a d8 a másik szomszédos királlyal (e7 vagy e8) hármas ciklust alkot, így blokkolja a c6, d6 mezőket. Hasonlóan blokkolt a c5, c6 mezőpár is \(\displaystyle C\) oldaláról, tehát \(\displaystyle D\)-ben legfeljebb csak d5-ön lehetne bábu, ami viszont ellentmondás.

A jobb oldali ábrán látszik a \(\displaystyle |D|=3\) eset. Belátjuk, hogy \(\displaystyle |E|+|F|+|G|+|H|\le7\). Feltehetjük, hogy \(\displaystyle E,F,G,H\) egyike sem 3 elemű, mert \(\displaystyle E\) a \(\displaystyle C\)-beli, \(\displaystyle F\) a \(\displaystyle D\)-beli elrendezés miatt biztosan nem az, \(\displaystyle |H|=3\) esetén \(\displaystyle |F|\le1\) és \(\displaystyle |G|\le1\), tehát \(\displaystyle |E|+|F|+|G|+|H|\le7\) adódna, ha pedig \(\displaystyle |G|=3\) lenne, abból \(\displaystyle |E|=1\) és \(\displaystyle |H|=1\) vagy \(\displaystyle |F|=1\) következne, azaz ismét \(\displaystyle |E|+|F|+|G|+|H|\le7\) adódna. Ha tehát \(\displaystyle F,G,H\) kételeműek, akkor – ilyen sorrendben nézve – csak az ábra szerinti párokat tartalmazhatják. Így viszont b4-re nem kerülhet bábu, mert a2 árván maradna, tehát a5 csak a4-en, c3 csak b3-on folytatható, ami b3-nál hibához vezet. Ez ismét ellentmondás, ami tehát igazolja, hogy 32-nél több király nem lehet ezzel a tulajdonsággal.

A 32 király elérhető, de csak két körrel, a külső kör a sarkok nélkül 24 peremmezőből áll, a belső kör ugyanígy 8 mező a középső 4x4-es négyzet szélén. Összefüggő, húr nélküli királykör legfeljebb 31 elemű lehet, ezt megkapjuk, ha a 24 peremmezőből álló kört jobbról "benyomjuk" a h7-g6-f6-e6-d6-c5-c4-d3-e3-f3-g4-h3-h2 görbe mentén.

Ha viszont pontosan 2 helyett legfeljebb 2 ütést kívánnánk, akkor már lehet 33 király a táblán: az egyik sarok 3 szomszédján, és további három, ezzel párhuzamos, de sarok nélküli L-alakú csoportban.

Előzmény: [94] sakkmath, 2024-08-25 21:31:45
[94] sakkmath2024-08-25 21:31:45

Augusztus 2-án, szűkebb körben eljutott hozzám dr. Császár Gyula válasza az [57.hsz.]-ben látott 8. kérdésre. Azóta eltelt több, mint 3 hét, e körben nem találkoztam kiegészítéssel, cáfolattal, ezért most felteszem dr. Császár Gyula példával illusztrált, bizonyítandó állítását/sejtését:

Előzmény: [57] Róka Sándor, 2024-07-18 06:27:32
[93] Káli gúla2024-08-21 21:08:52

Az OEIS-ben található 26-os elrendezés: A051754

Előzmény: [87] Róka Sándor, 2024-08-19 16:02:41
[92] Róka Sándor2024-08-21 10:29:42

Hopsssz ...
Valóban. Nem vettem észre. Köszönöm.

A 27-esben és a törpésben is az a feladat, hogy az \(\displaystyle \{1, 2, 3, 4, 5, 6, 7\}\) halmaznak válasszuk ki a lehető legtöbb 3-elemű részhalmazát úgy, hogy bármely két részhalmaznak legfeljebb egy közös eleme legyen.

Van egy kedves élményem a feladatról.
A törpés feladatot elmondtam Danka Emmának (most volt hatodikos). Talán még magyaráztam volna, miről szól a feladat, de már jön is Emma a válasszal:

Legfeljebb 7 nap lehet. Ha a törpepárokat nézzük, 21 pár van. Egy pár legfeljebb egy hármasban lehet. Egy hármasban 3 db párost látunk. Ha a hármasok száma \(\displaystyle m\), akkor \(\displaystyle 3m\le21\), \(\displaystyle m\le7\).

A 27-es megoldása itt olvasható.

Előzmény: [89] UdvariTibor, 2024-08-21 09:30:38
[91] Sinobi2024-08-21 10:09:44

javítás: A hét törpe 21 párt alkot. Minden nap pontosan 3 pár marad otthon. 8 vagy több nap így nem lehet.

helyett legyen inkább

A hét törpe 21 párt alkot. Minden nap pontosan 3 pár marad otthon, minden pár maximum egyszer. 8 vagy több nap így nem lehet.

[90] Sinobi2024-08-21 10:06:55

Igen, ez megegyezik a 27-as feladattal, szöveg és megoldás: https://ematlap.hu/hettusa-2/1409-hettusa4-megoldasok-megjegyzesek .

Hét napra konstrukció: A "Fano sík" nevű kombinatorikai konstrukció, lásd ábra. A zöld pöttyök a törpék, és a 6 egyenes szakasz, illetve a kör által meghatározott hármasok maradnak otthon minden nap. Az ábráról leolvasható hogy ez jó. (Ábra a linkelt Érintő cikkből.) Bővebben: https://hu.wikipedia.org/wiki/Fano-sík

Hétnél több nap nem lehet: A hét törpe 21 párt alkot. Minden nap pontosan 3 pár marad otthon. 8 vagy több nap így nem lehet.

[89] UdvariTibor2024-08-21 09:30:38

Nekem elsőre úgy tűnik, ez megegyezik a Héttusa 27. feladattal - más szövegezéssel. Így legfeljebb 7 napig lehet így szervezni.

Előzmény: [88] Róka Sándor, 2024-08-19 16:17:23
[88] Róka Sándor2024-08-19 16:17:23

A Héttusa (Érintő) feladataiban felbukkant már a hét törpe (21. és 28. feladatok). Itt vannak ismét.

16. kérdés: A hét törpe közül naponta hárman otthon maradnak, és a többiek elmennek a bányába dolgozni. Arra vigyáznak, hogy bármely két naphoz legfeljebb egy olyan törpe legyen, aki mindkétszer otthon maradt.
Legfeljebb hány napig lehet így megszervezni a munkába járást?

[87] Róka Sándor2024-08-19 16:02:41

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?

Előzmény: [41] Róka Sándor, 2024-07-14 22:22:50
[86] Káli gúla2024-08-11 10:48:17

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. }\)

Előzmény: [81] Sinobi, 2024-08-07 10:11:39
[85] UdvariTibor2024-08-10 15:24:27

Lemaradt: a 14. kérdéshoz.

Előzmény: [84] UdvariTibor, 2024-08-10 15:23:28
[84] UdvariTibor2024-08-10 15:23:28

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

Előzmény: [83] Róka Sándor, 2024-08-08 01:01:52
[83] Róka Sándor2024-08-08 01:01:52

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.

Előzmény: [70] Róka Sándor, 2024-07-23 08:04:59
[82] Sinobi2024-08-07 10:20:02

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?

Előzmény: [81] Sinobi, 2024-08-07 10:11:39
[81] Sinobi2024-08-07 10:11:39

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?

Előzmény: [79] Keresztvölgyi József, 2024-07-31 16:04:33
[80] Sinobi2024-08-07 09:36:53

> 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.

Előzmény: [69] Róka Sándor, 2024-07-22 22:04:31
[79] Keresztvölgyi József2024-07-31 16:04:33

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. ​

Előzmény: [70] Róka Sándor, 2024-07-23 08:04:59
[78] Keresztvölgyi József2024-07-31 14:37:17

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?).

Előzmény: [76] Makay Géza, 2024-07-31 12:28:38
[77] Makay Géza2024-07-31 12:29:26

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

Előzmény: [76] Makay Géza, 2024-07-31 12:28:38
[76] Makay Géza2024-07-31 12:28:38

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?

Előzmény: [75] Keresztvölgyi József, 2024-07-27 13:53:05
[75] Keresztvölgyi József2024-07-27 13:53:05

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?

Előzmény: [74] Makay Géza, 2024-07-27 10:30:19
[74] Makay Géza2024-07-27 10:30:19

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.

Előzmény: [70] Róka Sándor, 2024-07-23 08:04:59
[73] Róka Sándor2024-07-23 18:39:27

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.

Előzmény: [71] Sinobi, 2024-07-23 14:14:49
[72] Róbert Gida2024-07-23 18:22:18

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

Ilyen is volt? Most valamiről lemaradtam.

Előzmény: [69] Róka Sándor, 2024-07-22 22:04:31
[71] Sinobi2024-07-23 14:14:49

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.

Előzmény: [69] Róka Sándor, 2024-07-22 22:04:31

  [1]    [2]    [3]    [4]    [5]