Peli (tehtävä)

Peli  on eräänlainen matematiikan olympiatehtäviä , joissa on analysoitava pelin strategia ja/tai nimettävä tämän pelin voittaja. Yleensä päättyy perinteiseen kysymykseen: "Kuka voittaa, jos pelataan oikein?"

Pelin ominaisuudet

Yleensä tämäntyyppisten pelien tehtävissä:

Poikkeamat määritellyistä ominaisuuksista ovat yksittäisiä. Osa ongelmasta on juuri näiden ominaisuuksien todistaminen.

"Oikea peli"

"Oikea peli" tämän luokan ongelmissa on voittostrategia peliteoriasta - strategia, jota noudattamalla pelaaja voittaa missä tahansa vastustajan kostotoiminnassa. Oikea peli on peli, jossa molemmat vastustajat toimivat järkevästi yrittäen voittaa (älä anna periksi toisilleen).

Suhde peliteoriaan

Nämä tehtävät eivät yleensä vaadi peliteorian tuntemusta . Tiettyjä peliteorian säännöksiä - intuitiivisesti ilmeisiä - voidaan kuitenkin käyttää (katso alla).

Pelityypit

Pelit ovat seuraavan tyyppisiä:

1. Vitsipeli

Tämän tyyppisissä peleissä voitto ei riipu pelaajien toimista ja se tiedetään etukäteen.

2. Symmetriapelit

Tällaisten ongelmien ratkaisemiseksi käytetään ajatusta symmetriasta - tietyn hetken kuluttua yksi pelaaja pelaa symmetrisesti toiselle.

3. Pelit voittamiseen ja häviämiseen

Tämän tyyppisten ongelmien ratkaisuprosessissa löydetään paikkoja, joihin pelaaja voi varmistaa itselleen voiton - voittamisen ja joista hän ei voi voittaa millään toiminnallaan - häviämällä.

Ideoita käytetty

Ongelmapeleissä käytetään useita ratkaisumenetelmiä , mutta usein toistuvia ideoita on useita:

  1. invariantti  — yksi pelaajista jokaisella siirrolla tuo pelin tilan johonkin tilaan (esimerkiksi jäljellä olevien käyttämättömien kenttien summaan), ja tällainen tila on voittoisa. Ja peli on rajallinen
  2. voittaminen todistetaan "lopusta" käyttämällä dynaamisen ohjelmoinnin ideoita : ensin todistetaan, että jossakin "toiseksi viimeisestä paikasta" pääset "viimeiseen" (voittoon), sitten - että tietystä sarjasta "toiseksi viimeisestä" voit päästä vain "toiseksi viimeiseksi" ja niin edelleen, kunnes todistamme, että "edellinen ... toiseksi viimeinen" on ensimmäinen paikka. (Katso Grandi-toiminto ).
  3. strategiaa ei tarvitse kehittää sen olemassaolon todistamiseksi (tässä tapauksessa riittää, että todistetaan strategian ns. "puhdas olemassaolo" rakentamatta sitä nimenomaisesti).
  4. jos äärellisessä deterministisessä pelissä, jossa on kaksi osallistujaa, osoitetaan, että toinen osallistujista ei voi voittaa, niin toinen voittaa.
  5. niin sanottu. syöttö: jos jossain tilanteessa pelaaja A voi siirtää liikkeen vastustajalle, niin A ei ole huonommassa asemassa kuin vastustajansa.
  6. niin sanottu. strategialainaus : oletetaan, että toisella pelaajalla on strategia; Näytämme, että ensimmäinen voi tarttua aloitteeseen ja käyttää tätä strategiaa itse.