Спрэг-Грундигийн теорем. Ним¶

Оршил¶

Энэ теорем нь тэгш эрхт хоёр тоглогчийн тоглоом буюу боломжит нүүдэл ба хожих/хожигдох нь зөвхөн тоглоомын төлөвөөс хамаардаг тоглоомыг тодорхойлно. Өөрөөр хэлбэл хоёр тоглогчийн цорын ганц ялгаа нь тэдний нэг нь эхэлж нүүдэл хийдэгт оршино.

Түүнчлэн бид тоглоом төгс мэдээлэлтэй, өөрөөр хэлбэл тоглогчдоос ямар ч мэдээлэл нуугдаагүй (тэд дүрэм ба боломжит нүүдлүүдийг мэддэг) гэж үзнэ.

Тоглоом төгсгөлөг, өөрөөр хэлбэл тодорхой тооны нүүдлийн дараа тоглогчдын нэг нь өөр төлөв рүү шилжиж чадахгүй хожигдох байрлалд орно гэж үзнэ. Нөгөө талаас өрсөлдөгчдөө энэ байрлалыг үүсгэсэн тоглогч хожно. Ойлгомжтой нь энэ тоглоомд тэнцээ байхгүй.

Ийм тоглоомыг чиглэлтэй циклгүй граф-аар бүрэн тодорхойлж болно: оройнууд нь тоглоомын төлөвүүд, ирмэгүүд нь шилжилтүүд (нүүдлүүд) юм. Гарах ирмэггүй орой нь хожигдох орой болно (энэ оройноос нүүдэл хийх ёстой тоглогч хожигдоно).

Тэнцээ байхгүй тул бид тоглоомын бүх төлөвийг хожих эсвэл хожигдох гэж ангилж болно. Хожих төлөв гэдэг нь нөгөө тоглогч хамгийн сайнаар хариулсан ч түүний зайлшгүй ялагдалд хүргэх нүүдэл байдаг төлөв юм. Хожигдох төлөв гэдэг нь бүх нүүдэл нь нөгөө тоглогчийн хувьд хожих төлөв рүү хүргэдэг төлөв юм. Товчлон хэлбэл, хожигдох төлөв рүү шилжих дор хаяж нэг шилжилт байвал төлөв нь хожих, хожигдох төлөв рүү шилжих дор хаяж нэг шилжилт байхгүй бол төлөв нь хожигдох болно.

Өгөгдсөн тоглоомын төлөвүүдийг ангилах нь бидний зорилго юм.

Ийм тоглоомын онолыг Роланд Спрэг 1935 онд, Патрик Майкл Грунди 1939 онд бие даан боловсруулсан.

Ним¶

Энэ тоглоом нь дээр тайлбарласан хязгаарлалтуудыг дагадаг. Түүнчлэн төгс мэдээлэлтэй, тэгш эрхт хоёр тоглогчийн дурын тоглоомыг Ним тоглоом руу шилжүүлж болно. Энэ тоглоомыг судалснаар бид бусад бүх ижил төстэй тоглоомыг бодож чадах болно, гэхдээ энэ талаар дараа дэлгэрэнгүй үзнэ.

Түүхэн хувьд энэ тоглоом эртний үед түгээмэл байсан. Түүний гарал үүсэл магадгүй Хятадад байдаг — эсвэл ядаж л Jianshizi тоглоом түүнтэй маш төстэй. Европт хамгийн эртний дурдагдал нь 16-р зуунаас эхтэй. Нэрийг нь Чарльз Бутон өгсөн бөгөөд тэрээр 1901 онд энэ тоглоомын бүрэн шинжилгээг нийтэлсэн.

Тоглоомын тайлбар¶

Хэд хэдэн овоо байх бөгөөд тус бүр нь хэдэн чулуутай. Нэг нүүдэлд тоглогч ямар нэг нэг овооноос дурын эерэг тооны чулуу аваад хаяж болно. Хэрэв тоглогч нүүдэл хийж чадахгүй бол хожигдох ба энэ нь бүх овоо хоосорсон үед тохиолдоно.

Тоглоомын төлөвийг эерэг бүхэл тоонуудын мультиолонлогоор хоёрдмол утгагүйгээр тодорхойлно. Нүүдэл нь сонгосон бүхэл тоог чанд багасгахаас тогтоно (хэрэв тэг болбол олонлогоос хасагдана).

Шийдэл¶

Чарльз Л. Бутоны шийдэл дараах байдалтай:

