På ett 10×10-bräde finns en pjäs i varje ruta. En tillåten operation är att välja en diagonal som innehåller ett jämnt antal pjäser och ta bort en valfri pjäs från den diagonalen. Hur många pjäser kan man som mest ta bort med hjälp av sådana operationer?
Lösning:
Först och främst uppskattar vi hur många (eller snarare hur få) pjäser måste verkligen vara kvar på brädet.
Från början har vi 18 diagonaler med ett jämnt antal pjäser, och 20 med ett udda antal pjäser, totalt 38 stycken diagonaler. Vi kallar framöver diagonalerna för ”jämna” och ”udda” beroende på vilket antal pjäser som står på dem för tillfället.
Hur förändras detta antal när vi utför operationer? Jo, vi tar ju bort en pjäs från en jämn diagonal, så den diagonalen kommer att bli udda. Men varje pjäs står på två stycken diagonaler. Så den andra diagonalen kommer också att förändra sort.
Så antingen blir det jämn->udda och udda->jämn, vilket totalt sett inte förändrar antalet udda respektive jämna diagonaler eller så blir det jämn->udda och jämn->udda, vilket minskar antalet jämna diagonaler med 2 och ökar antalet udda diagonaler med 2.
På slutet, när vi inte längre kan utföra några tillåtna operationer, kommer antalet udda diagonaler alltså vara minst 20. Men en udda diagonal kan inte vara tom (för att 0 är ett jämnt antal). Så 20 är det minsta antalet icke-tomma diagonaler på slutet.
Varje pjäs kan bidra till max 2 diagonalers ”icke-tomhet”, vilket betyder att det måste finnas åtminstone 10 pjäser kvar på slutet.
Och det finns ett exempel på hur man kan ta bort pjäser på ett sådant sätt att det blir precis 10 kvar. Notera att om brädet målas schackrutigt, så kommer de vita diagonalerna inte ha något att göra med dem svarta (precis som en löpare alltid måste gå på samma färg under ett schackspel).
Därför om vi ta bort pjäserna från de vita rutorna så att det blir 5 kvar, så kan vi göra detsamma med de svarta rutorna (genom symmetrisk borttagning). Så här kan man ta bort från de vita rutorna, siffrorna nedan anger ordningen:
