Darts: surranó nyilak, gondolkodtató problémák Kombinatorika 6. feladatcsomag

GONDOLKODÁSI MÓDSZEREK Kombinatorika

A 5.6

Darts: surranó nyilak, gondolkodtató problémák Kombinatorika 6. feladatcsomag Életkor:

15–18 év

Fogalmak, eljárások:

• összeszámolási módszerek (permutáció, variáció, kombináció) • sorozatok rekurzív megadása • programozás (egyszerű algoritmusok) • diofantoszi egyenletek (legnagyobb közös osztó)

A csomag első felében a játékos feladatok megoldása során összeszámolási feladatokat oldunk meg, illetve a kombinatorika klasszikus leszámolási módszereit gyakoroljuk (permutációk, variációk, kombinációk). Ezek között alkalmanként vannak nehezebbek is, például az ismétléses kombinációval is megoldható feladatok. Egy másik téma a rekurziós gondolatmenet alkalmazása. Ennek segítségével szintén egy összeszámolási módszert gyakorolunk. A csomag második felében számelméleti, oszthatósági problémák megoldására is sor kerül. Itt a nehezebb feladatok során szintetizáljuk a megismert módszereket, eljárásokat.

A feladatok listája 1. Nem a közepe ér legtöbbet? (szövegértés, tájékozódás a síkban, szisztematikus összeszámlálás, logikai következtetés)

Fejlesztő matematika (5–12. évf.)

1


A 5.6

2. Kidobhatatlan összegek a dartstáblán (rendszerezőképesség, összefüggéslátás, kombinativitás, algoritmikus gondolkodás) 3. A „kétmezős darts játék” általános vizsgálata (összefüggéslátás, analógiás gondolkodás, figyelem)

Módszertani tanácsok Az első feladatlapon egyszerű feladatokon keresztül ismerkedhetnek meg a tanulók a dartstáblával, annak különböző szektoraival. A második feladatlap a klasszikus darts játékkal kapcsolatosan tűz ki néhány problémát. A tanulók általában kedvelik a játékos jellegű feladatokat; a gyakorlati játékból származó példák pedig további motivációt is jelenthetnek. Az 1–4. feladat építkező jellegű, az első három feladat előkészíti a nehezebb negyediket. Ha a csoport tanulóinak nagyon eltérő a tudásszintje, akkor – természetesen – „ugorhatunk”, tehát a tehetségesebb tanulóknak rögtön, felvezetés nélkül kitűzhető a nehezebb 4. feladat (három dobásból el nem érhető összegek). A később hangsúlyozott rekurziós gondolatmenet már itt is megjelenik, hiszen a feladat viszonylag egyszerűbben oldható meg, ha a korábbi esetekre (egy, illetve két dobásból el nem érhető összegek) visszavezetjük. A feladatlap második felében a hagyományos összeszámolási megoldások mellett algoritmusokat is készítünk. (Erre óvatosan utaltunk a feladatok kitűzésekor.) Sajnos a tanulók programozási képessége, tudása egyre haloványabb; célszerű számukra minél több lehetőséget nyújtani algoritmusok, egyszerű programok készítésére. A programkészítés nemcsak az algoritmikus gondolkodást fejleszti, hanem gyakran alkalmazható konkrét célfeladatok megoldására is. (Az ebben az írásban szereplő egyszerű feladatok igen alkalmasak a gyakorlásra.)

2



A 5.6

Az egyszerű programok alkalmazásának több előnye is lehet, s ezekre példákat látunk a további feladatlapok megoldásakor is: • általában egyszerűen bővíthető az algoritmus (azaz kis változtatással minőségileg új feladatot oldhatunk meg); • egyszerűen változtatható a ciklusok futási száma (azaz több eset összeszámolása gyakran semennyivel sem jelent több munkát); • és – módszertanilag nagyon fontos – a futási eredmények ismeretében gyakran sejtéseket fogalmazhatunk meg: új megoldási módszerek adódnak, vagy új kérdések, problémák vetődnek fel. Az 5. feladatban hosszas esetszétválasztással, sok eset aprólékos vizsgálatával érünk célt. Ezekre sosem szabad sajnálni az időt. Sajnos, az egyre inkább eluralkodó „automatizmus”, a teszt-jelleg erősödése az iskolai feladattípusokban, a 6. és 8. osztályos felvételik (vagy akár részben az érettségi vizsga is) kvázi-teszt jellege, de általában az elektronikus munka megjelenése felületességre, sőt kapkodásra inspirál. Rendkívül fontos a részletes elemzéseken alapuló, megfontolt és türelmes munkavégzéstípus erősítése. A harmadik feladatlapon a speciális darts játék ürügyén számelméleti problémákat vizsgálunk. (És persze az egyes öszszeszámolások lehetőséget adnak a klasszikus kombinatorikai struktúrák [permutáció, kombináció] alkalmazására, gyakorlására is.) A számelméleti tartalmat (diofantoszi egyenletek, legnagyobb közös osztó) nem hangsúlyozzuk, hiszen erről igen részletesen olvashatunk a B 6.1 jelű, Lábak és pénzügyek (diofantoszi feladatok) című feladatcsomagban (Fried Katalin és Török Judit munkája). Ismét sor kerül a véges rekurziók alkalmazására és egyszerűbb programok írására. A rekurzív sorozatokat általában nem, vagy csak alig érintjük a tanítási órán, mert az explicit alak előállítása nehéz. Talán érdemes ezt a kimaradó témakört hangsúlyosabbá tenni a tanítás folyamán, mert egyrészt


3


A 5.6

a rekurzió felállítása szakmailag tanulságos, másrészt a számológép tetszőleges tagot pillanatok alatt előállít. (Azaz ebből a szempontból nincs szükség az explicit alakra.)

Megoldások, megjegyzések 1. Nem a közepe ér legtöbbet? 1. Jack Szállíven: T18, 9, kB (88 pont – 1. hely) Billy Coolhand: D8; 19; T15 (80 pont – 3. hely) Sam Reyoles: B, 12, D12 (86 pont – 2. hely) 2. A: Igaz, mert 3 páratlan szám összege páratlan volna. B: Hamis. A legnagyobb szimpla szektor 20-at ér. Szimpla értékekből legfeljebb 60 pontot lehet elérni. Ha a külső bullt szimpla értéknek tekintjük, akkor is csak 75 pont érhető el. C: Hamis. Két páros és egy páratlan összege páratlan volna. D: Igaz. 3 db D13 dobása esetén az összeg 78. 3. A legértékesebb szomszédos mező hármas: T19–T7–T16 8 4. a) 2, 3, 5, 7, 11, 13, 17, 19 a prím értékű mezők. Közülük e o 3 -féleképpen választható ki három. b) Igen, lehet, például 2 + 5 + 13 = 20. A 2-nek ott kell lennie a dobások között, különben a három páratlan prím öszszege páratlan lenne. A maradék 18 előállításai: 5 + 13, 7 + 11. Tehát 3 megoldás van. c) A 2, 5, 11, 17 értékek 2 maradékot adnak 3-mal osztva, a 7, 13, 19 számok 1 maradékot adnak. 1. eset: Ha a 3 a dobott számok között van, akkor az iménti két csoportból (maradékosztályok) egyet-egyet kell választani ahhoz, hogy az összeg 3 többszöröse legyen. Ez 4 · 3 =12 lehetőséget jelent. 2. eset: Ha a 3 nincs a dobott számok között, akkor a három számnak azonos maradékosztályból kell származ4 3 nia. Ez e o + e o = 5 lehetőséget eredményez. 3 3

