Fibonachchi nim - Fibonacci nim

Fibonachchi nimani uyum tangalar bilan o'ynashadi

Fibonachchi nim matematik ayirish o'yini, o'yinning bir varianti nim. O'yin birinchi bo'lib 1963 yilda Maykl J. Vinixon tomonidan tasvirlangan bo'lib, uning ixtirosini Robert E. Gaskellga topshirgan. Bu Fibonachchi nim deyiladi, chunki Fibonachchi raqamlari uni tahlil qilishda og'ir xususiyat.[1]

Qoidalar

Fibonachchi nimani qoziqdan tangalarni yoki boshqa hisoblagichlarni navbatma-navbat olib tashlaydigan ikkita o'yinchi o'ynaydi. Birinchi harakat paytida o'yinchiga tangalarning hammasini olishga ruxsat berilmaydi va har bir keyingi harakat paytida olib tashlangan tangalar soni avvalgi harakatdan ikki baravar ko'p bo'lgan har qanday raqam bo'lishi mumkin. Ga ko'ra oddiy o'yin konvensiyasi, oxirgi tangani olgan o'yinchi g'alaba qozonadi.[2] Yoki Misere o'yini, oxirgi tangani olgan o'yinchi yutqazadi.

Ushbu o'yinni Fibonachchi nim deb nomlangan boshqa o'yindan ajratish kerak, unda o'yinchilar har bir yurishda har qanday Fibonachchi tangalarini olib tashlashlari mumkin.[3][4]

Strategiya

Fibonachchi nimidagi eng maqbul strategiyani "kvota" nuqtai nazaridan tavsiflash mumkin q (hozirda olib tashlanishi mumkin bo'lgan maksimal miqdordagi tangalar: birinchisidan tashqari, birinchi harakat paytida va undan keyin avvalgi harakatning ikki baravarigacha) va Zeckendorf vakili ketma-ket bo'lmagan Fibonachchi raqamlari yig'indisi sifatida joriy tangalar soni. Berilgan pozitsiya - bu yo'qotadigan pozitsiya (harakat qilmoqchi bo'lgan o'yinchi uchun) qachon q bu vakolatxonadagi eng kichik Fibonachchi raqamidan kam, aks holda g'oliblik pozitsiyasi. G'oliblik pozitsiyasida har doim barcha tangalarni olib tashlash (agar bunga ruxsat berilsa) yoki Zeckendorf vakolatxonasidagi eng kichik Fibonachchi raqamiga teng miqdordagi tangalarni olib tashlash har doim yutuqli harakatdir. Agar iloji bo'lsa, raqib o'yinchisi yutqazish holatiga duch keladi, chunki yangi kvota qolgan tangalar sonini Zeckendorfdagi eng kichik Fibonachchi raqamidan kichikroq bo'ladi. Yo'qotadigan pozitsiyadan har qanday harakat g'alaba qozonishga olib keladi.[1]

Xususan, boshlang'ich qoziqda Fibonachchi tangalari soni bo'lganida, birinchi o'yinchi uchun pozitsiya yo'qoladi (va ikkinchi o'yinchi uchun g'alaba qozonadi). Biroq, tangalarning boshlang'ich soni Fibonachchi raqami bo'lmaganida, birinchi o'yinchi har doim optimal o'yin bilan g'alaba qozonishi mumkin.[2]

Ushbu o'yinning noto'g'ri o'yini uchun, agar dastlab n tanga bo'lsa, unda birinchi o'yinchi n-1 tangani olib tashlashi va yutish uchun 1 tangani qoldirishi mumkin.

Misol

Masalan, dastlab 10 tanga bor deb taxmin qiling. Zekondorf vakili 10 = 8 + 2 ni tashkil qiladi, shuning uchun birinchi o'yinchining yutuqli harakati 8 ta tanga qoldirib, ushbu vakolatxonadagi eng kichik Fibonachchi raqamini olib tashlash bo'ladi. Ikkinchi o'yinchi eng ko'pi 4 tangani olib tashlashi mumkin, ammo 3 yoki undan ko'pini olib tashlash birinchi o'yinchining zudlik bilan g'alaba qozonishiga imkon beradi, shuning uchun ikkinchi o'yinchi 2 tangani oladi deb taxmin qiling, bu 6 = 5 + 1 tangani qoldiradi va birinchi o'yinchi yana oladi 5 ta tanga qoldirib, ushbu vakolatxonadagi eng kichik Fibonachchi raqami, 1 ta. Ikkinchi o'yinchi ikkita tanga olishi mumkin edi, ammo bu yana darhol yutqazadi, shuning uchun ikkinchi o'yinchi bitta tangani oladi va 4 = 3 + 1 ni qoldiradi. Birinchi o'yinchi yana 3 ta tanga qoldirib, ushbu vakolatxonadagi eng kichik Fibonachchi raqamini oladi. Endi, ikkinchi o'yinchi bitta yoki ikkita tanga oladimi-yo'qligidan qat'i nazar, birinchi o'yinchi keyingi harakatda o'yinda g'alaba qozonadi.

Nim qiymatlari

Fibonachchi nim an xolis o'yin har qanday pozitsiyada mavjud bo'lgan harakatlar harakatlanayotgan o'yinchining shaxsiga bog'liq emasligi sababli. Sprague-Grundy teoremasi bir nechta qoziq tangalar bo'lgan o'yin kengaytmasini tahlil qilish uchun ishlatilishi mumkin va har bir harakat tangalarni faqat bitta qoziqdan olib tashlaydi (xuddi shu qoziqdan oldingi harakatga nisbatan ko'pi bilan ikki baravar ko'p). Ushbu kengaytma uchunni hisoblash kerak nim-qiymat har bir qoziq; ko'p qoziqli o'yinning qiymati nim-sum bu nim qadriyatlarning. Biroq, ushbu qadriyatlarning to'liq tavsifi ma'lum emas.[5]

Adabiyotlar

  1. ^ a b Vinixon, Maykl J. (1963), "Fibonachchi Nim" (PDF), Fibonachchi har chorakda, 1 (4): 9–13.
  2. ^ a b Vajda, Stiven (2007), "Fibonachchi nim", Matematik o'yinlar va ularni qanday o'ynash kerak, Dover Books on Mathematics, Courier Corporation, 28–29 betlar, ISBN  9780486462776.
  3. ^ Alfred, aka U. (1963), "Fibonachchi raqamlarini o'rganish" (PDF), Fibonachchi har chorakda, 1 (1): 57–63. "Tadqiqot loyihasi: Fibonachchi nim" ga qarang. 63.
  4. ^ Hovuz, Jeremi C.; Xauells, Donald F. (1963), "Fibonachchi nimasi haqida ko'proq" (PDF), Fibonachchi har chorakda, 1 (3): 61–62.
  5. ^ Larsson, shahar; Rubinshteyn-Salzedo, Simon (2016), "Fibonachchi nimning Grundy qadriyatlari", Xalqaro o'yin nazariyasi jurnali, 45 (3): 617–625, arXiv:1410.0332, doi:10.1007 / s00182-015-0473-y, JANOB  3538534.