نیمبر

نیمبر (به انگلیسی: Nimber) یا عدد گراندی روشی برای مدل کردن بازی‌های ترکیبیاتی است. این روش اولین بار توسط مایکل گراندی پیشنهاد شد. قضیه اسپراگ-گراندی تضمین می‌کند که هر بازی منصفانه معادل یک کپه با اندازه مشخص در بازی نیم است که آن را نیمبر می‌نامیم.

خواص

نیمبرها اعداد ترتیبی با ضرب و جمع مخصوص به خود هستند که از خواص عملگر کمینه ناموجود(mex) نیز پشتیبانی می‌کند.

کمینه موجود

مقدار کمینه ناموجود(mex) یک مجموعه دلخواه $S$ از اعداد ترتیبی برابر است با کوچکترین عددی که در مجموعه ظاهر نمی‌شود. این عملگر در تعریف ضرب و جمع برای نیمبرها سودمند خواهد بود.

جمع

جمع روی نیمبرها به صورت بازگشتی و با استفاده از قاعده زیر تعریف می‌شود.

$\alpha \oplus \beta =mex(\{\alpha ^{\prime }\oplus \beta :\alpha ^{\prime }<\alpha \}\cup \{\alpha \oplus \beta ^{\prime }:\beta ^{\prime }<\beta \})$

ضرب

ضرب نیز به صورت بازگشتی تعریف می‌شود و از قاعده زیر استفاده می‌کند:

$\alpha \beta =mex(\{\alpha ^{\prime }\beta +allpha\beta ^{\prime }+\alpha ^{\prime }\beta ^{\prime }:\alpha ^{\prime }<\alpha ,\beta ^{\prime }<\beta \})$

جستارهای وابسته

• نیم (بازی)
• قضیه اسپراگ-گراندی

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Nimber». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۴ مارس ۲۰۱۷.