4



A 5.6

Összesen tehát 17-féleképpen fordulhat elő, hogy a három különböző prím összege 20. 2. Kidobhatatlan összegek a dartstáblán 1. Elérhető 1-től 20-ig normál dobással minden szám, valamint 40-ig dupla szektoros dobással a páros számok, és 60ig triplával a hárommal oszthatók. Ezenkívül még a 25 és 50 pontos Bull-dobásokkal számolhatunk. 21 és 40 között 10 páratlan szám van (21, 23, …, 39), ezek közül minden harmadik, összesen 4 darab osztható 3-mal. Duplával és triplával nem érhető el a maradék 6 pontszám: 23, 25, 29, 31, 35, 37. 41 és 60 között 20 szám van, közülük minden harmadik osztható 3-mal: 42, 45, 48, …, 60. A többi 13 szám nem érhető el triplával. Az így kapott 19 érték között szerepel még a két Bull-dobás, tehát összesen 17 olyan szám van, amit egyetlen dartsszal nem lehet megdobni. Ezek halmaza: A = {23, 29, 31, 35, 37, 41, 43, 44, 46, 47, 49, 52, 53, 55, 56, 58, 59}. 2. A feladat első megközelítésben nehéznek tűnik, hiszen a frontális megoldás elég sok eset végigpróbálását jelentené. Próbáljunk olyan módszereket alkalmazni, amelyek egyszerre több szám kizárására is alkalmasak! Először megállapíthatjuk, hogy az A halmazbeli elemek mind előállíthatók két dobásból. Ugyanis két normál dobás minden összeget előállít 40-ig; egy D20-as és egy normál dobás pedig a 40, …, 60 sorozat számait állítja elő. Hasonló megfontolással egy T20 és egy normál dobással a 60, …, 80 számok érhetők el; így csak a 81, 82, …, 120 összegek előállítása a kérdés. Egy fontos észrevétellel tovább csökkenthetjük a vizsgálandó összegek számát. Ha az első dobás T20, akkor két dobással minden olyan összeg kidobható, amit az egy dobással elért szám 60-nal történő növelésével kapunk. Ily módon felhasználhatjuk az előző feladat eredményét: a két dobás-


5


A 5.6

ból nem elérhető pontszámok csakis az A halmaz 60-nal megnövelt elemei közül kerülhetnek ki. A H1 = {83, 89, 91, 95, 97; 101, 103, 104, 106, 107, 109, 112, 113, 115, 116, 118, 119} halmaz még mindig „túl nagy” a rendszeres próbálgatáshoz, célszerű tovább csökkenteni a vizsgálandó elemek számát. Ha az első dobás például T19, akkor a két dobással így nem elérhető összegek H2 halmaza a H1 halmaz elemeinél 3-mal kisebb számokból áll: H2 = {80, 86, 88, 92, 94; 98, 100, 101, 103, 104, 106, 109, 110, 112, 113, 115, 116, 118, 119, 120}. (Mivel T19 + T20 = 117, a 118, 119, 120 számokat is belevettük H2-be.) A H1 + H2 = {101, 103, 104, 106, 109, 112, 113, 115, 116, 118, 119} halmaz pedig az egyik kezdéssel sem elérhető számokat tartalmazza. 11 szám maradt. Végezzük el még a T18-as kezdés vizsgálatát is: Ha az első dobás T18, akkor a két dobással ily módon nem elérhető összegek H3 halmaza a H2 halmaz elemeinél 3-mal kisebb számokból áll (valamint a T18 + T20 = 114-nél nagyobb számokból). H3 = {77, 83, 85, 89, 91; 95, 97, 98, 100, 101, 103, 106, 107, 109, 110, 112, 113, 115, 116, 117, 118, 119, 120}. Most is képezzük az újabb halmazmetszetet: H1 + H2 + H3 = {101, 103, 106, 109, 112, 113, 115, 116, 118, 119}; ez a 10 szám az eddigi kezdésekkel nem érhető el. Az utolsó lépés már nem volt hatékony, próbáljuk más módszerrel kizárni az elérhetetlen számokat. Két dobásból 100 pont fölé jutni csak úgy lehet, ha legalább az egyik dobás tripla. (Két Bull, valamint egy dupla és egy Bull összege is kisebb, mint 101.) Két tripla dobás összege 3-mal osztható szám. Mivel ilyen nincs a H1 + H2 + H3 halmazban, csak azokat a dobáspárokat kell vizsgálnunk, amelyekben pontosan egy tripla van.

6



A 5.6

Mivel egy tripla és egy dupla összege sem nagyobb 100nál, csak egy tripla és egy Bull dobástól várhatjuk, hogy öszszegük a halmaz valamely elemét adja. Az ilyen összegek 3-mal osztva 2 maradékot adnak, ezek a 101, 104, 107, 110. Közülük a 104 még H2-ben benne volt, de H3-ba már nem került be; a H1 + H2 + H3 halmazból még a 101-et zárhatjuk ki. (101 = Bull + T17). Eredmény: 9 olyan 121-nél kisebb szám van, amit két dobásból nem lehet elérni. Ezek: B = {103, 106, 109, 112, 113, 115, 116, 118, 119}. 3. Ha az egyik dobás 50-es Bull vagy kisebb értékű, akkor a maradék 123 pont túl sok, két dobásból nem érhető el. Minden dobásnak tehát 50-nél nagyobb triplának kell lennie. A tripla találatok összegei oszthatók 3-mal, míg a 173-ra ez nem igaz. Ezért a 173 pont valóban nem állítható elő három dobásból. 4. Az előző két eset vizsgálatakor alkalmazott gondolatmenetek most is alkalmazhatók. Minden olyan érték elérhető három dobásból, amit a két dobásból elért számok T20 = 60-nal történő növelésével kapunk. Ha tehát valamely érték nem érhető el három dobásból, akkor ennek a két dobásból el nem érhető számok (a B halmaz elemei) 60-nal megnövelt értékei között kell lenni. A B halmaz elemeit 60-nal megnövelve a C = {163, 166, 169, 172, 173, 175, 176, 178, 179} halmazt kapjuk; ezek között vannak tehát a három dobásból nem elérhető számok is. Ha csak egy triplát dobunk (maximum 60 pont), akkor a C elemei két további dobásból már nem állíthatók elő, hiszen ezek összege legfeljebb 100 lehet. Ha három triplát dobunk, ezek összege 3-mal osztható, de ilyen szám nincs a C elemei közt. Marad a pontosan két tripla esete. Ha a harmadik dobás dupla, az összeg kevés (legfeljebb T20 + T20 + D20 = 160);


7


A 5.6