Теорем. Овоонуудын хэмжээний xor-нийлбэр тэгээс ялгаатай байвал, зөвхөн тэр үед л одоогийн тоглогч хожих стратегитай байна. $a$ дарааллын xor-нийлбэр нь $a_1 \oplus a_2 \oplus \ldots \oplus a_n$ бөгөөд энд $\oplus$ нь битийн онцгойлох буюу (bitwise exclusive or) юм.

Баталгаа. Баталгааны түлхүүр нь өрсөлдөгчийн хувьд тэгш хэмт стратеги байх явдал юм. Xor-нийлбэр нь тэгтэй тэнцүү байрлалд нэг удаа орсон тоглогч урт хугацаанд түүнийг тэгээс ялгаатай болгож чадахгүйг бид харуулна — хэрэв тэд xor-нийлбэр тэгээс ялгаатай байрлал руу шилжвэл өрсөлдөгч нь xor-нийлбэрийг тэг болгож буцаах нүүдэлтэй үргэлж байна.

Бид теоремыг математик индукцээр батлана.

Хоосон Ним (бүх овоо хоосон буюу мультиолонлог хоосон)-ийн хувьд xor-нийлбэр тэг бөгөөд теорем үнэн.

Одоо бид хоосон биш төлөвд байна гэж үзье. Индукцийн таамаглал (ба тоглоомын циклгүй чанар)-ыг ашиглан бид одоогийнхоос хүрч болох бүх төлөвийн хувьд теорем батлагдсан гэж үзнэ.

Тэгвэл баталгаа хоёр хэсэгт хуваагдана: хэрэв одоогийн байрлалын хувьд xor-нийлбэр $s = 0$ бол энэ төлөв хожигдох буюу хүрч болох бүх төлөв $t \neq 0$ xor-нийлбэртэй болохыг бид батлах ёстой. Хэрэв $s \neq 0$ бол $t = 0$ байх төлөв рүү хүргэх нүүдэл байгааг батлах ёстой.

$s = 0$ гэж үзээд дурын нүүдлийг авч үзье. Энэ нүүдэл нь $x$ овооны хэмжээг $y$ хэмжээ хүртэл багасгана. $\oplus$-ийн энгийн шинж чанарыг ашиглавал

$$ t = s \oplus x \oplus y = 0 \oplus x \oplus y = x \oplus y $$

$y < x$ тул $y \oplus x$ нь тэг байж чадахгүй, иймээс $t \neq 0$. Энэ нь хүрч болох дурын төлөв (индукцийн таамаглалаар) хожих төлөв гэсэн үг тул бид хожигдох байрлалд байна.
$s \neq 0$ гэж үзье. $s$ тооны хоёртын дүрслэлийг авч үзье. Түүний тэргүүлэх (хамгийн их утгатай) тэг биш битийн индексийг $d$ гэе. Бидний нүүдэл нь хэмжээнийх нь $d$ дугаар бит тавигдсан овоон дээр байна (энэ нь заавал байх ёстой, эс тэгвээс уг бит $s$-д тавигдахгүй байх байсан). Бид түүний $x$ хэмжээг $y = x \oplus s$ хүртэл багасгана. $x$ ба $y$-ийн $d$-ээс их байрлал дахь бүх бит таарах ба $d$ дугаар бит $x$-д тавигдсан боловч $y$-д тавигдаагүй. Тиймээс $y < x$ бөгөөд энэ нь нүүдэл хууль ёсны байхад бидэнд хэрэгтэй бүх зүйл юм. Одоо бид:

$$ t = s \oplus x \oplus y = s \oplus x \oplus (s \oplus x) = 0 $$

Энэ нь бид хүрч болох хожигдох төлөвийг (индукцийн таамаглалаар) олсон бөгөөд одоогийн төлөв хожих гэсэн үг.

Дүгнэлт. Xor-нийлбэр өөрчлөгдөхгүй л бол Нимийн дурын төлөвийг эквивалент төлөвөөр солиж болно. Түүнчлэн хэд хэдэн овоотой Нимийг шинжлэхдээ бид түүнийг $s$ хэмжээтэй ганц овоогоор сольж болно.

Мизер тоглоом¶

Мизер тоглоом-д тоглоомын зорилго эсрэг байдаг тул сүүлчийн савааг авсан тоглогч тоглоомд хожигдоно. Мизер ним тоглоомыг стандарт ним тоглоомтой бараг адилаар оновчтой тоглож болох нь тогтоогддог. Санаа нь эхлээд мизер тоглоомыг стандарт тоглоом шиг тоглоод, тоглоомын төгсгөлд стратегиа өөрчлөх явдал юм. Шинэ стратегийг дараагийн нүүдлийн дараа овоо бүр хамгийн ихдээ нэг саваатай болох нөхцөлд нэвтрүүлнэ. Стандарт тоглоомд бид нэг саваатай тэгш тооны овоо үлдэх нүүдлийг сонгох ёстой. Гэвч мизер тоглоомд бид нэг саваатай сондгой тооны овоо байхаар нүүдэл сонгоно. Энэ стратеги ажилладаг, учир нь стратеги өөрчлөгддөг төлөв тоглоомд үргэлж гарч ирдэг бөгөөд энэ төлөв нь хожих төлөв юм, яагаад гэвэл энэ нь нэгээс олон саваатай яг нэг овоо агуулдаг тул ним нийлбэр 0 биш байна.

