Кіріспе

Қағаз бен қарындашпен ойналатын математикалық ойын

Sprouts – математикалық қасиеттері зерттелуге болатын, ешқандай жаққа басымдық бермейтін қағаз бен қарындашпен ойналатын ойын. Оны математиктер Джон Хортон Конвей мен Майкл С. Паттерсон 1960 жылдардың басында Кембридж университетінде ойлап тапқан. Ойынның бастауы танымал «нүктелер мен қораптар» ойынынан да оңай, бірақ оның өту барысы әлдеқайда көркем және табиғи түрде дамиды.

Ережелер

Ойынды екі ойыншы ойнайды, бастапқыда қағаз бетіне бірнеше нүктелер салынған. Ойыншылар кезекпен ойнайды, әр кезегінде екі нүкте арасында (немесе нүктеден өзіне) сызық салып, сол сызық бойында жаңа нүкте қосады. Ойыншылар келесі ережелерді сақтауға міндетті: Сызық тура немесе қисық болуы мүмкін, бірақ өзіне-өзіне немесе басқа сызықтарға тиіспеуі немесе қиылыспауы керек. Жаңа нүкте, жаңа сызықтың соңғы нүктесінің үстіне салына алмайды. Осылайша, жаңа нүкте сызықты екі қысқа сызыққа бөледі. Кез келген нүктеге үштен артық сызық жалғастырылмауы керек. Осы ережеге сәйкес, нүктеден өзіне салынған сызық екі сызыққа саналады, ал жаңа нүктелерге екі сызық қосылған болып есептеледі. Бір нүктеге бір сызықпен екі рет тиіп, содан кейін оны басқа нүктеге жалғастыруға болмайды. "Қалыпты ойын" деп аталатын нұсқада, соңғы қимыл жасаған ойыншы жеңіске жетеді. "Мизерлік ойын" кезінде соңғы қимыл жасаған ойыншы жеңіледі. Misère Sprouts – ұйымдастырылған аймақта бәсекелестікпен ойналатын жалғыз мизерлік комбинаторлық ойын. Оң жақтағы суретте 2 нүктелі қалыпты ойынның мысалы көрсетілген. Төртінші қимылдан кейін көптеген нүктелер "өлген" – оларға үш сызық қосылғандықтан, жаңа сызықтың соңғы нүктесі ретінде қолдануға болмайды. Екі нүкте (жасыл түспен көрсетілген) әлі де "тірі", оларға үштен кем сызық жалғанған. Бірақ, тағы бір қимыл жасау мүмкін емес, себебі тірі нүктеден өзіне салынған сызық төрт жалғастыру тудырады, ал бір тірі нүктеден екіншісіне салынған сызық басқа сызықтарды қиып өтеді. Сондықтан бесінші қимыл жасау мүмкін емес, ал бірінші ойыншы жеңіледі. Ойынның соңында тірі қалған нүктелер "аман қалғандар" деп аталады және Sprouts-ты талдауда маңызды рөл атқарады.

Жылжыту саны

Sprouts ойыны әрқашан аяқталады, бірақ бұл факт ойын ережелерінен көрінбейді, себебі әр қадамда дақтардың саны арта түседі. Ойынның неге әрқашан аяқталуын түсіну үшін дақтардың санының орнына өмірлер санын (сызықтарды жалғау мүмкіндіктерін) қарастыру қажет. Содан кейін, егер ойын n дақтан басталатын болса, ол 3n - 1 қадамнан аспайды және 2n қадамнан кем болмайды. Келесі дәлелдемелерде ойын n дақтан басталады және дәл m қадамға созылады деп ескереміз.

Жылжытулардың ең көп саны

Әрбір орын үш өмірмен басталады және әрбір қимыл ойындағы өмірлердің жалпы санын бірге азайтады (сызықтың соңғы нүктелерінде екі өмір жоғалады, бірақ жаңа орынның бір өмірі болады). Ойын соңында 3n – m өмір қалды. Әрбір тірі қалған орында бір ғана өмір бар (әйтпесе, сол орынға қосылатын тағы бір қимыл болар еді), сондықтан дәл 3n – m тірі қалған орын бар. Кем дегенде бір тірі қалған болуы керек, атап айтқанда, соңғы қимылмен қосылған орын. Демек, 3n – m ≥ 1; сондықтан ойын 3n – 1 қимылдан артық болмайды. Бұл жоғарғы шек – нақты ең жоғары шек, және оған ойын соңында тек бір тірі қалған орын болатындай етіп, көптеген тәсілдермен қол жеткізуге болады. Мысалы, оң жақтағы ойында бір тірі қалған орын бар және 3n – 1 қимыл жасалған.

Жылжытулардың ең аз саны

Ойын соңында өлі нүкте, егер ол тірі қалғанға тікелей жанасатын болса немесе тірі қалғанда цикл болса, тірі қалғанға жанасқан нүктеге тікелей жанасатын болса, тірі қалғанның көршісі деп аталады. Бұл оң жақтағы суретте көрсетілген. Әрбір тірі қалғанның дәл екі өлі көршісі болады. Ешбір өлі нүкте екі түрлі тірі қалғанның көршісі бола алмайды, әйтпесе тірі қалғандарды байланыстыратын қадам болар еді. Басқа барлық өлі нүктелер (тірі қалғандардың көршілері емес) "бөлектелгендер" деп аталады (иврит тілінен аударғанда). Егер p бөлектелгендер болса, онда

бастапқы нүктелер + қадамдар = ойын соңындағы барлық нүктелер саны = тірі қалғандар + көршілер + бөлектелгендер. Теңдеуді өзгерту арқылы:

Осыдан ойын кем дегенде 2n қадамға созылады және бөлектелгендердің саны 4-ке бөлінеді. Ойын ұзақтығының бұл ең төменгі шегі – нақты ең төменгі шек. Оң жақтағы сурет 2n қадамнан тұратын аяқталған ойынды көрсетеді. Онда n тірі қалған, 2n көрші және 0 бөлектелгендер бар.

Нағыз ойындардағы маңызы

Нағыз ойындарда, көбінесе, қозғалыстардың саны k немесе k+1 болады, басқа нұсқалардың болуы өте сирек. Бір ойыншы аман қалғандарды қоршаған жабық аймақтар жасауға тырысады (соның арқасында ойналатын қозғалыстардың жалпы саны азаяды), ал екіншісі – «фарисейлерді» (қозғалыстардың санын арттыру үшін) жасауға ұмтылады.

Жеңіс стратегиясы

Sprouts - бұл теңдік мүмкін емес, шекті ойын болғандықтан, бастапқы дақтардың санына байланысты бірінші немесе екінші ойыншы үшін мінсіз стратегия бар. Белгілі бір бастапқы позиция бойынша басты сұрақ – егер олар мінсіз ойнаса, қай ойыншы жеңіске жете алатынын анықтау. Егер жеңіс стратегиясы бірінші ойыншыға арналған болса, онда позицияның нәтижесі "жеңіс" деп аталады, ал екінші ойыншыға арналған болса, онда позицияның нәтижесі "жеңіліс" деп аталады (өйткені бұл бірінші ойыншының көзқарасынан жеңіліс). Нәтиже бастапқы позицияның ойын ағашын құру арқылы анықталады. Бұл тек аз санды дақтар үшін қолмен жасауға болады, ал 1990 жылдан бері барлық жаңа нәтижелер компьютерлік іздеу арқылы алынды.

Қалыпты нұсқа

Математикалық ойындардағы жеңіс жолдары еңбегінде Денис Моллисон 6 орындық қалыпты ойынның екінші ойыншы үшін жеңіс әкелетінін 47 беттік қолмен жасалған талдау арқылы дәлелдеген. Бұл рекорд ұзақ уақыт бойы сақталды, 1990 жылы Дэвид Апплегейт, Гай Джейкобсон және Дэниел Слейтор Карнеги Меллон университетінде алғашқы компьютерлік талдау жасағанға дейін. Олар сол кездегі ең жақсы аппараттық қамтамасыз етумен 11 орынға дейін жетті. Апплегейт, Джейкобсон және Слейтор өз нәтижелерінде бір үлгіні байқады және бірінші ойыншының орындар саны алтыға бөлінгенде үш, төрт немесе бес қалдық қалдырса, жеңіске жететін стратегиясы бар деген болжам жасады. Бұл математикалық тұрғыдан алғанда, төмендегі кестеде көрсетілген үлгі алты орындық циклмен шексіз қайталанады дегенді білдіреді. Орындар 0 1 2 3 4 5 6 7 8 9 10 11 Қалыпты нәтиже Жеңіліс Жеңіліс Жеңіліс Жеңіс Жеңіс Жеңіс Жеңіліс Жеңіліс Жеңіліс Жеңіс Жеңіс Жеңіс

2001 жылы Риккардо Фокарди мен Фламина Луччо 7 орындық қалыпты ойынның жеңіліске ұшырағанын қолмен дәлелдеу әдісін сипаттады. Кейін, 2006 жылы Джош Джордан есептеу нәтижелерін 14 орынға дейін кеңейтті. 2007 жылы Жюльен Лемойн мен Саймон Вьенно есептеуді үдету үшін нимберлер тұжырымына негізделген алгоритмді ұсынды, оның көмегімен 32 орынға дейін жетті. Олар 2011 жылы есептеуді 44 орынға дейін кеңейтті, сондай-ақ 46, 47 және 53 орынмен үш жеке бастапқы позицияны да зерттеді. Қазіргі кездегі қалыпты ойын нәтижелері Апплегейт, Джейкобсон және Слейтордың болжамымен толық сәйкес келеді.

Misère нұсқасы

Sprouts-тың misère нұсқасының есептеу тарихы, сол адамдар қатысқан, қалыпты нұсқаға өте ұқсас. Дегенмен, misère нұсқасын есептеу қиын, ал прогресс айтарлықтай баяу болды. 1990 жылы Апплегейт, Джейкобсон және Слейтор тоғыз орынға дейін жетті. Олардың нәтижелеріне сүйене отырып, нәтиже бес кезеңдік тұрақты үлгіге сәйкес келеді деп болжады. Алайда, бұл болжам 2007 жылы Джош Джордан мен Роман Хорковтың misère талдауын 12 орынға дейін кеңейтуімен күшін жойды: 12 орындық misère ойыны – жеңіс, болжамдағы жеңіліс емес. Осы команда 2009 жылы 16 орынға жетті. Сол жылы Жюльен Лемон мен Саймон Виенно күрделі алгоритмдерді қолданып 17 орынға жетті. Олар 2011 жылы 20 орынға дейін талдауды кеңейтті. Қазіргі уақытта misère ойынының нәтижесі кейбір ерекше мәндермен алты ұзындықтағы үлгіні ұстанады деп болжануда: misère Sprouts-та қалдық (mod 6) бойынша нөл, төрт немесе бес болғанда бірінші ойыншы жеңіске жетеді, бірақ бірінші ойыншы бір орындық ойында жеңіп, төрт орындық ойында жеңіліске ұшырайды. Төмендегі кестеде екі ретсіз мән қалың әріппен көрсетілген. Орындар 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Misère нәтижесі Жеңіс Жеңіс Жоғалту Жоғалту Жеңіс Жоғалту Жоғалту Жеңіс Жеңіс Жеңіс Жоғалту Жоғалту