vagyis két tripla és egy Bull zárhat ki további elemeket a C halmazból. Két tripla és egy Bull a T20 + T20 + B = 170 ponttal végződő számokat állítja elő: 170, 167, 164, 161… Ilyen szám nincs a C halmazban. Eredmény: 9 olyan 181-nél kisebb szám van, amit három dobásból nem lehet elérni. Ezek: C = {163, 166, 169, 172, 173, 175, 176, 178, 179}. Egy kis programozás Az algoritmus szerkesztésekor eljárhatunk úgy, hogy először az 1 dobásból el nem érhető számokat keressük meg; majd ezek ismeretében a 2 dobásból nem kidobható öszszegeket határozzuk meg; végül ezek segítségével megadjuk a 3 dobásból el nem érhető összegeket. Egy lehetséges eljárást megadunk az alábbiakban. (Ez könnyen bővíthető lesz a 2, illetve 3 dobás esetére is.) Az 1 dobásból elérhető számokat megadja az S = n · x + d · 2x + t · 3x + k · 25 + b · 50 összeg (változó) értéke, ahol n, d, t, k, b rendre a normál, dupla, tripla, külső Bull és Bull dobások számát jelenti, x pedig 1-től 20-ig futó ciklusváltozó. (Természetesen 1 dobás esetén az n + d + t + k + b összeg értéke pontosan 1, azaz a négy változóból az egyik mindig 1, a többi zérus.) Megtehetnénk, hogy x minden ciklusában rendre az n = 1, majd d = 1, …, b = 1 értékekkel meghatározzuk S aktuális értékét, de – kicsit bonyolultabban, viszont talán tovább fejleszthető módon – egymásba skatulyázott ciklusokat is alkalmazhatunk. A külső ciklusban n fut 0-tól 1-ig, a belső ciklusban d fut 0-tól (1 – n)-ig, az eggyel mélyebbre ágyazott ciklusban t fusson 0-tól (1 – n – d)-ig és így tovább. Ezzel elérjük, hogy az öt ciklusváltozó összege 0 vagy 1 lesz (persze amikor mindegyik zérus, akkor az S = 0 jellegtelen érték adódik).

8



A 5.6

N Megjegyzés: Ezzel a módszerrel valójában az = G ismétléK ses kombináció eseteit járjuk végig, most speciálisan az N N 5 = G = e o = e o eseteket. 1 1 1 Definiálunk tehát egy összeg1() tömböt a kidobható számok jelölésére. Kezdetben a tömb elemeit lenullázzuk, és amikor valamelyik S értéket kiszámoltuk, összeg1(S)-et 1-re állítjuk. (Ezzel jelezzük, hogy az S érték kidobható.) Végezetül kiíratjuk az összeg1() azon értékeit, amelyek nullák; ezek lesznek a nem elérhető számok. Az algoritmus: Ciklus i:=0-tól 60-ig összeg1(i):=0 Ciklus vége Ciklus x:=1-től 20-ig Ciklus n:=0-tól 1-ig Ciklus d:=0-tól 1–n-ig Ciklus t:=0-tól 1–(n+d)-ig Ciklus k:=0-tól 1-(n+d+t)-ig Ciklus b:=0-tól 1-(n+d+t+k)-ig S:=n∙x+d∙2∙x+t∙3∙x+k∙25+b∙50 összeg1(S):=1 Ciklus vége Ciklus vége Ciklus vége Ciklus vége Ciklus vége Ciklus vége Ciklus i:=0-tól 60-ig Ha összeg1(i)=0 akkor Ki:i Ciklus vége

A program futási eredményét táblázatba foglalhatjuk. [Tehát ezen i értékekre összeg1(i) = 0, azaz az 1 dobásból nem kidobható számokat kapjuk meg.]


9


A 5.6

összeg1: i

23 29 31 35 37 41 43 44 46 47 49 52

53 55 56 58 59 A 2 dobásból ki nem dobható összegeket úgy kaphatjuk meg, hogy az összeg1() elemeit páronként összeadjuk, és az így kapott értékeket egy összeg2() tömbben kigyűjtjük. Ezt megtehetjük például úgy, hogy az összeg2() megfelelő indexű elemeit 1-re állítjuk. (Kezdetben persze lenullázzuk a tömb elemeit.) Az első programrészhez csatlakoztatott algoritmus: Ciklus i:=0-tól 120-ig összeg2(i):=0 Ciklus vége Ciklus i:=0-tól 60-ig Ciklus j:=0-tól 60-ig Ha összeg1[i]=1 és összeg1[j]=1 akkor összeg2[i+j]:=1 Ciklus vége Ciklus vége Ciklus i:=0-től 120-ig Ha összeg2(i)=0 akkor Ki:i Ciklus vége

A futási eredmény már ismert, korábban meghatároztuk azt a 9 számot, amelyek nem dobhatók ki két nyíllal: összeg2: i 103 106 109 112 113 115 116 118 119 Végül a programot a korábbihoz hasonlóan kiegészítjük azzal a résszel, amely az összeg3() tömbben kigyűjti a három dobással elő nem állítható összegeket.

10



A 5.6

Ciklus i:=0-tól 180-ig összeg3(i):=0 Ciklus vége Ciklus i:=0-tól 60-ig Ciklus j:=0-tól 120-ig Ha összeg1[i]=1 és összeg2[j]=1 akkor összeg3[i+j]:=1 Ciklus vége Ciklus vége Ciklus i:=0-től 180-ig Ha összeg3(i)=0 akkor Ki:i Ciklus vége

A futási eredmény: összeg3: i 163 166 169 172 173 175 176 178 179 (Egyszerűen összeadtuk a 2 és az 1 dobásból elérhető számokat.) Természetesen lehet egyszerűbb algoritmust írni a feladatra [és például a 0-1 értékű összeg() tömbök helyett sokkal elegánsabb lett volna logikai tömböket alkalmazni], de ez az algoritmus könnyen kódolható, egyszerűen bővíthető, és a kis számok miatt nem volt szükségünk hatékonyabb eljárásra sem. Befejezésül még megadjuk azokat az összegeket, amelyekről kiderült – az algoritmus további bővítése során –, hogy nem dobhatók ki 4 dartsszal. összeg4: i 223 226 229 232 233 235 236 238 239 5. Rendszeres esetszétválasztást végzünk a tripla dobások száma alapján. 1. eset: Ha nyolc dobás tripla. Ekkor a nyolc dobás maximális összege 8 · 60 = 480, tehát a dupla dobásnak legalább 22-nek kell lennie. Mivel a kilenc dobás összege (501) is osztható hárommal, és a 8 tripla do-


11

GONDOLKODÁSI MÓDSZEREK

A 5.6

Kombinatorika

bás összege is, ezért csak a 3-mal osztható dupla befejezések jöhetnek szóba. Ezek a 24, 30, 36; és ekkor a triplákkal elérendő összeg rendre 477, 471, 465. Ezek harmadrésze 159, 157, 155; ezen összegeket kell „normál szektorú” dobásokból előállítani. A 159 hét darab 20-as és egy 19-es összegeként állítható elő. A 157-es összeg 2-vel kevesebb, így a 19-est cserélhetjük egy 17-esre, vagy egy 20-ast 18-asra és így tovább. A lehetőségeket érdemes táblázatban összefoglalni: 159 (8 triplával: 477, kilépő dobás: D12) 7 db 20 1 db 19 157 (8 triplával: 471, kilépő dobás: D15) 7 db 20 6 db 20 5 db 20 1 db 17 1 db 19 3 db 19 1 db 18 155 (8 triplával: 465, kilépő dobás: D18) 7 db 20 6 db 20 6 db 20 1 db 15 1 db 19 1 db 18 1 db 16 1 db 17 5 db 1 db 2 db

20 19 18

