ematematikas
Kategorijos +Nauja tema Prisijungti        

Matematikos olimpiadinis uždavinys Nr. 15***

Olimpiados Peržiūrų skaičius (4515)

Sąlyga.

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]

Paskutinį kartą atnaujinta 2012-05-15

0

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.

Paskutinį kartą atnaujinta 2012-05-07

0

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?

0

verbunaiŠauniai! Važiavai į IMO?


Esu važiavęs :)

Jei gerai įsivaizduoju, esi iš Lietuvos olimpiados komisijos? Gal ir tu važiavai į IMO?

0

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.

0

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į :(

0

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 :)

0

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

0

teisybės dėlei, aš nesu vienintelis toks. Aš esu paskutinis toks :D

0

Norėdami rašyti žinutes privalote prisijungti!