Spil (opgave)

Et spil  er en type olympiadeproblemer i matematik , hvor det er nødvendigt at analysere spillets strategi og/eller udpege vinderen af ​​dette spil. Ender normalt med det traditionelle spørgsmål: "Hvem vinder, hvis det spilles korrekt?"

Spilkarakteristika

Som regel i opgaver af denne type spil:

Afvigelser fra de angivne egenskaber er enkeltstående. En del af problemet består netop i beviset for disse egenskaber.

"Det rigtige spil"

Et "korrekt spil" i problemer i denne klasse er en vindende strategi fra spilteorien - en strategi, hvorefter spilleren vil vinde i modstanderens eventuelle gengældelseshandlinger. Det korrekte spil er et spil, hvor begge modstandere handler fornuftigt og forsøger at vinde (ikke give efter for hinanden).

Relation til spilteori

Disse opgaver kræver som udgangspunkt ikke kendskab til spilteori . Visse bestemmelser i spilteorien - intuitivt indlysende - kan dog bruges (se nedenfor).

Typer af spil

Spil er af følgende typer:

1. Spøgespil

I denne type spil afhænger sejren ikke af spillernes handlinger og er kendt på forhånd.

2. Symmetri spil

For at løse problemer af denne type bruges ideen om symmetri - efter et vist øjeblik spiller en spiller symmetrisk til en anden.

3. Spil for at vinde og tabe positioner

I processen med at løse problemer af denne type, findes positioner, hvor spilleren kan sikre sig sejr - vinde, og hvorfra han ikke kan vinde med nogen af ​​sine handlinger - tabe.

Brugte ideer

Problemspil bruger en række forskellige metoder til at løse , men der er flere ideer, der ofte gentages:

  1. invariant  — en af ​​spillerne bringer med hvert træk spillets tilstand til en eller anden tilstand (for eksempel summen af ​​de resterende ubesatte felter), og sådan en tilstand vinder. Og spillet er begrænset
  2. at vinde er bevist "fra slutningen", ved hjælp af ideerne om dynamisk programmering : først er det bevist, at du er i en af ​​de "næstsidste positioner" kan komme til den "sidste" (vindende), derefter - det fra et bestemt sæt af "næstsidste" kan du kun komme til "næstsidste" " og så videre, indtil vi beviser, at "forrige ... næstsidste" position er den indledende. (Se Grandi funktion ).
  3. det er ikke nødvendigt at udvikle en strategi for at bevise dens eksistens (i dette tilfælde er det nok at bevise den såkaldte "rene eksistens" af strategien uden at konstruere den eksplicit).
  4. hvis det i et endeligt deterministisk spil med to deltagere bevises, at en af ​​deltagerne ikke kan vinde, så vil den anden vinde.
  5. såkaldte. pass: hvis spiller A i en eller anden situation kan give træk til modstanderen, så er A i en position, der ikke er værre end hans modstanders.
  6. såkaldte. strategilån : antag, at den anden spiller har en strategi; vi viser, at den første kan gribe initiativet og selv bruge denne strategi.