4 db 3 db 1 db

20 19 18

3 db 5 db

5 db 2 db 1 db

20 19 17

20 19

A 159 előállításakor 6 darab (vagy kevesebb) 20-as nem elég: 2 · 19 = 38, és 38 + 6 · 20 = 158 < 159. A 157 előállításakor 4 darab (vagy kevesebb) 20-as nem elég: 4 · 19 = 76, és 76 + 4 · 20 = 156 < 157. A 155 előállításakor pedig 2 darab (vagy kevesebb) 20-as szintén nem elég: 6 · 19 = 114, és 114 + 2 · 20 = 154 < 155.

12



A 5.6

Meg kell még vizsgálni, hogy a kilencedik dupla dobás lehet-e Bull, de nem: ekkor a számok összege nem lenne osztható 3-mal. 2. eset: Hét dobás tripla. Ezek maximális összege 7 · 60 = 420, tehát legalább 81 pontot kell a két további dobásból előállítani. A két további dobás összegének oszthatónak kell lennie 3-mal, mert az 501, valamint a hét tripla összege is osztható 3-mal; tehát két Bull nem jöhet szóba. Mivel két dupla összege legfeljebb 80, a maradék két dobás csak egy dupla és egy Bull lehet. Ráadásul ezek összege osztható 2-vel, így a lehetőségek: 84, 90, 96, … További szűkítés, hogy egy Bull és egy dupla összege legfeljebb 90; így két eset maradt, a 84 és a 90. Ez elő is állhat: 84 = B + D17 és 90 = B + D20. Ekkor a triplákkal elért összeg 417, illetve 411. A könnyebb számolás kedvéért ismét meghatározzuk ezek harmadrészét: 139, illetve 137 adódik. A lehetséges eseteket ismét táblázatba foglaltuk: 139 (7 triplával: 417, továbbá egy Bull és egy D17, utóbbiak egyike a kilépő dobás) 6 db 20 1 db 19 137 (7 triplával: 411, továbbá egy Bull és egy D20, utóbbiak egyike a kilépő dobás) 6 db 20 5 db 20 4 db 20 1 db 17 1 db 19 3 db 19 1 db 18 Ismét könnyen igazolható, hogy több megoldás nincs. A 139 előállításakor 5 darab (vagy kevesebb) 20-as nem elég: 2 · 19 = 38, és 38 + 5 · 20 = 138 < 139. Hasonlóan a 137 előállításakor 3 darab (vagy kevesebb) 20as nem elég: 4 · 19 = 76, és 76 + 3 · 20 = 136 < 137. Fejlesztő matematika (5–12. évf.)

13


A 5.6

3. eset: Hat dobás tripla. Hat darab T20-as összege 360, a maradék 141 pontot kell három dobásból előállítani. Ezek között normál dobás nem lehet, hiszen ezek értéke legfeljebb 20, és a maradék 141 – 20 = 121 pont két nemtripla dobással nem érhető el. Ha a három dobás valamelyike külső Bull, akkor 141 – 25 = 116 pontot kellene elérni két nem tripla dobással, de ez láthatóan nem lehetséges. A három nem tripla dobás tehát csak Bull és dupla lehet. Mivel ezek összege páros, és a 3-mal való oszthatóság továbbra is fennáll, a 144, 150, 156, … sorozat elemei közül kerülnek ki a szóba jöhető összegek. Három Bull megfelelő (3 · 50 = 150 pont), de két Bull nem lehetséges: ekkor ugyanis 44 vagy több pontot kellene elérni a két duplával. (Hasonlóan nem lehet 0 vagy 1 Bull sem: három duplával a 144, két duplával a 94 pont nem elérhető.) A hat triplával 501 – 150 = 351 pontot kell elérni. Ennek harmada 117; ezek felbontását a hagyományos módon táblázattal adjuk meg. 117 (6 triplával: 351, ezek mellett 2 Bull, kilépő dobás: Bull) 5 db 20 4 db 20 3 db 20 1 db 17 1 db 19 3 db 19 1 db 18 Több megoldás nincs, 2 darab (vagy kevesebb) 20-as nem elég: 4 · 19 = 76, és 76 + 2 · 20 = 116 < 117. 4. eset: Öt dobás tripla. Ezek összege legfeljebb 300, a maradék elérendő összeg legalább 201. Ezt 4 további dobással már nem érhetjük el, 4 Bull összege is csak 200. A gondolatmenetből az is látszik, hogy ötnél kevesebb tripla dobás esetén sincs megoldás. Összefoglaljuk a kilenc nyilas „501 dupla ki” játék lehetséges megoldásait. Az egyes típusok mellett felsoroljuk azt is, 14



A 5.6

Kombinatorika

hogy az aktuális típus hányféleképpen fordulhat elő. (Ekkor az egyes sorozatok ismétléses permutációinak a számát kell meghatároznunk, figyelve arra, hogy dupla vagy Bull dobással végződjön a sorozat. A lehetséges záródobásokat vastagabb betűk jelölik.) Típus

Esetszám

7 db T20, T19, D12

8

7 db T20, T17, D15

8

6 db T20, T19, T18, D15

8! = 8 $ 7 = 56 6!

5 db T20, 3 db T19, D15

8 e o = 56 3

7 db T20, T15, D18

8

6 db T20, T19, T16, D18

56

6 db T20, T18, T17, D18

56

5 db T20, T19, T19, T17, D18

8! = 168 5! $ 2!

5 db T20, T19, T18, T18, D18

168

4 db T20, 3 db T19, T18, D18

8! = 280 4! $ 3!

3 db T20, 5 db T19, D18

56

6 db T20, T19, B, D17

56 + 56 = 112

6 db T20, T17, B, D20

112

5 db T20, T19, T18, B, D20

8 · 7 · 6 · 2 = 672

4 db T20, 3 db T19, B, D20

280 · 2 = 560

5 db T20, T17, 3 db B

8! = 168 5! $ 2!

4 db T20, T19, T18, 3 db B

8! = 840 4! $ 2!


15


A 5.6

Kombinatorika

3 db T20, 3 db T19, 3 db B

8! = 560 3! $ 3! $ 2!

Összesen:

3944

Például a 4 db T20, 3 db T19, B, D20 típus előfordulásainak számát a következőképpen kapjuk meg: Ha D20 az utolsó dobás, akkor 4 db T20, 3 db T19 és B lehetséges sorrendjeinek (az ismétléses permutációknak) a száma 8! = 8 $ 7 $ 6 $ 5 = 280 , és ugyanennyi sorrendet kapunk 4! $ 3! 6 akkor is, ha B az utolsó dobás. Eredmény: 280 · 2 = 560. 3. A „kétmezős darts játék” általános vizsgálata 1. A 6-os dobásokból a 6 többszörösei, a 11-es dobásokból pedig a 11 többszörösei dobhatók ki. Ha az első kezdőszámokat megvizsgáljuk, ritkábban találunk elérhető (a továbbiakban „jó”) számot, később ezek sűrűsödnek. Nem jó szám az 1, 2, 3, 4, 5, 7, 8, 9, 10, 13, 14, 15, 16, 19, 20, …; jó számok a 6, 11, 12, 17, 18, 22, 23, 24, 28, 29, 30, 33, … Ha a kidobható számok sorozatát „folyamatában” vizsgáljuk, akkor egy fontos észrevételt tehetünk: ha valamelyik szám megfelelő, akkor a nála 6-tal (vagy 11-gyel) nagyobb szám is jó lesz. (Eggyel több 6-os vagy 11-es szerepel az előállító összegben.) Azaz egy jó szám megtalálása után a megfelelő 6-os maradékosztály összes eleme előállítható. Ez alapján csak keresni kell a 6-tal osztva 0, 1, 2, 3, 4, 5-ös maradékosztályokban egy-egy számot (lehetőleg a legkisebbet a maradékosztályban); ha mindegyikben találunk ilyet, akkor kész vagyunk: „egy idő után”, azaz egy bizonyos számtól kezdve minden összeg előállítható lesz. A 0 maradékosztályban megfelelő szám a 6 (vagy maga a 0); az 5 maradékosztályban a 11; 22 maradéka 6-tal osztva 4, tehát 22 jó lesz a 4-es maradékosztály kezdőszámának. 3 maradékot ad a 33, 2 maradékot pedig a 44. Végül 55 az utolsó, 1-es maradékosztályt is lefedi.