Тэгш эрхт тоглоом ба Нимийн эквивалент байдал (Спрэг-Грундигийн теорем)¶

Одоо бид дурын тэгш эрхт тоглоомын дурын төлөвийн хувьд түүнд харгалзах Нимийн төлөвийг хэрхэн олохыг сурна.

Нэмэгдэлтэй Нимийн тухай лемм¶

Бид Нимд дараах өөрчлөлтийг авч үзнэ: бид мөн сонгосон овоонд чулуу нэмэхийг зөвшөөрнө. Хэрхэн, хэзээ нэмэхийг зөвшөөрөх талаарх нарийн дүрэм биднийг сонирхохгүй, гэхдээ дүрмүүд нь бидний тоглоомыг циклгүй байлгах ёстой. Дараагийн хэсгүүдэд жишээ тоглоомуудыг авч үзнэ.

Лемм. Нимд нэмэгдэл нэмэх нь хожих ба хожигдох төлөвийг хэрхэн тодорхойлохыг өөрчлөхгүй. Өөрөөр хэлбэл нэмэгдэл нь ашиггүй бөгөөд бид тэдгээрийг хожих стратегид ашиглах шаардлагагүй.

Баталгаа. Тоглогч овоонд чулуу нэмсэн гэж үзье. Тэгвэл түүний өрсөлдөгч нүүдлийг нь зүгээр л буцааж болно — тоог өмнөх утга руу нь буцааж багасгана. Тоглоом циклгүй тул эрт орой хэзээ нэгэн цагт одоогийн тоглогч нэмэх нүүдэл хийж чадахгүй болж, ердийн Ним нүүдлийг хийх шаардлагатай болно.

Спрэг-Грундигийн теорем¶

Хоёр тоглогчийн тэгш эрхт тоглоомын $v$ төлөвийг авч үзье, түүнээс хүрч болох төлөвүүдийг $v_i$ гэе (энд $i \in \{ 1, 2, \dots, k \} , k \ge 0$). Энэ төлөвд бид $x$ хэмжээтэй ганц овоотой бүрэн эквивалент Ним тоглоомыг харгалзуулж болно. $x$ тоог $v$ төлөвийн Грундигийн утга буюу ним-утга гэж нэрлэнэ.

Түүнчлэн энэ тоог дараах рекурсив аргаар олж болно:

$$ x = \text{mex}\ \{ x_1, \ldots, x_k \}, $$

энд $x_i$ нь $v_i$ төлөвийн Грундигийн утга бөгөөд $\text{mex}$ (minimum excludant) функц нь өгөгдсөн олонлогт байхгүй хамгийн бага сөрөг биш бүхэл тоо юм.

Тоглоомыг граф гэж үзвэл бид гарах ирмэггүй оройноос эхлэн Грундигийн утгуудыг аажмаар тооцоолж болно. Грундигийн утга тэгтэй тэнцүү байх нь төлөв хожигдох гэсэн үг.

Баталгаа. Бид индукцээр баталгаа хийнэ.

Нүүдэлгүй оройнуудын хувьд $x$ утга нь хоосон олонлогийн $\text{mex}$ буюу тэг болно. Энэ нь зөв, учир нь хоосон Ним хожигдоно.

Одоо өөр дурын $v$ оройг авч үзье. Индукцээр бид түүний хүрч болох оройнуудад харгалзах $x_i$ утгууд аль хэдийн тооцоологдсон гэж үзнэ.

$p = \text{mex}\ \{ x_1, \ldots, x_k \}$ гэе. Тэгвэл дурын бүхэл $i \in [0, p)$-ийн хувьд Грундигийн утга нь $i$ байх хүрч болох орой байдаг гэдгийг бид мэднэ. Энэ нь $v$ нь $p$ хэмжээтэй ганц овоотой нэмэгдэлтэй Ним тоглоомын төлөвтэй эквивалент гэсэн үг. Ийм тоглоомд бид $p$-ээс бага бүх хэмжээний овоо руу шилжилттэй, магадгүй $p$-ээс их хэмжээтэй овоо руу шилжилттэй байна. Тиймээс $p$ нь одоо авч үзэж буй төлөвийн хувьд үнэхээр хайж буй Грундигийн утга юм.

