Įvadas į kombinatoriką
Turinys
Paprastų skaičiavimų taisyklės
Paprastų skaičiavimų taisyklės - teorija
Sudėtis
Jei įvykis $A$ gali įvykti $m$ būdais, o įvykis $B$ gali įvykti $n$ būdais, ir šie įvykiai negali įvykti vienu metu (jie yra nesuderinami), tai įvykis "$A$ arba $B$" gali įvykti $m + n$ būdais.
Pavyzdys: jei turite 3 skirtingus marškinėlius ir 4 skirtingas maikes, tai iš viso turite $3 + 4 = 7$ skirtingus viršutinius drabužius, kuriuos galite pasirinkti apsirengti.
Daugyba
Jei įvykis $A$ gali įvykti $m$ būdais, ir po to, kai įvykis $A$ įvyko, įvykis $B$ gali įvykti $n$ būdais, tai įvykių pora "$A$ ir $B$" gali įvykti $m \cdot n$ būdų. Ši taisyklė gali būti išplėsta keliems įvykiams.
Pavyzdys: jei turite 3 marškinėlius ir 4 kelnes, tai galite sukurti $3 \cdot 4 = 12$ skirtingų aprangos derinių.
Paprastų skaičiavimų taisyklės - uždaviniai
1. Kiek yra dviženklių skaičių, kurių skaitmenų suma lygi 7?
Sprendimas
Dviženklis skaičius $xy$ reiškia $10x + y$. $x$ negali būti 0. Skaitmenų suma yra $x+y=7$.
Galimos poros $(x, y)$:
Jei $x=1$, $y=6$ (skaičius 16)
Jei $x=2$, $y=5$ (skaičius 25)
Jei $x=3$, $y=4$ (skaičius 34)
Jei $x=4$, $y=3$ (skaičius 43)
Jei $x=5$, $y=2$ (skaičius 52)
Jei $x=6$, $y=1$ (skaičius 61)
Jei $x=7$, $y=0$ (skaičius 70)
Taigi, iš viso yra 7 tokie skaičiai.
Yra 7 dviženkliai skaičiai, kurių skaitmenų suma lygi 7.
2. Kiek skirtingų 4 skaitmenų PIN kodų galima sudaryti, jei skaitmenys gali kartotis?
Sprendimas
Kiekviena PIN kodo pozicija (tūkstančių, šimtų, dešimčių, vienetų) gali būti užpildyta bet kuriuo iš 10 skaitmenų (nuo 0 iki 9). Kadangi skaitmenys gali kartotis, kiekvienai pozicijai turime 10 pasirinkimų.
Pagal daugybos taisyklę:
Pirmo skaitmens pasirinkimai: 10
Antro skaitmens pasirinkimai: 10
Trečio skaitmens pasirinkimai: 10
Ketvirto skaitmens pasirinkimai: 10
Bendras PIN kodų skaičius: $10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10000$.
Galima sudaryti 10000 skirtingų 4 skaitmenų PIN kodų.
3. Automobilių numeriai Lietuvoje susideda iš trijų raidžių (naudojant 24 raides) ir trijų skaitmenų (nuo 0 iki 9). Kiek skirtingų automobilių numerių galima suformuoti, jei:
a) Raidės ir skaitmenys gali kartotis.
b) Raidės ir skaitmenys negali kartotis.
Sprendimas
a) Raidės ir skaitmenys gali kartotis:
Raidžių pozicijos:
Pirma raidė: 24 pasirinkimai
Antra raidė: 24 pasirinkimai
Trečia raidė: 24 pasirinkimai
Bendras raidžių derinių skaičius: $24 \cdot 24 \cdot 24 = 24^3 = 13824$.
Skaitmenų pozicijos:
Pirmas skaitmuo: 10 pasirinkimų (0-9)
Antras skaitmuo: 10 pasirinkimų
Trečias skaitmuo: 10 pasirinkimų
Bendras skaitmenų derinių skaičius: $10 \cdot 10 \cdot 10 = 10^3 = 1000$.
Bendras automobilių numerių skaičius (pagal daugybos taisyklę):
$13824 \cdot 1000 = 13824000$.
b) Raidės ir skaitmenys negali kartotis:
Raidžių pozicijos:
Pirma raidė: 24 pasirinkimai
Antra raidė: 23 pasirinkimai (viena jau panaudota)
Trečia raidė: 22 pasirinkimai (dvi jau panaudotos)
Bendras raidžių derinių skaičius: $24 \cdot 23 \cdot 22 = 12144$.
Skaitmenų pozicijos:
Pirmas skaitmuo: 10 pasirinkimų
Antras skaitmuo: 9 pasirinkimai
Trečias skaitmuo: 8 pasirinkimai
Bendras skaitmenų derinių skaičius: $10 \cdot 9 \cdot 8 = 720$.
Bendras automobilių numerių skaičius (pagal daugybos taisyklę):
$12144 \cdot 720 = 8743680$.
Gretiniai, kėliniai ir deriniai
Gretiniai, kėliniai ir deriniai - teorija
Gretiniai
Gretinių iš \(n\) elementų po \(k\) yra tokie junginiai, kurie vienas nuo kito skiriasi arba pačiais elementais, arba jų išdėstymo tvarka.
$$A_n^k = n(n-1)(n-2) \cdot \dotsc \cdot (n-(k-1)) = \frac{n!}{(n-k)!}$$
Pavyzdžiui:
$$A_5^3 = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1} = 5 \cdot 4 \cdot 3 = 60$$
Laikoma, kad $A_0^0 = 1$ ir $A_n^0 = 1$.
Daugiau apie gretinius
Kėliniai
Kėliniai iš $n$ elementų yra gretiniai iš $n$ elementų po $n$ elementų. Kėlinių skaičius žymimas $P_n$ ir apskaičiuojamas remiantis formule:
$$P_n = n(n-1)(n-2) \cdot \dotsc \cdot 3 \cdot 2 \cdot 1 = n!$$
Kėlinių su pasikartojimais skaičiaus formulė:
$$P_n (k_1, k_2, k_3, \dotsc, k_n) = \frac{n!}{k_1 ! \cdot k_2 ! \cdot k_3 ! \cdot \dotsc \cdot k_n !}$$
Čia $n$ - junginio elementų skaičius,
$k_1$ - elemento $a_1$ pasikartojimų skaičius,
$k_2$ - elemento $a_2$ pasikartojimų skaičius,
$\dotsc$
$k_n$ - elemento $a_n$ pasikartojimų skaičius.
Visada $k_1 + k_2 + k_3 + \dotsc + k_n = n$.
Daugiau apie kėlinius
Deriniai
Deriniai iš $n$ elementų po $k$ elementų vadinami junginiai, kurie vienas nuo kito skiriasi tik pačiais elementais (į elementų išdėstymo tvarką neatsižvelgiame).
Derinių iš $n$ elementų po $k$ skaičius yra žymimas $C_n^k$ ($1 \leq k \leq n$) ir apskaičiuojamas remiantis formule:
$$C_n^k = \frac{n(n-1)(n-2)\cdot \dotsc \cdot(n-(k-1))}{k!} = \frac{n!}{k!(n-k)!}$$
Laikoma, kad $C_0^0 = 1$ ir $C_n^0 = 1$.
Pavyzdžiui:
$$C_5^3 = \frac{5!}{3!(5-3)!} = \frac{5!}{3!2!} = \frac{5 \cdot 4}{2 \cdot 1} = 10$$
Daugiau apie derinius
Gretiniai, kėliniai ir deriniai - uždaviniai
1. Kiek skirtingų būdų 6 draugai gali atsisėsti į eilę kino teatre?
Sprendimas
Kadangi visi 6 draugai sėda į eilę, tai yra visų elementų išdėstymas, kur tvarka yra svarbi. Tai yra kėlinys. Naudosime jo formulę: $P_n = n!$. $$n=6$$ $$P_6 = 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$$ 6 draugai gali atsisėsti į eilę 720 skirtingų būdų.
2. Mokykloje yra 10 skirtingų sporto būrelių. Mokinys gali pasirinkti 3 būrelius.
a) Kiek skirtingų būrelių rinkinių jis gali pasirinkti, jei jam nerūpi pasirinkimo tvarka?
b) Kiek skirtingų būrelių rinkinių jis gali pasirinkti, jei pirmas pasirinktas būrelis yra jam svarbiausias, antras – mažiau svarbus, o trečias – mažiausiai svarbus?
Sprendimas
Čia $n=10$ (bendras būrelių skaičius), o $k=3$ (pasirenkamų būrelių skaičius).
a) Nerūpi pasirinkimo tvarka: tai yra derinys.
$$C_{10}^3 = \binom{10}{3} = \frac{10!}{3!(10-3)!} = \frac{10!}{3!7!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 10 \cdot 3 \cdot 4 = 120.$$
b) Tvarka yra svarbi: tai yra gretinys.
$$A_{10}^3 = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720.$$
a) 120 skirtingų būrelių rinkinių.
b) 720 skirtingų būrelių rinkinių.
3. Iš 7 vyrų ir 5 moterų reikia sudaryti 4 asmenų komandą. Kiek skirtingų komandų galima sudaryti, jei komandoje turi būti bent 2 moterys?
Sprendimas
Bendras žmonių skaičius $N = 7+5 = 12$. Komandą sudaro $K=4$ asmenys.
Komandoje turi būti bent 2 moterys. Tai reiškia, kad moterų skaičius gali būti 2, 3 arba 4.
Suskirstykime į atvejus ir pritaikykime derinių formulę (nes komandoje asmenų tvarka nesvarbi).
1 atvejis: 2 moterys ir 2 vyrai
Pasirenkame 2 moteris iš 5: $C_5^2 = \frac{5!}{2!3!} = \frac{5 \cdot 4}{2 \cdot 1} = 10$ būdų.
Pasirenkame 2 vyrus iš 7: $C_7^2 = \frac{7!}{2!5!} = \frac{7 \cdot 6}{2 \cdot 1} = 21$ būdas.
Bendras šio atvejo komandų skaičius (pagal daugybos taisyklę): $10 \cdot 21 = 210$.
2 atvejis: 3 moterys ir 1 vyras
Pasirenkame 3 moteris iš 5: $C_5^3 = \frac{5!}{3!2!} = \frac{5 \cdot 4}{2 \cdot 1} = 10$ būdų.
Pasirenkame 1 vyrą iš 7: $C_7^1 = \frac{7!}{1!6!} = 7$ būdai.
Bendras šio atvejo komandų skaičius: $10 \cdot 7 = 70$.
3 atvejis: 4 moterys ir 0 vyrų
Pasirenkame 4 moteris iš 5: $C_5^4 = \frac{5!}{4!1!} = 5$ būdų.
Pasirenkame 0 vyrų iš 7: $C_7^0 = 1$ būdas.
Bendras šio atvejo komandų skaičius: $5 \cdot 1 = 5$.
Bendras visų galimų komandų skaičius (pagal sudėties taisyklę):
$210 + 70 + 5 = 285$.
Galima sudaryti 285 skirtingas komandas.
Dirichlė principas
Dirichlė principas - teorija
Kas yra Dirichlė principas?
Dirichlė principas (dar žinomas kaip balandžių narvelio principas, angl. Pigeonhole Principle) yra paprastas, bet nepaprastai dažnai naudojamas įrankis kombinatorikos įrodymams. Jis teigia:
Jei $n$ daiktų yra paskirstyti į $m$ dėžučių (arba balandžiai į narvelius), ir $n > m$, tai bent vienoje dėžutėje (narvelyje) bus daugiau nei vienas daiktas.
Kitaip tariant, jei turite daugiau balandžių nei narvelių, bent viename narvelyje turės būti du ar daugiau balandžių.
Apibendrinta formuluotė:
Jei $n$ daiktų yra paskirstyti į $m$ dėžučių, tai bent vienoje dėžutėje bus bent $\lceil n/m \rceil$ daiktų (čia $\lceil x \rceil$ reiškia mažiausią sveikąjį skaičių, ne mažesnį už $x$).
Strategija sprendžiant uždavinius su Dirichlė principu:
Svarbiausia – teisingai atpažinti, kas yra "daiktai" (balandžiai) ir kas yra "dėžutės" (narveliai). Uždaviniuose dažnai reikia patiems juos apibrėžti arba sukurti.
Daugiau apie Dirichlė principą
Dirichlė principas dažnai pritaikomas uždaviniuose, daugiau apie jį pasiskaityti galie čia:
Plačiau apie Dirichlė principą
Dirichlė principas - uždaviniai
1. Mokykloje yra 366 mokiniai. Įrodykite, kad bent du mokiniai turi gimtadienį tą pačią dieną. (Neįskaitant keliamųjų metų, t.y., metuose yra 365 dienos).
Sprendimas
Daiktai (balandžiai): 366 mokiniai.
Dėžutės (narveliai): 365 metų dienos (galimos gimtadienių datos).
Kadangi $n=366$ (mokinių skaičius) ir $m=365$ (dienų skaičius), ir $n > m$, pagal Dirichlė principą bent vienoje "dėžutėje" (gimtadienio dieną) bus daugiau nei vienas "daiktas" (mokinys). Vadinasi, bent du mokiniai turi gimtadienį tą pačią dieną.
Įrodyta.
2. Kokį mažiausią skaičių kojinių reikia ištraukti iš stalčiaus tamsoje, kad tikrai turėtumėte porą tų pačių spalvų kojinių, jei stalčiuje yra 10 mėlynų ir 8 juodos kojinės?
Sprendimas
Jei ištrauksime 2 kojines:
1. gali būti mėlyna ir mėlyna (porą turime)
2. gali būti juoda ir juoda (porą turime)
3. gali būti mėlyna ir juoda (poros neturime)
Pagal Dirichlė principą, kad tikrai turėtume porą, mums reikia, kad kojinių skaičius būtų didesnis už dėžučių skaičių plius 1.
Jei ištrauksime po vieną kojinę iš kiekvienos spalvos "dėžutės", t.y., 1 mėlyną ir 1 juodą, turėsime 2 kojines ir neturėsime poros.
Kai ištrauksime trečią kojinę, ji būtinai bus arba mėlyna, arba juoda, todėl sudarys porą su viena iš jau turimų kojinių.
Mažiausias skaičius $n=m+1=2+1=3$.
Reikia ištraukti 3 kojines.
3. Duoti 5 taškai plokštumoje, kurių koordinatės yra sveikieji skaičiai. Įrodykite, kad egzistuoja bent viena atkarpa, jungianti du iš šių taškų, kurios vidurio taško koordinatės yra sveikieji skaičiai.
Sprendimas
Atkarpos, jungiančios taškus ($x_1$, $y_1$) ir ($x_2$, $y_2$), vidurio taško koordinatės yra ($\frac{x_1 + x_2}{2}$, $\frac{y_1 + y_2}{2}$). Kad vidurio taško koordinatės būtų sveikieji skaičiai, $x_1 + x_2$ ir $y_1 + y_2$ turi būti lyginiai skaičiai. Tai įvyksta, jei $x_1$ ir $x_2$ yra to pačio lyginumo (abu lyginiai arba abu nelyginiai) ir $y_1$ ir $y_2$ yra to pačio lyginumo.
Taško ($x$,$y$) koordinatės gali turėti 4 lyginumo derinius:
1. (lyginis, lyginis)
2. (lyginis, nelyginis)
3. (nelyginis, lyginis)
4. (nelyginis, nelyginis)
Dėžutės (narveliai): šie 4 galimi koordinačių lyginumo deriniai. Taigi, $m=4$ dėžutės.
Daiktai (balandžiai): duoti 5 taškai. Taigi, $n=5$ daiktai.
Kadangi $n=5>m=4$, tai pagal Dirichlė principą bent du taškai pateks į tą pačią lyginumo derinio dėžutę. Tai reiškia, kad atsiras bent du taškai ($x_1$, $y_1$) ir ($x_2$, $y_2$), kurių $x$ koordinatės turi tą patį lyginumą ir $y$ koordinatės turi tą patį lyginumą.
Jei $x_1$ ir $x_2$ yra to paties lyginumo, tai $x_1 + x_2$ yra lyginis.
Jei $y_1$ ir $y_2$ yra to paties lyginumo, tai $y_1 + y_2$ yra lyginis.
Vadinasi, $\frac{x_1 + x_2}{2}$ ir $\frac{y_1 + y_2}{2}$ bus sveikieji skaičiai. Todėl šių dviejų taškų vidurio taško koordinatės bus sveikieji skaičiai.
Įrodyta.
Matematiniai žaidimai
Matematiniai žaidimai - teorija
Kas yra matematiniai žaidimai?
Matematiniai žaidimai yra ypatinga kombinatorikos sritis, nagrinėjanti žaidimus su griežtomis taisyklėmis, kur atsitiktinumas nedaro įtakos rezultatui, o žaidėjų ėjimai yra žinomi. Šiuose žaidimuose, kaip ir šachmatuose ar šaškėse, svarbiausia yra strategija, logiškas mąstymas ir gebėjimas nustatyti laiminčias bei pralaiminčias pozicijas. Olimpiadinėje matematikoje matematiniai žaidimai dažnai pasirodo kaip loginiai uždaviniai, reikalaujantys mąstyti keliais ėjimais į priekį ir atrasti bendrus laiminčios strategijos principus.
Pagrindinis matematinio žaidimo tikslas yra rasti laiminčiąją strategiją – tai yra taisyklių rinkinys, leidžiantis vienam iš žaidėjų (nepriklausomai nuo kito žaidėjo ėjimų) pasiekti laiminčią poziciją. Laiminčiosios strategijos dažnai grindžiamos žaidimo pozicijų klasifikavimu į laiminčias pozicijas (pozicijas, iš kurių pirmasis žaidėjas pralaimi, jei antrasis žaidėjas žaidžia tobulai, t.y. laiminčios antrajam žaidėjui) ir pralaiminčias pozicijas (pozicijas, iš kurių pirmasis žaidėjas laimi, jei žaidžia tobulai, t.y. laiminčios pirmajam žaidėjui).
Daugiau apie matematinius žaidimus
Matematiniai žaidimai yra dažni olimpiadinėje kombinatorikoje, daugiau apie juos (žaidimą NIM ir t.t.) rasite matematikos knygoje, kurią parašė 5 Lietuvos matematikai, ne kartą atstovavę Lietuvą tarptautinėse olimpiadose:
Plačiau apie matematinius žaidimus (skyrelis "Matematiniai žaidimai" - 92 psl.)
Matematiniai žaidimai - uždaviniai
1. Ant stalo yra 10 degtukų. Du žaidėjai pakaitomis ima 1 arba 2 degtukus. Laimi tas, kuris paima paskutinius degtukus. Koks žaidėjas (pirmasis ar antrasis) turi laiminčią strategiją? Žaidimą pradeda pirmasis žaidėjas.
Sprendimas
Analizuokime žaidimą nuo pabaigos.
Jei liko 1 arba 2 degtukai: žaidėjas, kurio eilė, paima visus ir laimi. Tai laiminčioji pozicija.
Jei liko 3 degtukai: kad ir kiek paimtų (1 ar 2), liks 2 arba 1 degtukas. Iš tų pozicijų kitas žaidėjas paims viską ir laimės. Vadinasi, 3 degtukai yra pralaiminčioji pozicija.
Jei liko 4 degtukai: žaidėjas gali paimti 1 degtuką ir palikti 3. 3 yra pralaiminčioji pozicija, tad šis žaidėjas laimi. Vadinasi, 4 degtukai yra laiminčioji pozicija.
Jei liko 5 degtukai: žaidėjas gali paimti 2 degtukus ir palikti 3. 3 yra pralaiminčioji pozicija, tad šis žaidėjas laimi. Vadinasi, 5 degtukai yra laiminčioji pozicija.
Jei liko 6 degtukai: žaidėjas gali paimti 3 degtukus ir palikti 3. Bet jis negali paimti 3, nes paima tik 1 arba 2.
Jei paima 1, lieka 5 (laiminčioji pozicija).
Jei paima 2, lieka 4 (laiminčioji pozicija).
Vadinasi, 6 degtukai yra pralaiminčioji pozicija, nes kad ir ką darytum, visada palieki laiminčiąją poziciją.
O nuo čia telieka įrodyti, kad pirmasis žaidėjas visada gali priversti antrąjį pradėti ėjimą su 6 degtukais (pralaiminčioje pozicijoje), o tada jau įrodėme, kad pirmasis žaidėjas laimės.
O tai padaryti yra paprasta: pirmasis žaidėjas turi paimti 1 degtuką, palikdamas 9. Tada antrasis žaidėjas turės paimti 1 arba 2, palikdamas 8 arba 7. Iš abiejų šių pozicijų pirmasis žaidėjas gali palikti 6 (paimdamas 2 arba 1 atitinkamai). Vadinasi, kad pirmasis žaidėjas gali visada laimėti, jeigu jis pirmas darys ėjimą.
Pirmasis žaidėjas turi laiminčią strategiją.
2. Ant stalo yra 20 degtukų. Du žaidėjai pakaitomis paima degtukus. Vienu ėjimu žaidėjas gali paimti 1, 2 arba 3 degtukus. Laimi tas, kuris paima paskutinį degtuką. Kas laimi, jei abu žaidžia tobulai?
Sprendimas
Čia ir vėl galėtume analizuoti žaidimą nuo pabaigos, nustatydami P (pralaiminčias) ir L (laiminčias) pozicijas, tačiau galime tai padaryti greičiau.
Mes žinome, kad ir kokį skaičių degtukų paims pirmasis žaidėjas, antrasis galės paimti tiek, kad bendra per jų abiejų ėjimą paimtų degtukų suma būtų lygi 4. Jei pirmasis žaidėjas paima 1, tada antrasis 3, jei pirmasis 2, tada ir antrasis 2, o jei pirmasis 3, tada antrasis 1.
Vadinasi, kad per vieną bendrą ėjimą (vadinasi kai abu žaidėjai padaro po vieną ėjimą atskirai) nuo stalo visada galima paimti 4 degtukus, o iš viso yra 20 degtukų, vadinasi galime padaryti 5 tokius ėjimus, kai nuimame po 4 degtukus nuo stalo, ir tada antrasis žaidėjas per savo 5-ą ėjimą paims paskutinį degtuką nuo stalo.
Antrasis žaidėjas turi laiminčią strategiją.
3. Ant stalo yra $N$ monetų. Du žaidėjai pakaitomis paima monetas. Vienu ėjimu žaidėjas gali paimti 1, 2 arba 4 monetas. Laimi tas, kuris paima paskutinę monetą. Kokia laiminčioji strategija, jei $N=25$?
Sprendimas
Tai yra "Atėmimo žaidimas", kurio strategija nustatoma identifikuojant laiminčias (L) ir pralaiminčias (P) pozicijas, dirbant atbuline eiga nuo 0 monetų.
P-pozicija: Žaidėjas, kurio eilė, pralaimi, jei priešininkas žaidžia tobulai. Iš šios pozicijos bet koks galimas ėjimas veda į N-poziciją.
L-pozicija: Žaidėjas, kurio eilė, laimi, jei žaidžia tobulai. Iš šios pozicijos egzistuoja bent vienas ėjimas, kuris veda į L-poziciją.
Galimi ėjimai: paimti 1, 2 arba 4 monetas.
Nustatysime L ir P pozicijas iki 25 monetų:
0 monetų: P-pozicija (nėra ėjimų, todėl pralaimi tas, kurio eilė).
1 moneta: L-pozicija (galima paimti 1 monetą, lieka 0 (P)).
2 monetos: L-pozicija (galima paimti 2 monetas, lieka 0 (P)).
3 monetos: P-pozicija (jei paimi 1, lieka 2 (L); jei paimi 2, lieka 1 (L)).
4 monetos: L-pozicija (galima paimti 4 monetas, lieka 0 (P)).
5 monetos: L-pozicija (galima paimti 2 monetas, lieka 3 (P)).
6 monetos: P-pozicija (jei paimi 1, lieka 5 (L); jei paimi 2, lieka 4 (L); jei paimi 4, lieka 2 (L)).
7 monetos: L-pozicija (galima paimti 1 monetą, lieka 6 (P)).
8 monetos: L-pozicija (galima paimti 2 monetas, lieka 6 (P)).
9 monetos: P-pozicija (jei paimi 1, lieka 8 (L); jei paimi 2, lieka 7 (L); jei paimi 4, lieka 5 (L)).
10 monetų: L-pozicija (galima paimti 1 monetą, lieka 9 (P)).
11 monetų: L-pozicija (galima paimti 2 monetas, lieka 9 (P)).
12 monetų: P-pozicija (jei paimi 1, lieka 11 (L); jei paimi 2, lieka 10 (L); jei paimi 4, lieka 8 (L)).
13 monetų: L-pozicija (galima paimti 1 monetą, lieka 12 (P)).
14 monetų: L-pozicija (galima paimti 2 monetas, lieka 12 (P)).
15 monetų: P-pozicija (jei paimi 1, lieka 14 (L); jei paimi 2, lieka 13 (L); jei paimi 4, lieka 11 (L)).
16 monetų: L-pozicija (galima paimti 1 monetą, lieka 15 (P)).
17 monetų: L-pozicija (galima paimti 2 monetas, lieka 15 (P)).
18 monetų: P-pozicija (jei paimi 1, lieka 17 (L); jei paimi 2, lieka 16 (L); jei paimi 4, lieka 14 (L)).
19 monetų: L-pozicija (galima paimti 1 monetą, lieka 18 (P)).
20 monetų: L-pozicija (galima paimti 2 monetas, lieka 18 (P)).
21 moneta: P-pozicija (jei paimi 1, lieka 20 (L); jei paimi 2, lieka 19 (L); jei paimi 4, lieka 17 (L)).
22 monetos: L-pozicija (galima paimti 1 monetą, lieka 21 (P)).
23 monetos: L-pozicija (galima paimti 2 monetas, lieka 21 (P)).
24 monetos: P-pozicija (jei paimi 1, lieka 23 (L); jei paimi 2, lieka 22 (L); jei paimi 4, lieka 20 (L)).
25 monetos: L-pozicija (galima paimti 1 monetą, lieka 24 (P)).
Pradžioje monetų yra $N=25$. Kadangi 25 yra L-pozicija (žr. sąrašą), pirmasis žaidėjas turi laiminčią strategiją.
Laiminčioji strategija pirmajam žaidėjui:
Pirmasis žaidėjas, esantis L-pozicijoje, turi padaryti ėjimą, kuris palieka oponentą P-pozicijoje.
Iš $N=25$, artimiausia ir pasiekiama P-pozicija yra 24.
Kad paliktų 24 monetas, pirmasis žaidėjas turi paimti $25−24=1$ monetą.
Po to, kai pirmasis žaidėjas paima 1 monetą, lieka 24 monetos (P-pozicija). Antrasis žaidėjas, kad ir kiek paimtų (1, 2 ar 4), paliks L-poziciją (23, 22 ar 20 atitinkamai). Iš L-pozicijos pirmasis žaidėjas vėlgi visada gali padaryti ėjimą, kad paliktų P-poziciją, ir taip toliau, kol galiausiai paims paskutines monetas.
Pirmasis žaidėjas turi laiminčią strategiją.
Daugiau uždavinių ir teorijos galite rasti matematikos knygoje, kurią parašė 5 Lietuvos matematikai, ne kartą atstovavę Lietuvą tarptautinėse olimpiadose:
Plačiau apie matematinius žaidimus (skyrelis "Matematiniai žaidimai" - 92 psl.)
Apibendrinimas
Papildomi ištekliai
- Lietuviškas Youtube kanalas, kuriame yra daug olimpiadinės matematikos uždavinių su sprendimais:
Kofka505 - Matematikos knyga, kurią parašė 5 Lietuvos matematikai, ne kartą atstovavę Lietuvą tarptautinėse olimpiadose (joje aprašomos visos 4 olimpiadinės matematikos sritys):
Matematikos knyga - Praeitų metų Lietuvos mokinių matematikos olimpiados (LMMO) užduotys:
LMMO svetainė