16



A 5.6

maradék (mod 6) 0 1 2 3 4 5 kezdőszám 0; 6 55 44 33 22 11 A táblázat alapján kidobhatók a következő összegek: – 6, 12, 18, … (azaz a 6k alakú számok, k = 1, 2, 3, …; illetve a k = 0 esetet is ide sorolhatjuk); – 55, 61, 67, … (6k + 1 alakú számok, k = 9, 10, 11, …); – 44, 50, 56, … (6k + 2 alakú számok, k = 7, 8, 9, …); – 33, 39, 45, … (6k + 3 alakú számok, k = 5, 6, 7, …); – 22, 28, 34, … (6k + 4 alakú számok, k = 3, 4, 5, …); – 11, 17, 23, … (6k + 5 alakú számok, k = 1, 2, 3, …). Látható, hogy 55-től kezdve minden összeg elérhető; sőt azt is sejthetjük, hogy az 55 – 6 = 49 a legnagyobb olyan összeg, amit nem lehet kidobni ezen a kétszektoros „darts” táblán. A sejtés bizonyítása nem is nehéz: A 6-os dobások nem változtatják meg az összeg 6-tal való osztási maradékát, azaz az osztási maradék csak a 11-es dobások számától függ. Fentebb az egyes maradékosztályok kezdőszámait úgy képeztük, hogy rendre vettük az 1 · 11, 2 · 11, 3 · 11, 4 · 11, 5 · 11 (és esetleg ide sorolhatjuk a 0 · 11-et is) kezdőszámokat. Történetesen ezek mind különböző maradékokat adtak 6-tal osztva, az ismétlődés hiánya pedig éppen azt jelenti, hogy mindegyik esetben a lehető legkisebb kezdőszámát kaptuk meg a maradékosztálynak. Ebből már következik, hogy a fenti sorozat az egyes maradékosztályok legkisebb jó számait állítja elő. A maradékosztályonkénti legnagyobb rossz számokat a fenti sorozat 6-tal csökkentett értékei adják meg. Ezek rendre: 1 · 11 – 6 = 5, 2 · 11 – 6 = 16, 3 · 11 – 6 = 27, 4 · 11– 6 = 38, 5 · 11 – 6 = 49. Most már válaszolhatunk a feladat kérdésére: ezen a darts táblán a legnagyobb, nem elérhető összeg a 49. Megjegyzés: Hasonló eredményt kapunk akkor is, ha nem a 6-tal, hanem a 11-gyel való oszthatóság alapján osztályozzuk a számokat. Ekkor az egyes (mod 11) maradékosztályok


17


A 5.6

kezdőszámai és legnagyobb nem elérhető számai az alábbiak: maradék kezdőszám legnagyobb nem elér(mod 11) hető összeg 0 0, 11 1 12 1 2 24 13 3 36 25 4 48 37 5 60 49 6 6 7 18 7 8 30 19 9 42 31 10 54 43 Természetesen most is a 49 a legnagyobb nem elérhető összeg, azaz a feladat megoldása. 2. A mod 6 maradékosztályok alapján egyszerű összeszámolást végezhetünk. maradék kezdőszám nem elérhető öszdb (mod 6) szegek 0 0, 6 1 55 1, 7, …, 49 9 2 44 2, 8, …, 38 7 3 33 3, 9, …, 27 5 4 22 4, 10, 16 3 5 11 5 1 Összesen 25 nem elérhető összeg van. 3. Az előző feladatban megmutattuk, hogy a legnagyobb nem elérhető összeg a 49; ebből következik, hogy a határ18



A 5.6

szám 50. (Általában is igaz, hogy a határszámnál eggyel kisebb szám nem elérhető.) Az 50 maradéka 6-tal osztva 2, tehát az előállításához szükség van 44 = 4 · 11 miatt 4 darab 11-es dobásra. Ekkor adódik, hogy csak egyetlen további 6-os dobás kell. A 4 darab 11-es és 1 darab 6-os dobások összesen 5-féleképpen következhetnek, így az 50 határszám pontosan 5-féleképpen dobható ki. 4. a) A 100 maradéka 6-tal osztva 4, így szükség van 2 darab 11-es dobásra. 100 – 2 · 11 = 78 = 6 · 13, tehát egy megoldást a (6; 11) " (13; 2) számpár ad. (Az első szám mindig a kisebb, 6-os dobások darabszámát jelöli, míg a második a 11-esek számát.) Másik megoldást kapunk, ha észrevesszük, hogy 6 darab 11-es dobás nem változtatja meg az összeg 6-os maradékát. (Úgy is fogalmazhatunk, hogy 11 darab 6-ost kicserélhetünk 6 darab 11-esre.) Ekkor a (2; 8) megoldást kapjuk, és valóban: 2 · 6 + 8 · 11 = 100. Több előállítási lehetőség nincs. Általában az (x; y) számpárral adott x és y darab egyforma objektum összes lehetséges sorrendjét, azaz az ismétléses permutációinak a számát az (x + y) ! képlet adja meg. Ez alapján a 100-as összeg x! $ y! 15! + 10! = 105 + 45 = 150 -féleképpen állítható elő. 13! $ 2! 8! $ 2! Egy másik okoskodás az lehet, hogy az x + y darab összeadandóból kiválasztjuk például az x darab első típusút. (Az első példánál maradva a 15 összeadandóból kiválasztjuk azt a 13-at, amelyik a 6-os lesz.) Mivel a kiválasztott elemek sorrendje nem számít, az elemek egy kombinációját kapjuk. (x + y) elemből x darabot x+y e o -féleképpen választhatunk ki. [Természetesen x x+y (x + y) ! . Nagyobb számok számológépes kie o= x! $ y! x Fejlesztő matematika (5–12. évf.)

19


A 5.6

Kombinatorika

számolása esetén talán könnyebb a kombinációk számának meghatározása; erre sok gépen külön funkcióbillentyű van.] b) A 200 maradéka 6-tal osztva 2, így 4 darab 11-es dobásra van szükség. 200 – 44 = 156; ekkor 26 darab 6-os dobásra van szükség. A lehetőségeket és az előállító utak számát az alábbi táblázatban tüntettük fel. 6-os 11-es dobások dobások

sorrendek száma

26

4

