Ant lentos du žaidėjai iš eilės vienas po kito rašo natūraliuosius skaičius, ne didesnius už p (p yra duotas natūralus skaičius). Pagal taisykles žaidėjai negali rašyti skaičių, kurie yra bent vieno jau parašyto skaičiaus daliklis. (Pavyzdžiui, jei ant lentos užrašytas skaičius 10, tai jau nebegalima rašyti 1, 2, 5, 10).
Kas laimės, jei: a) p=10; b) p=2012?
Šį uždavinį mums pasiūlė mūsų forumo narys verbunai. Ačiū Jam!
[spoiler]
Sprendimas.
Nesvarbu koks p, visada laimės pirmas žaidėjas. Jei p = 1, tai akivaizdu, todėl tarkime, kad p > 1.
Žaidimas yra baigtinis (yra tik baigtinis skaičius galimų pozicijų), todėl kažkuris žaidėjas, žaisdamas optimaliai, gali užsitikrinti pergalę (t.y. tas žaidėjas turi "laiminčią strategiją").
Žymėkime žaidėjus A ir B: A - pirmasis, B - antrasis.
Įrodysime, kad B negali turėti laiminčiosios strategijos. Tarkime, kad turi. Tuomet jei A pirmu ėjimu užrašytų 1, B savo pirmu ėjimu galėtų užrašyti kažkokį skaičių k (1 < k ≤ p), kuris užtikrintų B pergalę (jei toliau žaistų optimaliai). Tai reiškia, kad jei A pirmuoju ėjimu užrašytų k, B negalėtų užsitikrinti pergalės, kadangi situacijos {1, k} ir {k} yra visiškai lygios (nes 1 yra visų natūrinių skaičių daliklis ir joks natūrinis skaičius, didesnis už 1, nėra 1 daliklis). Gauname prieštarą.
Taigi laiminčiąją strategiją turi A.
Ats.: abiem atvejais laimės žaidimą pradėjęs žaidėjas.
Šį sprendimą mums pasiūlė mūsų forumo narys AncientMariner. Ačiū ir Jam!
[/spoiler]
pakeista prieš 11 m
AncientMariner +411
Nesvarbu koks p, visada laimės pirmas žaidėjas. Jei p = 1, tai akivaizdu, todėl tarkime, kad p > 1.
Žaidimas yra baigtinis (yra tik baigtinis skaičius galimų pozicijų), todėl kažkuris žaidėjas, žaisdamas optimaliai, gali užsitikrinti pergalę (t.y. tas žaidėjas turi "laiminčią strategiją").
Žymėkime žaidėjus A ir B: A - pirmasis, B - antrasis.
Įrodysime, kad B negali turėti laiminčiosios strategijos. Tarkime, kad turi. Tuomet jei A pirmu ėjimu užrašytų 1, B savo pirmu ėjimu galėtų užrašyti kažkokį skaičių k (1 < k ≤ p), kuris užtikrintų B pergalę (jei toliau žaistų optimaliai). Tai reiškia, kad jei A pirmuoju ėjimu užrašytų k, B negalėtų užsitikrinti pergalės, kadangi situacijos {1, k} ir {k} yra visiškai lygios (nes 1 yra visų natūrinių skaičių daliklis ir joks natūrinis skaičius, didesnis už 1, nėra 1 daliklis). Gauname prieštarą.
Taigi laiminčiąją strategiją turi A.
pakeista prieš 11 m
verbunai PRO +127
AncientMarinerNesvarbu koks p, visada laimės pirmas žaidėjas. Jei p = 1, tai akivaizdu, todėl tarkime, kad p > 1.
Žaidimas yra baigtinis (yra tik baigtinis skaičius galimų pozicijų), todėl kažkuris žaidėjas, žaisdamas optimaliai, gali užsitikrinti pergalę (t.y. tas žaidėjas turi "laiminčią strategiją").
Žymėkime žaidėjus A ir B: A - pirmasis, B - antrasis.
Įrodysime, kad B negali turėti laiminčiosios strategijos. Tarkime, kad turi. Tuomet jei A pirmu ėjimu užrašytų 1, B savo pirmu ėjimu galėtų užrašyti kažkokį skaičių k (1 < k ≤ p), kuris užtikrintų B pergalę (jei toliau žaistų optimaliai). Kita vertus, jei A pirmuoju ėjimu užrašytų k, B negalėtų užsitikrinti pergalės, kadangi situacijos {1, k} ir {k} yra visiškai lygios (nes 1 yra visų natūrinių skaičių daliklis ir joks natūrinis skaičius, didesnis už 1, nėra 1 daliklis). Gauname prieštarą.
Taigi laiminčiąją strategiją turi A.
Šauniai! Važiavai į IMO?
AncientMariner +411
verbunaiŠauniai! Važiavai į IMO?
Esu važiavęs :)
Jei gerai įsivaizduoju, esi iš Lietuvos olimpiados komisijos? Gal ir tu važiavai į IMO?
verbunai PRO +127
Kaip sekėsi? Esu jau 7 metus ten. O pats nevažiavau, tuo metu ne vien už rezultatus vežė. Nors dukart buvau šalia- metė monetą, likau 7tas.
AncientMariner +411
verbunaiKaip sekėsi? Esu jau 7 metus ten. O pats nevažiavau, tuo metu ne vien už rezultatus vežė. Nors dukart buvau šalia- metė monetą, likau 7tas.
A, aišku. :)
O kaip man sekėsi - esu grįžęs su visais įmanomais rezultatais (esu ir tuščiom rankom), išskyrus aukščiausios prabos medalį :(
verbunai PRO +127
AncientMariner
verbunaiKaip sekėsi? Esu jau 7 metus ten. O pats nevažiavau, tuo metu ne vien už rezultatus vežė. Nors dukart buvau šalia- metė monetą, likau 7tas.
A, aišku. :)
O kaip man sekėsi - esu grįžęs su visais įmanomais rezultatais (esu ir tuščiom rankom), išskyrus aukščiausios prabos medalį :(
Na pagal aprašymą, vienintelis toks per istoriją tėra lietuvis. 2008tų sidabras :)
AncientMariner +411
verbunai
AncientMariner
verbunaiKaip sekėsi? Esu jau 7 metus ten. O pats nevažiavau, tuo metu ne vien už rezultatus vežė. Nors dukart buvau šalia- metė monetą, likau 7tas.
A, aišku. :)
O kaip man sekėsi - esu grįžęs su visais įmanomais rezultatais (esu ir tuščiom rankom), išskyrus aukščiausios prabos medalį :(
Na pagal aprašymą, vienintelis toks per istoriją tėra lietuvis. 2008tų sidabras :)
Kaip ir vienintelis nelaimėlis, kuriam kelią į IMO užkirto moneta.
Taigi apsikeitėm lygiaverte informacija :D
verbunai PRO +127
teisybės dėlei, aš nesu vienintelis toks. Aš esu paskutinis toks :D