Во неколку купчиња се наоѓаат по произволен број жетони. Два играчи најизменично повлекуваат потези. Во секој потег, играчот кој е на ред бира едно купче и од него зема произвлен број жетони, при што мора да земе барем еден жетон. Победник е оној играч кој ќе го земе последниот останат жетон. Прашањето кое ќе го разгледуваме е: кој играч победува во конкретна ситуација и како треба да игра за да победи? На сликата е даден пример со 3 купчиња во кои има по 8, 13 и 15 жетони.
Да разгледаме најпрво два едноставни примера и стратегијата која би ја примениле за да победиме.
Пример 1. Нека се дадени две купчиња, едното со 4, а другото со 7 жетони. Состојбата ќе ја бележиме со подреден пар (4,7). Во овој случај, првиот играч може да победи така што најпрво ќе земе 3 жетона од купчето со 7 жетони, по што и двете купчиња ќе имаат ист број жетони (4,4). Во вториот потег, вториот играч ќе земе извесен број жетони од некое од купчињата, при што ќе настане нова сотојба (4, k). Стратегијата која ќе треба да ја примени првиот играч е да во секој потег го изедначува бројот на жетоните кои се наоѓаат на секое од купчињата. Така, во нашиот пример, во третиот потег првиот играч би земал 4 – k жетони од првото купче доведувајќи нова состојба (k, k). Придржувајќи се кон оваа стратегија, првиот играч ќе победи после конечен број потези земајќи го последниот жетон.
Пример 2. Нека се дадени повторно две купчиња, но со ист почетен број на жетони. Сега, првиот играч со неговиот потег ќе ја наруши еднаквоста, па другиот играч применувајќи ја горната стратегија ќе може да победи.
Но, што ако се дадени повеќе купчиња секое со различен број жетони? Со која стратегија би победил првиот играч? Како би требало да играме за да бидеме сигурни дека кој потег и да го направи противникот, тоа сигурно нема да биде победничкиот потег?
Да претпоставиме дека имаме N купчиња секое со по xn жетони. На примерот на сликата имаме 3 купчиња (8, 13, 15). Идејата е најпрвин бројот на жетони во секое од купчињата да се претстави во неговата бинарна форма. Така, 8 би се претставил како 1000, 13 како 1101, а 15 како 1111. Потоа, формираме бинарна сума S од сите овие броеви, така што го занемаруваме преносот на битови при собирањето. Практично, секој бит од бинарната сума S се добива со XOR на битовите на соодветните места од секој xi. Oваа бинарна сума S уште се нарекува и НИМ сума и бележиме S=x1⨁x2⨁x3⨁…⨁xn.
При победничкиот потег (оној со кој се зема последниот жетон, или последните жетони, доколку сите се во едно купче) очигледно НИМ сумата ќе стане 0. Да забележиме дека обратното не важи, т.е. можно е НИМ сумата да се доведе до 0 без притоа да се земени сите жетони. Она што треба да се осигураме за да победиме е дека вториот играч никогаш нема НИМ сумата да ја доведе до 0, а тоа секако ќе го вклучи и случајот кога вториот играч го зема последниот жетон.
Стратегијата за победничката игра е одредена од следниве две тврдења чиј доказ е даден подолу:
1. Доколку моменталната НИМ сума е различна од 0, играчот кој е на ред секогаш ќе може да одигра потег со кој НИМ сумата ќе ја доведе до 0.
2. Доколку моменталната НИМ сума е еднаква на 0, независно од потегот на играчот кој е на ред, НИМ сумата по неговиот потег не може да биде повторно 0.
Користејќи го тврдењето 2, можеме да заклучиме дека вториот играч сигурно нема да ја доведе НИМ сумата на 0 доколку ние претходно ја доведеме на 0. Тврдењето 1 ни гарантира дека тоа ќе можеме секогаш да го направиме по потегот на противникот. Така, оставајќи му на вториот играч постојано почетна НИМ сума 0 пред тој да игра, ќе бидеме сигурни дека неговиот потег ќе резултира со НИМ сума различна од нула, а тоа значи дека тој никогаш нема да го направи победничкиот потег и дека ќе можеме да го употребиме првото тврдење во нашиот следен потег.
Заклучуваме дека првиот играч има победничка стратегија ако и само ако почетната НИМ сума од броевите на жетоните во купчињата е различна од 0. Тогаш тој со секој потег ќе ја доведува НИМ сумата до 0 и по конечен број потези ќе победи. Ако почетната НИМ сума е 0, тогаш со првиот потег, првиот играч би ја направил различна од 0 и во тој случај вториот играч има победничка стратегија.
Доказ на тврдењата 1 и 2
Нека со x1,x2,…,xn ги обележиме бројот на жетони во секое од N – те купчиња пред потегот, а со y1,y2,…,yn бројот на жетони во секое од N – те купчиња по потегот. Ако промената со потегот настанува во купчето k (k≤N), тогаш xi=yi за секое i≠k (бидејќи сите купчиња освен k – тото остануваат непроменети), освен за i=k за кое ќе важи xk>yk (бидејќи одземаме жетони од k – тото купче). Нека S=x1⨁x2⨁x3⨁…⨁xn и T=y1⨁y2⨁y3 ⨁…⨁yn се НИМ сумите пред и по потегот во кој се одземаат жетони од k – тото купче. Сега, земајќи ги предвид асоцијативноста и комутативноста на XOR операцијата како и својствата x⨁x=0 и x⨁0=x имаме :
T = 0 ⨁ T =
Тврдење 1. Доколку S≠0 , секогаш постои потег така што Т=0.
Доказ. Нека d е позицијата на најлевиот бит во НИМ сумата пред потегот (S) кој е еднаков на 1 и нека го избереме k така што битот во xk на позиција d е исто така еднаков на 1. Таков k мора да постои бидејќи во спротивно битот на позиција d во S ќе беше 0. Сега, ако дозволиме yk=S⨁xk , за Т имаме :
T = S ⨁ xk ⨁ yk=
Уште останува да докажеме дека при ваквиот избор на k, yk секогаш ќе биде помал од xk, т.е. од купчето секогаш ќе се вадат жетони. Имено, сите битови лево од позиција d остануваат исти во yk како и во xk. Битот на позиција d опаѓа од 1 на 0 (се комплементира бидејќи d го одбравме такво да битот на позиција d во S беше 1, а едно битна XOR операција помеѓу некоја вредност и 1 е секогаш комплементот на таа вредност). Сега, со промената на d – тиот бит од 1 во 0, вредноста на yk= xk- 2d и било која промена на битовите десно од d не може да направи разлика поголема од 2d-1 со што се гарантира дека ваквото yk ќе биде најмалку за 1 помало од xk. (види пример подолу)
Тврдење 2. Доколку S=0 , тогаш T≠0 независно од направениот потег.
Доказ. За Т имаме :
T = S ⨁ xk ⨁ yk=
бидејќи xk≠yk .
Забелешка. Во доказот користевме XOR операција помеѓу два или повеќе повеќе битни броја. Резултатот од ваквата операција е нов број чијшто бит на i – тата позиција е добиен со земање на XOR од сите битови кои се наоѓаат на истата i – та позиција во секој од броевите. Или пак, резултатот можеме да го гледаме како бинарна сума на сите тие броеви при што преносот при собирањето се испушта. Пример. (101)⨁(110) = 011; Пример. (1000)⨁(0101)⨁(1111) = 0010
Пример. Нека имаме 3 купчиња со состојба (8, 13, 15). Бинарните репрезентации на 8, 13, 15, како и на НИМ сумата S се дадени на сликата погоре. Најлевиот бит во S кој е еднаков на 1 се наоѓа на позиција 3 (позициите се нумерирани од 0 па нагоре почнувајќи од десно кон лево). Сега бираме купче (k) такво што бројот на жетоните во него претставен бинарно има единица на позиција d. Во нашиот пример, можеме да го избереме било кое од трите купчиња бидејќи сите имаат 1 на третата позиција. Можеше да се случи да имаме само една опција, но секако не може да се случи да нема ниту едно такво купче бидејќи позицијата d ја избравме таква да соодветниот бит во S е 1. Го одбираме третото купче со 15 жетони (x3 = 15) и бројот на жетони кои треба да ги оставиме го добиваме со S⨁x3. Во случајов тоа е 5 (y3 = 5), а треба да земеме x3 – y3 = 10 жетони.
Наместо од третото купче, можевме да земеме 6 жетони од првото или пак 7 жетони од второто купче воопшто не оддалечувајќи се од победничката стратегија.
PDF http://www.mediafire.com/?ay0ufrg831sn6rj
математички игри игра nim game теорија математика
Да разгледаме најпрво два едноставни примера и стратегијата која би ја примениле за да победиме.
Пример 1. Нека се дадени две купчиња, едното со 4, а другото со 7 жетони. Состојбата ќе ја бележиме со подреден пар (4,7). Во овој случај, првиот играч може да победи така што најпрво ќе земе 3 жетона од купчето со 7 жетони, по што и двете купчиња ќе имаат ист број жетони (4,4). Во вториот потег, вториот играч ќе земе извесен број жетони од некое од купчињата, при што ќе настане нова сотојба (4, k). Стратегијата која ќе треба да ја примени првиот играч е да во секој потег го изедначува бројот на жетоните кои се наоѓаат на секое од купчињата. Така, во нашиот пример, во третиот потег првиот играч би земал 4 – k жетони од првото купче доведувајќи нова состојба (k, k). Придржувајќи се кон оваа стратегија, првиот играч ќе победи после конечен број потези земајќи го последниот жетон.
Пример 2. Нека се дадени повторно две купчиња, но со ист почетен број на жетони. Сега, првиот играч со неговиот потег ќе ја наруши еднаквоста, па другиот играч применувајќи ја горната стратегија ќе може да победи.
Но, што ако се дадени повеќе купчиња секое со различен број жетони? Со која стратегија би победил првиот играч? Како би требало да играме за да бидеме сигурни дека кој потег и да го направи противникот, тоа сигурно нема да биде победничкиот потег?
Да претпоставиме дека имаме N купчиња секое со по xn жетони. На примерот на сликата имаме 3 купчиња (8, 13, 15). Идејата е најпрвин бројот на жетони во секое од купчињата да се претстави во неговата бинарна форма. Така, 8 би се претставил како 1000, 13 како 1101, а 15 како 1111. Потоа, формираме бинарна сума S од сите овие броеви, така што го занемаруваме преносот на битови при собирањето. Практично, секој бит од бинарната сума S се добива со XOR на битовите на соодветните места од секој xi. Oваа бинарна сума S уште се нарекува и НИМ сума и бележиме S=x1⨁x2⨁x3⨁…⨁xn.
При победничкиот потег (оној со кој се зема последниот жетон, или последните жетони, доколку сите се во едно купче) очигледно НИМ сумата ќе стане 0. Да забележиме дека обратното не важи, т.е. можно е НИМ сумата да се доведе до 0 без притоа да се земени сите жетони. Она што треба да се осигураме за да победиме е дека вториот играч никогаш нема НИМ сумата да ја доведе до 0, а тоа секако ќе го вклучи и случајот кога вториот играч го зема последниот жетон.
Стратегијата за победничката игра е одредена од следниве две тврдења чиј доказ е даден подолу:
1. Доколку моменталната НИМ сума е различна од 0, играчот кој е на ред секогаш ќе може да одигра потег со кој НИМ сумата ќе ја доведе до 0.
2. Доколку моменталната НИМ сума е еднаква на 0, независно од потегот на играчот кој е на ред, НИМ сумата по неговиот потег не може да биде повторно 0.
Користејќи го тврдењето 2, можеме да заклучиме дека вториот играч сигурно нема да ја доведе НИМ сумата на 0 доколку ние претходно ја доведеме на 0. Тврдењето 1 ни гарантира дека тоа ќе можеме секогаш да го направиме по потегот на противникот. Така, оставајќи му на вториот играч постојано почетна НИМ сума 0 пред тој да игра, ќе бидеме сигурни дека неговиот потег ќе резултира со НИМ сума различна од нула, а тоа значи дека тој никогаш нема да го направи победничкиот потег и дека ќе можеме да го употребиме првото тврдење во нашиот следен потег.
Заклучуваме дека првиот играч има победничка стратегија ако и само ако почетната НИМ сума од броевите на жетоните во купчињата е различна од 0. Тогаш тој со секој потег ќе ја доведува НИМ сумата до 0 и по конечен број потези ќе победи. Ако почетната НИМ сума е 0, тогаш со првиот потег, првиот играч би ја направил различна од 0 и во тој случај вториот играч има победничка стратегија.
Доказ на тврдењата 1 и 2
Нека со x1,x2,…,xn ги обележиме бројот на жетони во секое од N – те купчиња пред потегот, а со y1,y2,…,yn бројот на жетони во секое од N – те купчиња по потегот. Ако промената со потегот настанува во купчето k (k≤N), тогаш xi=yi за секое i≠k (бидејќи сите купчиња освен k – тото остануваат непроменети), освен за i=k за кое ќе важи xk>yk (бидејќи одземаме жетони од k – тото купче). Нека S=x1⨁x2⨁x3⨁…⨁xn и T=y1⨁y2⨁y3 ⨁…⨁yn се НИМ сумите пред и по потегот во кој се одземаат жетони од k – тото купче. Сега, земајќи ги предвид асоцијативноста и комутативноста на XOR операцијата како и својствата x⨁x=0 и x⨁0=x имаме :
T = 0 ⨁ T =
= S ⨁ S ⨁ T =
= S ⨁ (x1 ⨁ x2 ⨁ x3 ⨁ …⨁ xn ) ⨁ (y1 ⨁ y2 ⨁ y3 ⨁…⨁ yn )=
= S ⨁(x1 ⨁ y1) ⨁ (x2 ⨁ y2 ) ⨁…⨁ (xn⨁yn)=
= S ⨁ 0 ⨁ 0 ⨁…⨁ (xk⨁yk) ⨁ 0 ⨁ …⨁ 0=
= S ⨁ xk ⨁ yk
Тврдење 1. Доколку S≠0 , секогаш постои потег така што Т=0.
Доказ. Нека d е позицијата на најлевиот бит во НИМ сумата пред потегот (S) кој е еднаков на 1 и нека го избереме k така што битот во xk на позиција d е исто така еднаков на 1. Таков k мора да постои бидејќи во спротивно битот на позиција d во S ќе беше 0. Сега, ако дозволиме yk=S⨁xk , за Т имаме :
T = S ⨁ xk ⨁ yk=
= S ⨁ xk ⨁ (S ⨁ xk)=
= S ⨁ S ⨁ xk ⨁ xk=
= 0 Уште останува да докажеме дека при ваквиот избор на k, yk секогаш ќе биде помал од xk, т.е. од купчето секогаш ќе се вадат жетони. Имено, сите битови лево од позиција d остануваат исти во yk како и во xk. Битот на позиција d опаѓа од 1 на 0 (се комплементира бидејќи d го одбравме такво да битот на позиција d во S беше 1, а едно битна XOR операција помеѓу некоја вредност и 1 е секогаш комплементот на таа вредност). Сега, со промената на d – тиот бит од 1 во 0, вредноста на yk= xk- 2d и било која промена на битовите десно од d не може да направи разлика поголема од 2d-1 со што се гарантира дека ваквото yk ќе биде најмалку за 1 помало од xk. (види пример подолу)
Тврдење 2. Доколку S=0 , тогаш T≠0 независно од направениот потег.
Доказ. За Т имаме :
T = S ⨁ xk ⨁ yk=
= 0 ⨁ xk ⨁ yk=
= xk ⨁ yk ≠ 0 бидејќи xk≠yk .
Забелешка. Во доказот користевме XOR операција помеѓу два или повеќе повеќе битни броја. Резултатот од ваквата операција е нов број чијшто бит на i – тата позиција е добиен со земање на XOR од сите битови кои се наоѓаат на истата i – та позиција во секој од броевите. Или пак, резултатот можеме да го гледаме како бинарна сума на сите тие броеви при што преносот при собирањето се испушта. Пример. (101)⨁(110) = 011; Пример. (1000)⨁(0101)⨁(1111) = 0010
Пример. Нека имаме 3 купчиња со состојба (8, 13, 15). Бинарните репрезентации на 8, 13, 15, како и на НИМ сумата S се дадени на сликата погоре. Најлевиот бит во S кој е еднаков на 1 се наоѓа на позиција 3 (позициите се нумерирани од 0 па нагоре почнувајќи од десно кон лево). Сега бираме купче (k) такво што бројот на жетоните во него претставен бинарно има единица на позиција d. Во нашиот пример, можеме да го избереме било кое од трите купчиња бидејќи сите имаат 1 на третата позиција. Можеше да се случи да имаме само една опција, но секако не може да се случи да нема ниту едно такво купче бидејќи позицијата d ја избравме таква да соодветниот бит во S е 1. Го одбираме третото купче со 15 жетони (x3 = 15) и бројот на жетони кои треба да ги оставиме го добиваме со S⨁x3. Во случајов тоа е 5 (y3 = 5), а треба да земеме x3 – y3 = 10 жетони.
Наместо од третото купче, можевме да земеме 6 жетони од првото или пак 7 жетони од второто купче воопшто не оддалечувајќи се од победничката стратегија.
PDF http://www.mediafire.com/?ay0ufrg831sn6rj
математички игри игра nim game теорија математика
No comments:
Post a Comment