بچهها بیاین یه بازی خفن رو با هم بررسی کنیم به اسم «Multiplicative Modular Nim» که خودشون براش یه اسم باحال گذاشتن: MuM (مخفف همون اسم طولانیه!). اگه نیم رو میشناسین، میدونین که یه بازی کلاسیک ریاضیه که توش چندتا توده سنگ یا چوب داریم و بازیکنا یکییکی نوبتشون میشه تا یکی از تودهها رو انتخاب کنن و هر چندتایی دلشون میخواد ازش بردارن. کسی که آخرین سنگو برداره، برندست. تحلیل اینکه تو هر وضعیت کی برندس، تو نیم معمولی با چیزی به اسم nim-sum انجام میشه که همون جمع بیت به بیت (یا همون XOR) هست.
خب حالا MuM اومده یه پیچ باحال بندازه. توی MuM بهجای اینکه سایز تودهها رو باهم جمع کنیم (یا nim-sum بگیریم)، همه رو در هم ضرب میکنیم و بعدش با یه عدد m (یعنی مدول) قسمت میکنیم و باقیمونده رو نگه میداریم. اینجا «ضرب مدولار» اومده جای nim-sum. مدولار یعنی هر چیزی رو بذارین تو جدول ضرب، بعد باقیمونده تقسیم بر یه عدد رو نگه دارین؛ مثلاً ضرب مدول ۵ یعنی اعداد رو تقسیم بر ۵ کنید و باقیمونده رو پیدا کنید.
حالا جالب اینجاست که این کار همه معادلات بازی نیم رو به هم میریزه و براش یه دنیای جدید و متفاوت میسازه! نویسندههای مقاله اومدن و یه تحلیل کامل، دقیق و مشابه همون سبک قدیمی نیم (که بهش Bouton-style analysis میگن) آماده کردن، مخصوصاً وقتی اون عدد m یه عدد اول باشه (یعنی فقط بر خودش و ۱ بخشپذیر باشه).
آ، یه چیز مهم! تو نیم کلاسیک تئوریای داریم به اسم تئوری Sprague-Grundy که میگه هر موقعیت بازی رو میتونی با یه عدد معروف به nimber نمایش بدی که عملاً ارزش اون موقعیت رو مشخص میکنه (یه جور «عدد برنده یا بازنده بودن» جایگاه فعلی بازی). تو MuM، نویسندهها یه چیز مشابه تعریف کردن به اسم «mumber». حالا mumber یعنی چی؟ عملاً همون nimber ـه، ولی به جای جمع XOR، از ضرب و مدولار استفاده میکنیم. دوستان تو مقاله براش یه روال بازگشتی (یا همون recursion) باحال ساختن که بهش multiplicative mex میگن. mex یعنی «کمترین عدد طبیعی که تو بین مقادیر فعلی نیست»؛ مثلاً بین ۰، ۱، ۳ کمترین عدد جاافتاده میشه ۲.
تحلیل نتونستنیشون نشون دادن مقدار mumber هر حالت از بازی همون حاصلضرب تودهها (mod m) هست. و اگه چندتا بازی MuM رو همزمان بازی کنین (که بهش disjunctive sum یا جمع جداشونده میگن؛ یعنی هرلحظه هرکدوم از بازیارو میتونی حرکت کنی)، mumber این مجموعه بازم با ضرب مدولار به دست میاد، یعنی کاملاً برعکس نیم کلاسیک که nimber رو باید با XOR جمع بزنی.
یه نکته خیلی جالب اینه که وقتی اون عدد m اول نیست (مثلاً ۶ که میشه ۲×۳)، MuM میتونه به کمک یه قضیه معروف تو ریاضیات یعنی Chinese Remainder Theorem (یا همون قضیه باقیمانده چینی) به چندتا زیربازی مستقل شکسته بشه. این قضیه میگه میتونی وضعیت رو جداگانه برای عوامل اول m نگاه کنی و بعداً جوابها رو ترکیب کنی.
کار جالبتر این مقاله اینه که MuM رو حتی به دنیاهای پیشرفتهتری هم میبره، مثلاً به “finite field” ها. این فیلدها تو ریاضی میشن دستههایی از اعداد که با قوانین خطی و ضربی خاص خودشون کار میکنن؛ نمونه معروفش تو رمزنگاری AES هست (همون S-box که مغز متفکر رمزگذاری AES محسوب میشه!). هدف نویسندهها این بوده بچهها راحتتر و ملموستر ساختار جبری سخت اونجا رو بفهمن.
اما اینجا یه مشکل پیش میاد: اگه تودهها رو با اعداد صحیح نشون بدیم و بخوایم بفرستیم تو finite field، ممکنه چندتا حالت مختلفِ توده، به یه عدد تو field نگاشت بشن (یعنی دست آخر، چندتا چیدمان مختلف در نهایت به یه عدد تو فیلد میرسن). نویسندهها برای اینکه این سردرگمی پیش نیاد، یه مدل دقیق تعریف کردن به اسم Canonical Heap Model، که یعنی هر وضعیت دقیقاً یه جور توی بازی نشون داده بشه.
تا الان اولین بارِ که یه تحلیل کامل و سیستماتیک واسه یه نسخه مولتیپلیکتیو مدولار از نیم ارائه شده و حتی فراتر رفته و واسش یه جبر ترکیبیاتی کاملاً جدید ساخته شده که دیگه توش خبری از جمع و XOR نیست!
خلاصه MuM یه بازی ناب، با ریاضی و منطق پیشرفته، که هم واسه سرگرمی ریاضینوازا عالیه، هم یه راه مناسب برای یاد گرفتن مفاهیم جبری و تئوری بازیهاست. دفعه بعد که خواستین نیم بازی کنین، یه بار MuM رو تست کنین؛ هم لذت میبرید، هم مغزتون ورزش میکنه! 😄
منبع: +
