Симетрични игри. Въже
Преслав Наков
Алгоритмичните игри представляват изключително интересен клон на компютърната информатика. Посветени са им немалко книги по програмиране, а подобни задачи често се дават на задочни и очни състезания. В основата на решенията на подобен род задачи често залягат интересни идеи. Една такава универсална идея е тази за симетричните ходове, на която ще се спрем по-подробно на базата на три различни задачи. Да започнем с задача 4 от Задочния конкурс по информатика на сп.
Computer (публикувана в бр. 8/1998):Дадена е лента, разграфена на N клетки. Двама играчи A и B играят чрез последователни ходове игра, при която на всеки ход съответният играч зачертава най-много K съседни клетки, които дотогава са били незачертани. Печели играчът, който успее да направи последния ход.
Напишете програма, която определя за дадени N и K, дали съществува печеливша стратегия за играча, който започва пръв, т. е. дали той може да спечели независимо от начина на игра на другия играч.
Решение:
Предложената задача силно прилича на задача 2/1990 от Задочния конкурс по информатика на сп. Computer. Нека припомним нейното условие:
Двама играят следната игра. Дълго парче въже се разрязва последователно с ножица от първия и от втория играч. Губи този, който пръв отреже парче, по-късо от един сантиметър. Да се състави програма за компютър, която, започвайки първа, да играе срещу втория играч и да спечели играта.
В брой 2/1991 на сп. Computer е публикувано и следното решение:
"... При всяко разрязване на въжето нито едно от новополучените парчета не се изхвърля. Това уточнение ни позволява да мислим, че след разрязване може и да не разместваме парчетата, т. е. все едно, че само отбелязваме мястото на разрязване. Тази уговорка дава смисъл на понятието среда на въжето във всеки момент от играта. Това ни помага да опишем по-просто стратегията за първия играч (компютъра)...
При първия си ход компютърът "разрязва" въжето точно по средата. После, след всяко разрязване, направено от противника на някакво място, компютърът "разрязва" въжето на място, симетрично относно средата на въжето.
Тази стратегия винаги осигурява победа на компютъра, т. е. както и да играе вторият играч, компютърът ще победи, ако "спазва" описаните правила. Доказателството е очевидно: просто компютърът не може да загуби, защото от това ще следва, че противникът му вече е загубил на предния ход..."
Идеята на симетричната стратегия на игра намира широко приложение при подобен род задачи. Ще дадем още един пример:
Задача:
Дадена е кръгла маса с радиус R и достатъчен брой монети с радиус r < R. Двама играчи поставят последователно по една монета върху масата. Губи този, който няма къде да постави своята монета. Монетите се поставят така, че изцяло да лежат върху масата, като не се допука да се припокриват.
Решението на задачата силно прилича на това от предходната: На първия ход играч 1 поставя своята монета в центъа на масата, след което играе симетрично на своя съперник.
Но нека се върнем на нашата задача 4/1998. На пръв поглед като че ли изглежда, че между задачите 4/1998 и 2/1990 няма много общо. Действително задача 2/1990 има, така да се каже, "реален" характер, тъй като мястото на отрязване би могло да се зададе като реално число. Т. е. не се изисква получените в резултат на разрязването парчета да имат целочислени дължини. Това винаги гарантира победа на започващия разрязването, освен ако първоначалната дължина на въжето не е по-малка от два сантиметра.
Далеч обаче не стоят така нещата при задача 4/1998. Тук зачертаването, съответстващо на "разрязването" при 2/1990, е по-особено и в резултат на прилагането му се получават не 2, а 3 части, като третата (взетите съседни клетки) се изключва от по-нататъчни разглеждания. При това могат да се вземат само цял брой клетки, при това започващи от целочислени позиции, което определя "дискретния" ("целочислен") характер на задачата. При това положение не съвсем ясно дали стратегия
подобна на симетричната игра при задача 2/1990 би ни донесла нещо.Оказва се, че симетричната игра и тук води до елегантно решение на задачата, но идеята е малко по-различна. Целта на първия ход е да раздели клетките на две равни по дължина групи. Ясно е, че оттук нататък може стриктно да се следва принципът на симетрия, успешно използван при решението на 2/1990.
И така, ако започващият играта успее с първия си ход да раздели клетките на две равни по дължина групи, той несъмнено печели играта, продължавайки оттук нататък да играе симетрично на ходовете на своя противник. А какво става, ако началната конфигурация, т. е. началните стойности на N и K, не позволява такова разделяне? За да си отговорим на този важен въпрос, трябва да видим кога такова разделяне не е възможно.
Ако началната конфигурация има нечетен брой елементи (N=2k+1), то, вземайки на първия ход нечетен брой от средата, започващият очевидно успява да раздели клетките в две равни по дължина групи. При четен брой клетки пък (N=2k) следва да се вземат четен брой клетки от средата. Тъй като най-малкото нечетно число е 1, което е минималната допустима стойност за K, то следва, че при нечетно N започващият винаги (но не непременно единствено тогава) печели, вземайки средната клетка. При четно N обаче възниква проблем, тъй като най
-малкото четно число е 2, докато минималната стойност на K е 1. При K=1 започващият няма да може да раздели клетките на две равни по дължина групи. Дали обаче ще загуби? Очевидно отговорът на този въпрос е положителен.И така достигнахме до следното заключение: Започващият губи тогава и само тогава, когато N=2
K, K=1, k=1,2,3,...Сега не е трудно да се напише програма, решаваща задачата на произволен език за програмиране. Прилагам решения на Pascal, C и C++. Простотата на решението позволява реализация и на някои нетрадиционни езици като предложената комбинация от HTML и JavaScript: COMPZAD4. HTM.
#include <stdio.h>
main()
{ int N,K;
printf("N="); scanf("%d",&N);
printf("K="); scanf("%d",&K);
printf("%s%c","\nПечели ",(N%2==0&&K==1)?'B':'A');
}
CONST M : Array[Boolean] of Char = ('A','B');
VAR N,K : LongInt;
BEGIN
Write('N = '); ReadLn(N);
Write('K = '); ReadLn(K);
WriteLn('Печели играч ',M[(K=1) and not odd(N)])
END.
<HTML>
<BODY>
<FORM NAME='forma'>
N = <INPUT TYPE="text" NAME="N">
K = <INPUT TYPE="text" NAME="K">
<INPUT TYPE="submit" NAME="OK" VALUE="Кой печели?" ONCLICK="alert('Печели '+((document.forma.N.value%2==0&&document.forma.K.value==1)?'B':'A'));">
</FORM>
</BODY>
</HTML>