30! = 30 $ 29 $ 28 $ 27 = 27 405 26! $ 4! 24

15

10

25! = e25 o = 3 628 760 15! $ 10! 10

4

16

e

20 o = 4845 4

Érdekes, hogy a 200 előállítási számára – a 100-hoz képest – egy irdatlan nagy értéket kaptunk (27 405 + 3 628 760 + 4845 = 3 661 010). Ha a fenti, rendkívül egyszerű dartstáblán két játékos egyaránt 200 pontot is ér el, rendkívül valószínűtlen, hogy egyformán játszottak… Második megoldási lehetőség (útmutatás): Az a) feladat megoldása két részből állt. Az első lépésben meghatároztuk, hogy milyen típusú előállítások vannak; ehhez megállapítottuk a 6x + 11y = 100 egyenlet (x, y ! N) megoldásszámát. [(x, y) = (13, 2) vagy (x, y) = (2, 8).] A feladat hátterében tehát a fenti, úgynevezett diofantoszi egyenlet megoldása szerepel, amelynek általános megoldására többféle módszer is ismert. [Ezeket részletesen tárgyalja a B 6.1 jelű, Lábak és pénzügyek (diofantoszi feladatok) című feladatcsomag.]

20



A 5.6

A második lépésben azt számítottuk ki, hogy a kapott típusok hányféle sorrendben fordulhatnak elő. Ez egyszerű, tisztán kombinatorika feladat, ismétléses permutáció vagy kombináció alkalmazásával. Harmadik megoldási lehetőség: Rekurziót is alkalmazhatunk. Ennek során igyekszünk a korábbi, kisebb öszszegekre kapott előállítások számát felhasználni a nagyobb összegek előállításánál. Jelölje f(i) az i összeg előállításainak a számát, a feladat tehát f(100) meghatározása. Az f(0), f(1), f(2), … , sorozat kis elemszámú tagjainak értékeit könnyen meghatározhatjuk. f(0) = f(6) = f(12) = 1, f(11) = 1, míg a többi, 12-nél kisebb kezdőtag zérus: f(1) = f(2) = … = f(10) = 0. (Ez azt jelenti, hogy a 6, 11, 12 számok egyféleképpen érhetők el, míg a többi 12-nél kisebb szám nem dobható ki.) Hasonlóan 1-értékűek az f(18) = f(24) = … = f(60) vagy az f(22) = f(33) = f(44) = f(55) tagok is. Az első olyan eleme a sorozatnak, amelyik 1-nél nagyobb, a 17-dik. f(17) = 2, mert a 17 elérhető 6 + 11 és 11 + 6 dobásokkal is. Hogyan tudunk valamilyen általános összefüggést felírni a sorozat tagjaira? Hogyan tudjuk az általános n-edik tagot kifejezni a korábbiak segítségével? Az utolsó dobás vagy 6-os volt, vagy 11-es. Ezért az n-edik tagot, azaz az n összeget az (n – 6). és az (n – 11). tagok összegeként állíthatjuk elő. Ugyanis az utolsó dobás öszszegét vagy a 6-tal kisebb, vagy a 11-gyel kisebb összeg növelésével kaphatjuk meg; ezeket pedig f(n – 6), illetve f(n – 11) módon érhettük el. Tehát az f(n) = f(n – 6) + f(n – 11) rekurzív sorozat 100., illetve 200. tagját kell meghatároznunk (ismerve az első 11 kezdőtag értékét). Persze a fokozatos behelyettesítés


21


A 5.6

Kombinatorika

igen időigényes munka lenne, de a véges rekurzió számítógépes megoldása egészen könnyű. Az alábbiakban megadunk egy egyszerű algoritmust. 1. Az f( ) sorozat első 11 tagjának kezdőértéket adunk. 2. Az i ciklusváltozót 12-től egyesével növeljük 100-ig. 3. A cikluson belül meghatározzuk f(i) értékét az f(i) = f(i – 6) + f(i – 11) rekurzív összefüggéssel. [Ki is íratjuk f(i) értékét.] Az eljárás: Ciklus i:=1-től 11-ig f(i):=0 Ciklus vége f(6):=1; f(11):=1 i:=12 Ciklus amíg i 100 f(i):= f(i–6) + f(i–11) Ki: i, f(i) i:= i + 1 Ciklus vége

Persze ha f(200) vagy más végérték a kérdés, akkor a ciklushatárt módosítani kell. A fenti program futási eredménye 100, illetve 200 végérték esetén (az utolsó 13 tagot adjuk meg): i f(i) i f(i) 88 89 90 91 92 93 94 95 96 97

22

79 50 211 462 495 286 100 135 463 792

188 189 190 191 192 193 194 195 196 197


1 164 694 1 315 034 1 120 770 861 321 942 657 1 450 376 1 985 976 2 062 539 1 679 020 1 385 482


A 5.6

98 715 198 1 728 820 99 365 199 2 615 070 100 150 200 3 301 010 5. Az világos, hogy a keresett összeg 95 és 100 közé esik. [A 95-nél kisebb összegek esetében a náluk 6-tal nagyobb összegek már többféleképpen állíthatók elő. Például f(94) < f(100) = f(94) + f(89).] Ezek közül a maximálisan kidobhatót viszont csak próbálgatással tudjuk megkeresni, más matematikai módszerünk nem nagyon van. A számítógépes eredményeknek most nagy hasznát vesszük, hiszen közvetlenül leolvasható, hogy a keresett szám a 97. Tehát a 97 az a 100-nál nem nagyobb pozitív egész szám, amelyik a legtöbbféle módon állítható elő 6x + 11y alakban, ahol x, y természetes számok. 6. Az első feladatban már bevált módszert követjük. a) Az 5 és a 2 · 5 = 10 dobások megadják a legkisebb elérhető összegeket a 3-mal osztva 2, illetve 1 maradékú számok körében. (A 3-mal osztható számok közül a legkisebb elérhető a 3, illetve a 0.) Ebből következik, hogy a 2, illetve a 7 a legnagyobb, nem elérhető szám a két maradékosztályban. A határszám tehát a 8. b) 6x + 8y (x, y ! N) alakban csak olyan összegek állíthatók elő, amelyek 6 és 8 legnagyobb közös osztójának is többszörösei: lnko(6, 8) = 2 osztja az összeget. Vagyis ezen a táblán a páratlan számok nem dobhatók ki, így nincs határszám. (Bármilyen számnál találunk nála nagyobb, nem kidobható számot.) Mivel az ax + bx (x, y ! N) összeg mindkét tagja osztható a és b legnagyobb közös osztójával, ebből adódik, hogy a határszám létezésének szükséges feltétele a és b relatív prím volta. c) lnko(6, 7, 8) = 1, így van reményünk határszámot találni. Rendre előállítjuk a mod 6 maradékosztály kezdőelemeit, 7y + 8z alakban. 6-tal osztva:


23


A 5.6

– az (y, z) = (1, 0) számpár 1 maradékot ad (7); – az (y, z) = (0, 1) számpár 2 maradékot ad (8); – az (y, z) = (1, 1) számpár 3 maradékot ad (15); – az (y, z) = (2, 1) számpár 4 maradékot ad (22); – az (y, z) = (1, 2) számpár 5 maradékot ad (23); – és természetesen az (y, z) = (0, 0) számpár 0 maradékot ad (0). A számpárok képzéséből adódóan a 0, 7, 8, 15, 22, 23 értékek egyúttal a maradékosztályok legkisebb előállítható tagjai is. Megadhatjuk a határszámot: a legnagyobb, nem elérhető szám a 17, így a határszám 18. 7. a) Már korábban láttuk, hogy a határszám létezésének szükséges feltétele lnko(a, b) = 1, azaz a és b relatív prím volta. Most bebizonyítjuk, hogy ez a feltétel elégséges is. Tekintsük a 0 · b, 1 · b, 2 · b, …, (a – 1) · b számok (mod a) osztási maradékait! Ha lenne közöttük két egyforma, például i · b és j · b (ahol i < j), akkor különbségüket osztania kellene a-nak. De (j – i) · b nem osztható a-val, mert a és b relatív prímek, azaz nincs közös osztójuk; a másik (j – i) tényező pedig (a – 1)-nél kisebb pozitív egész szám. Tehát az a darab 0 · b, 1 · b, 2 · b, …, (a – 1) · b számok mind különböző maradékot adnak a-val osztva. Ez csak úgy lehetséges, ha – valamilyen sorrendben – az összes 0, 1, 2, …, (a – 1) maradékot megadják, azaz teljes maradékrendszert alkotnak (mod a). Vagyis b többszörösei segítségével minden (mod a) maradékosztályt elő tudunk állítani. Így – egy bizonyos értéktől kezdve – minden összeg előállítható lesz, hiszen egy-egy maradékosztály összes elemét megkaphatjuk, ha a kezdőtaghoz a többszöröseit adjuk. A határszám konkrét értékét is megállapíthatjuk. Ehhez azt kell észrevennünk, hogy a 0 · b, 1 · b, 2 · b, …, (a – 1) · b számok az egyes maradékosztályok legkisebb elérhető számait adják meg. (Ennek az

24



A 5.6

az oka, hogy ha valamelyik j · b kezdőtagnál lenne kisebb, például i · b, azt már korábban felsoroltuk volna egy másik maradékosztálynál.) Megvannak tehát a legnagyobb nem elérhető számok, ezek: 1 · b – a, 2 · b – a, …, (a – 1) · b – a. Világos, hogy a legnagyobb nem elérhető szám (a – 1) · b – a, és így a határszám (a – 1) · b – a + 1 = (a – 1) · (b – 1). Ellenőrzésképpen összevetjük az eredményt a korábban megoldott (6; 11) és (3; 5) táblák határszámaival. A formula szerint 5 · 10 = 50 és 2 · 4 = 8 határszámokat kellett kapnunk, és ez egyezik is. b) A nem kidobható összegeket úgy kaphatjuk meg, hogy az egyes maradékosztályok kezdőtagjainak értékeit a többszöröseivel csökkentjük. Például az (a – 1) · b kezdőtag esetén nem elérhetők az (a – 1) · b – a, (a – 1) · b – 2a, … számok. Ezek darabszáma annyi, ahányszor az a megvan az â – 1 h $ b E . (Itt [x] az x szám egész (a – 1) · b-ben, azaz ; a részét jelenti.) A nem kidobható összegek számát tehát az â – 1 h $ b S = ; 1 $ b E+;2 $ b E+;3 $ b E+ f +; E összeg adja a a a a meg. Ha {x} jelöli az x szám törtrészét, akkor [x] = x – {x} miatt â – 1 h $ b S = 1$b + 2$b +f+ – a a a â – 1 h $ b c' 1 $ b 1 + ' 2 $ b 1 + f + ' 1m . a a a Az összeg első tagja a számtani sorozat összegképletével kiszámítható: 1 $ b + 2 $ b + f + â – 1h $ b = b $ ^1 + 2 + f + â – 1hh = a a a a


25


A 5.6

a $ â – 1 h b $ â – 1 h . Az összeg második tagjá= b$ = 2 2 a nak kiszámításához pedig felhasználhatjuk, hogy az 1 · b, 2 · b, …, (a – 1) · b számlálók – valamilyen sorrendben – teljes maradékrendszert alkotnak mod a. (A 0 kivételével.) Mivel az i$b ' 1 a típusú kifejezésekben az eredmény csak a számláló (mod a) maradékától függ, így 1 $ b + 2 $ b + f + ' â – 1 h $ b 1 = ' 1 ' 1 a a a = $ 1 .+$2 .+ f +$a – 1 . = 1 + 2 + f + a – 1 . a a a a a a a $ â – 1 h a – 1 = Ez az összeg pedig éppen 2a 2 , így b $ â – 1 h a – 1 ^ b – 1 h $ â – 1 h S= – . = 2 2 2 Ennyi tehát a nem kidobható összegek száma. (Érdekesség, hogy ez éppen a határszám fele.) Ellenőrzés: (a – 1) és (b – 1) valamelyike páros (nem lehet a és b is páros, mert relatív prímek), tehát S egész szám. Az 1. feladatban a = 6, b = 11 választással a nem elérhető ^6 – 1h $ ^11 – 1h . összegek száma 25 volt, és ez valóban 2 A (3; 5) táblán a nem kidobható összegek 2; 1, 4, 7; ezek száma valóban a 8 határszám fele. 8. Az általános formulák ismeretében a feladat már nem nehéz. A határszám (a – 1) · (b – 1), így megoldandó az â – 1h $ ^ b – 1h # 13 1diofantoszi egyenlőtlenség. Nem túl sok eset végigpróbálásával célt érünk: Ha a = 2, akkor b = 3, 4, …, 14 jöhet szóba, de az (a, b) = 1 feltétel miatt csak b = 3, 5, 7, 9, 11, 13 megfelelő. Ha a = 3, akkor 4 # b # 7 , b = 4, 5, 7 lehet. Ha a = 4, akkor b = 5. Ha a $ 5 , akkor már több megoldás nincs.

26


GONDOLKODÁSI MÓDSZEREK Szövegértés

Kombinatorika

A 5.6

1. Nem a közepe ér legtöbbet? A darts Nagy-Britanniából származó ügyességi játék. Újabban a sportág egyre népszerűbb: bajnokságokat és nemzetközi versenyeket rendeznek, ezek az események egyes sportadókon is rendre feltűnnek a televízió képernyőjén, és a játék kedvelt időtöltés a kocsmákban, szórakozóhelyeken.

A játékban a mellékelt ábrán látható céltábla egyes mezőire dobónyíllal (darts) célzunk. A megfelelő 1, 2, …, 20 mezőket eltalálva ennyi pontot ér egy-egy dobás. Ha a külső vékony körgyűrűbe (dupla szektor) áll be a nyíl, akkor a körcikken jelzett dobásérték duplázódik, a beljebb lévő körgyűrű (tripla Fejlesztő matematika (5–12. évf.)

27

15–18. év


Kombinatorika

A 5.6

szektor) eltalálása pedig háromszorozza az értéket. Még két speciális mező van: a céltábla piros közepe (Bull vagy bulls eye) 50 pontot, a körülötte levő zöld külső Bull pedig 25 pontot ér. Például három dobásból legfeljebb 180 pont érhető el, ha három tripla 20-ast dob a játékos (T20 + T20 + T20 = 180). A játéktáblán kívülre érkező dobások, illetve a tábláról leeső nyilak 0 pontot érnek.

15–18. év

