Spel (uppgift)

Ett spel  är en typ av olympiadproblem i matematik , där det krävs att man analyserar spelets strategi och/eller utnämner vinnaren av detta spel. Slutar vanligtvis med den traditionella frågan: "Vem vinner om det spelas rätt?"

Spelets egenskaper

Som regel, i uppgifter av denna typ av spel:

Avvikelser från de angivna egenskaperna är enstaka. En del av problemet består just i att bevisa dessa egenskaper.

"Rätt spel"

Ett "korrekt spel" i problem av denna klass är en vinnande strategi från spelteorin - en strategi, efter vilken spelaren kommer att vinna i motståndarens eventuella repressalier. Rätt spel är ett spel där båda motståndarna agerar rimligt och försöker vinna (inte ge efter för varandra).

Relation till spelteori

Dessa uppgifter kräver som regel inga kunskaper i spelteori . Vissa bestämmelser i spelteorin - intuitivt uppenbara - kan dock användas (se nedan).

Typer av spel

Spel är av följande typer:

1. Skämtspel

I den här typen av spel beror seger inte på spelarnas agerande och är känd i förväg.

2. Symmetrispel

För att lösa problem av denna typ används idén om symmetri - efter ett visst ögonblick spelar en spelare symmetriskt mot en annan.

3. Spel för att vinna och förlora positioner

I processen med att lösa problem av denna typ, hittas positioner, där spelaren kan säkerställa seger för sig själv - vinna, och från vilka han inte kan vinna med någon av sina handlingar - förlora.

Använda idéer

Problemspel använder en mängd olika metoder för att lösa , men det finns flera idéer som ofta upprepas:

  1. invariant  — en av spelarna för varje drag spelets tillstånd till något tillstånd (till exempel summan av de återstående obesatta fälten), och ett sådant tillstånd vinner. Och spelet är ändligt
  2. att vinna bevisas "från slutet", med hjälp av idéerna om dynamisk programmering : först bevisas det att när du är i en av de "näst sista positionerna" kan du komma till den "sista" (vinnande), sedan - det från en viss uppsättning av "näst sista" kan du bara komma till "näst sista" " och så vidare, tills vi bevisar att "föregående ... näst sista" positionen är den första. (Se Grandi funktion ).
  3. det är inte nödvändigt att utveckla en strategi för att bevisa dess existens (i detta fall räcker det att bevisa strategins så kallade "rena existens" utan att konstruera den explicit).
  4. om det i ett ändligt deterministiskt spel med två deltagare bevisas att en av deltagarna inte kan vinna, så kommer den andra att vinna.
  5. så kallade. pass: om spelare A i någon situation kan skicka draget till motståndaren, så är A i en position som inte är sämre än hans motståndare.
  6. så kallade. strategilån : anta att den andra spelaren har en strategi; vi visar att den första kan ta initiativet och använda denna strategi själv.