حساب کاربری
​
زمان تقریبی مطالعه: 1 دقیقه
لینک کوتاه

نیمبر

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

فهرست

  • ۱ خواص
    • ۱.۱ کمینه موجود
    • ۱.۲ جمع
    • ۱.۳ ضرب
  • ۲ جستارهای وابسته
  • ۳ منابع

خواص

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

کمینه موجود

مقدار کمینه ناموجود(mex) یک مجموعه دلخواه S {\displaystyle S}

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

جمع

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

α ⊕ β = m e x ( { α ′ ⊕ β : α ′ < α } ∪ { α ⊕ β ′ : β ′ < β } ) {\displaystyle \alpha \oplus \beta =mex(\{\alpha ^{\prime }\oplus \beta :\alpha ^{\prime }<\alpha \}\cup \{\alpha \oplus \beta ^{\prime }:\beta ^{\prime }<\beta \})}

ضرب

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

α β = m e x ( { α ′ β + a l l p h a β ′ + α ′ β ′ : α ′ < α , β ′ < β } ) {\displaystyle \alpha \beta =mex(\{\alpha ^{\prime }\beta +allpha\beta ^{\prime }+\alpha ^{\prime }\beta ^{\prime }:\alpha ^{\prime }<\alpha ,\beta ^{\prime }<\beta \})}

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

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

منابع

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