Теоремын хэрэглээ¶

Эцэст нь бид тэгш эрхт хоёр тоглогчийн дурын тоглоомд хэрэглэж болох, тоглоомын хожих/хожигдох үр дүнг тодорхойлох алгоритмыг тайлбарлана.

Өгөгдсөн төлөвийн Грундигийн утгыг тооцоолохын тулд танд дараах зүйл хэрэгтэй:

Энэ төлөвөөс гарах бүх боломжит шилжилтийг ол
Шилжилт бүр нь бие даасан тоглоомуудын нийлбэр рүү хүргэж болно (degenerate case-д нэг тоглоом). Бие даасан тоглоом бүрийн Грундигийн утгыг тооцоолж, тэдгээрийг xor-нийлбэрлэ. Мэдээж ганц тоглоом байвал xor юу ч хийхгүй.
Шилжилт бүрийн Грундигийн утгыг тооцоолсны дараа бид төлөвийн утгыг эдгээр тоонуудын $\text{mex}$ болгон олно.
Хэрэв утга нь тэг бол одоогийн төлөв хожигдох, эс бөгөөс хожих болно.

Өмнөх хэсэгтэй харьцуулбал бид нэгтгэсэн тоглоом руу шилжилт байж болох баримтыг харгалзан үзнэ. Бид тэдгээрийг бие даасан тоглоомуудын Грундигийн утгатай тэнцүү овооны хэмжээтэй Ним гэж үзнэ. Бид тэдгээрийг Бутоны теоремын дагуу ердийн Ним шиг xor-нийлбэрлэж болно.

Грундигийн утгуудын хэв маяг¶

Грундигийн утгуудыг ашиглан тодорхой бодлого бодохдоо хэв маяг хайхын тулд утгуудын хүснэгтийг судлах нь ихэвчлэн ашигтай байдаг.

Онолын шинжилгээнд нэлээд хэцүү мэт санагдах олон тоглоомд Грундигийн утгууд нь үечилсэн эсвэл амархан ойлгомжтой хэлбэртэй болж хувирдаг. Тохиолдлын дийлэнх олонхид ажиглагдсан хэв маяг үнэн болж, хүсвэл индукцээр батлаж болдог.

Гэвч Грундигийн утгууд үргэлж ийм зүй тогтол агуулдгаас хол бөгөөд зарим маш энгийн тоглоомд ч ийм зүй тогтол байгаа эсэхийг асуух бодлого одоо ч нээлттэй хэвээр байна (ж.нь "Грундигийн тоглоом").

Жишээ тоглоомууд¶

Загалмай-загалмай¶

Дүрэм. $1 \times n$ хэмжээтэй нүдтэй судал авч үзье. Нэг нүүдэлд тоглогч нэг загалмай тавих ёстой, гэхдээ хоёр загалмайг зэрэгцүүлэн (зэргэлдээ нүдэнд) тавихыг хориглоно. Ердийнх шиг хүчинтэй нүүдэлгүй тоглогч хожигдоно.

Шийдэл. Тоглогч ямар нэг нүдэнд загалмай тавихад бид судлыг хоёр бие даасан хэсэгт хуваагдаж байна гэж бодож болно: загалмайн зүүн талд ба баруун талд. Энэ тохиолдолд загалмайтай нүд, түүнчлэн түүний зүүн ба баруун хөршүүд устгагдана — тэдгээрт өөр юу ч тавьж болохгүй. Тиймээс хэрэв бид нүднүүдийг $1$-ээс $n$ хүртэл дугаарлавал $1 < i < n$ байрлалд загалмай тавих нь судлыг $i-2$ ба $n-i-1$ урттай хоёр судал болгон хуваана, өөрөөр хэлбэл бид $i-2$ ба $n-i-1$ тоглоомуудын нийлбэр рүү шилжинэ. Загалмайг $1$ эсвэл $n$ байрлалд тэмдэглэсэн зах тохиолдолд бид $n-2$ тоглоом руу шилжинэ.

Тиймээс Грундигийн утга $g(n)$ нь дараах хэлбэртэй:

$$g(n) = \text{mex} \Bigl( \{ g(n-2) \} \cup \{g(i-2) \oplus g(n-i-1) \mid 2 \leq i \leq n-1\} \Bigr) .$$

Ингэснээр бид $O(n^2)$ шийдэлтэй боллоо.

Үнэн хэрэгтээ $g(n)$ нь $n=52$-оос эхлэн 34 урттай үетэй.