نیمبر

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

خواص

نیمبرها اعداد ترتیبی با ضرب و جمع مخصوص به خود هستند که از خواص عملگر کمینه ناموجود(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 \})$

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

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

منابع

• الگو:یادکرد-ویکی