نیمبر

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

خواص

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

کمینه موجود

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

جمع

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

ضرب

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

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

منابع

  1. ریچارد ک. گای (۱۳۸۰بازی منصفانه، ترجمهٔ عبادالله محمودیان، آناهیتا آریاچهر، دانشگاه صنعتی شریف، موسسه انتشارات علمی از پارامتر ناشناخته |کشور= صرف‌نظر شد (کمک)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.