نیمبر

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

خواص

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

کمینه موجود

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

جمع

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

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

ضرب

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

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

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

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

منابع

1. ریچارد ک. گای (۱۳۸۰)، بازی منصفانه، ترجمهٔ عبادالله محمودیان، آناهیتا آریاچهر، دانشگاه صنعتی شریف، موسسه انتشارات علمی از پارامتر ناشناخته |کشور= صرف‌نظر شد (کمک)

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