1. Három jó barát fogadást kötött. Mindegyikük 3-3 nyilat dob a dartstáblára. A legkevesebb pontot elért játékos fizeti a legnagyobb összeget elért cimborájának vacsoráját. Hogyan alakult a sorrend közöttük? Jack Szállíven

Billy Coolhand

Sam Reyoles

28



Kombinatorika

A 5.6

2. Miután a cimborák elhagyták a vendéglőt, a pincér is kipróbálta, mit tud. 3 dobásból 78 pontot ért el. Döntsd el az alábbi állításokról, hogy igazak-e! A: A dobott értékek között van páros. B: Lehet, hogy minden nyíl szimpla szektorba érkezett. C: A dobott értékek közül csakis az egyik páratlan. D: Lehet, hogy minden nyíl ugyanabba a mezőbe érkezett. 3. Keresd meg azt a 3 szomszédos szektort, amelyeknek összértéke legnagyobb! 4. A pincér újabb három dobásával ezúttal éppen három különböző (normál szektorú) prímszámot dobott. a) Hányféleképpen történhetett ez? b) Lehet-e a dobott összeg 20? Ha igen, hányféleképpen állhat elő ez az összeg? c)* Hányféleképpen fordulhat elő, hogy a három különböző prím összege 3-mal osztható? A tábla elhelyezése: • A táblától 237 cm-re kell állnia a dobónak. • A tábla középpontjának magassága a talajtól mérve 173 cm (egy hat láb, illetve 183 cm magas ember szemmagassága). Dobás: • Dobásnál mindkét lábnak a dobóvonal mögött kell lennie. • Az eldobott nyilat akkor sem lehet újra eldobni, ha az nem érte a táblát, elejtett nyílért azonban a dobóvonalon belülre is be lehet lépni. (Forrás: Wikipedia)


29

15–18. év


Rendszerezőképesség

A 5.6

2. Kidobhatatlan összegek a dartstáblán 1. A 61-nél kisebb pontszámok közül melyek nem érhetők el egy dobásból? Melyek ezek a pontszámok? 15–18. év

2. A 121-nél kisebb pontszámok közül melyek nem érhetők el két dobásból? 3. Mutasd meg, hogy a 173 pont nem érhető el három dobásból! 4. Melyek azok a 181-nél kisebb pontszámok, amelyek nem érhetők el három dobásból? (Esetleg megpróbálhatsz írni egy egyszerű számítógépes programot is, amely futási eredményként a kérdezett számokat adja meg.) A dartsbajnokságokon általában 501 kezdőpontról indulnak a versenyzők, egy dobássorozatban 3 nyíllal dobnak, és minden dobás után az aktuális dobásértékkel csökkentik a pontszámukat. Az nyer, aki hamarabb eléri a 0 pontot. A játék egy érdekes nehezítése, hogy „kimenni”, azaz a játékot befejezni csak pontos dobásértékkel lehet (a versenyző tehát nem kerülhet 0 alá). Például ha 12 pontja van egy versenyzőnek, akkor egy dobással a 12, D6 vagy T4 módon fejezheti be a játékot; míg pl. a 15, D7 vagy T8 dobások érvénytelenek. (Egyes játékverziókban azt is megkövetelik, hogy az utolsó kimenő dobás dupla legyen, de egyelőre ezzel nem foglalkozunk.) Legkevesebb 9 dobással, tehát 3 × 3 dartsszal lehet befejezni egy játékot, de ehhez igen nagy ügyesség kell. Versenyeken általában külön díjazzák az „501 dupla ki” játékokat, amikor még az is további nehezítés, hogy az utolsó kiszálló dobásnak duplának kell lenni. (Ekkor az 50-es Bull is duplának számít.) 30



Rendszerezőképesség

A 5.6

Televízióban először 1984. október 13-án mutattak meg egy kilences darts játékot, a nevezetes játszmában John Lowe a T20, T20, T20; T20, T20, T20; T18, T17, D18 utat választotta. 5. Milyen útvonalakon érhető el kilenc dartsszal az „501 dupla ki” játék? Hányféleképpen történhet egy ilyen játék? (Ez utóbbi kérdést úgy értjük, hogy például a T18, T17, D18 és T18, D18, T17 utakat különbözőnek tekintjük.) A dartsversenyeken, a versenyzők körében persze nem mindegyik 9-es sorozat egyformán népszerű. Például a dartsversenyeken nem szokás az, hogy 167-et dobjanak (tripla 20, tripla 19, bulls eye) minden hármas dartsszal, mert ennél a játékmódnál nincs hibahatár.


31

16–18. év

GONDOLKODÁSI MÓDSZEREK Összefüggéslátás

Kombinatorika

A 5.6

3. A „kétmezős darts játék” általános vizsgálata

16–18. év

1. Mekkora az a legnagyobb összeg, amit nem lehet kidobni a képen látható dartstáblán, akárhányszor is dobhatunk rá? (A KöMaL K. 366. feladata.)

2. Hány olyan összeg van a fenti játékban, amelyet nem tudunk kidobni? 3. Nevezzük „határszámnak” azt a legkisebb kidobható öszszeget, amelyre igaz, hogy minden nála nagyobb összeg is kidobható. Hányféleképpen dobható ki a határszám a fenti dartstáblán? (A dobások sorrendje is számít, azaz a 6 + 11 és a 11 + 6 dobássorozatokat különbözőknek tekintjük.) 4. Hányféleképpen dobható ki egy adott, konkrét összeg a fenti dartstáblán? (A dobások sorrendje is számít.) Tekintsük például az a) 100;

b) 200

összegeket! 5. Vajon melyik lehet az a 100-nál nem nagyobb összeg, amelyik a lehető legtöbb módon dobható ki ezen a dartstáblán?

32


GONDOLKODÁSI MÓDSZEREK Összefüggéslátás

Kombinatorika

A 5.6

6. Határozd meg a határszámokat az alábbi „dartstáblákon”! a)

b)

c)

16–18. év

7. Oldd meg általános esetben is a fenti feladattípust! Legyen a dartstáblán két szektor, értékük a és b (a < b pozitív egész számok). a) Adjunk szükséges és elégséges feltételt a határszám létezésére! b)* Határozzuk meg a nem kidobható összegek számát! 8. A fordított irányú kérdést is feltehetjük. Ha egy dartstáblán a és b a két szektor értéke, akkor milyen (a; b) számpárok esetén biztosított, hogy a határszám ne legyen például 13nál nagyobb? (1 < a < b pozitív egész számok) A legenda szerint néhány száz évvel ezelőtt egy átfázott angol íjász elhatározta, hogy kellemesebb módot választ a gyakorlásra a téli hónapokban. Letette íját, levágott a nyílvesszőjéből, és elvonult a közeli pub kellemes melegébe és kényelmébe, ahol ügyességét úgy gyakorolta, hogy a lerövidített nyílvesszőket a falra akasztott farönkszeletbe dobta. Mellé állt egy másik íjász, aki megpróbált az előzőnél jobb eredményt elérni, és ezzel megszületett a vetélkedés, a játék, a sport. (Forrás: Wikipedia)


33


Az Ön jegyzetei, kérdései*:

* Kérdéseit juttassa el a RAABE Kiadóhoz! 34


A 5.6

Darts: surranó nyilak, gondolkodtató problémák Kombinatorika 6. feladatcsomag

Recommend Documents