Wythoffs o'yini - Wythoffs game

Wythoffning o'yini ikkita qoziq taymer bilan o'ynaydi

Uytofning o'yini ikki o'yinchi matematik ayirish o'yini, ikkita qoziq taymer bilan o'ynadi. Aktyorlar navbatma-navbat bir yoki ikkala qoziqdan hisoblagichlarni olib tashlashadi; ikkala qoziqdan hisoblagichlarni olib tashlashda har bir qoziqdan chiqarilgan hisoblagichlar soni teng bo'lishi kerak. O'yin bitta odam oxirgi hisoblagichni yoki hisoblagichlarni olib tashlaganida tugaydi va shu bilan g'alaba qozonadi.

O'yinning teng keladigan tavsifi bu bitta shaxmat malikasi kvadratlarning katta panjarasiga biron joyga joylashtirilgan va har bir o'yinchi qirolichani katakchaning pastki chap burchagiga qarab siljitishi mumkin: janubiy, g'arbiy yoki janubi-g'arbiy qismida har qanday qadam. G'olib, qirolichani burchakka ko'chiradigan o'yinchi.

Martin Gardner 1977 yil martida "Matematik o'yinlar ustuni "ichida Ilmiy Amerika o'yin Xitoyda 捡 石子 nomi ostida o'tkazilgan deb da'vo qilmoqda jiǎn shízǐ ("toshlarni yig'ish").[1] Gollandiyalik matematik W. A. ​​Wythoff 1907 yilda o'yinning matematik tahlilini nashr etdi.[2]

Optimal strategiya

Uythoffning Nim o'yinini tasavvur qilish. Eng chap chap kvadrat (1,1), qizil kvadratchalar esa sovuq holatga ega. G'olib kvadrat rasmga kiritilmaganligini unutmang.

O'yindagi har qanday pozitsiyani juftlik tomonidan tasvirlash mumkin butun sonlar (n, m) bilan n ≤ m, pozitsiyadagi ikkala qoziq hajmini yoki malikaning koordinatalarini tavsiflovchi. O'yin strategiyasi atrofida aylanadi sovuq pozitsiyalar va issiq pozitsiyalar: sovuq holatda, navbati harakatga kelgan o'yinchi eng yaxshi o'yin bilan yutqazadi, issiq holatda esa, navbati kelgan futbolchi eng yaxshi o'yin bilan g'alaba qozonadi. The maqbul strategiya - har qanday sovuq vaziyatga o'tish.

Pozitsiyalarni issiq va sovuqqa tasniflash amalga oshirilishi mumkin rekursiv quyidagi uchta qoidalar bilan:

  1. (0,0) - sovuq holat.
  2. Bir harakat bilan sovuq holatga erishish mumkin bo'lgan har qanday pozitsiya issiq holatdir.
  3. Agar har bir harakat issiq holatga olib keladigan bo'lsa, unda pozitsiya sovuq bo'ladi.

Masalan, shaklning barcha pozitsiyalari (0, m) va (m, m) bilan m > 0 issiq, qoida bo'yicha 2. Biroq, (1,2) pozitsiyasi sovuq, chunki undan erishish mumkin bo'lgan yagona pozitsiyalar (0,1), (0,2), (1,0) va (1,1), barchasi issiq. Sovuq holatlar (n, m) ning eng kichik qiymatlari bilan n va m (0, 0), (1, 2), (3, 5), (4, 7), (6, 10) va (8, 13). (ketma-ketlik A066096 va A090909 yilda OEIS ) (Shuningdek qarang OEISA072061)

Uchun misere o'yini ushbu o'yindan (0, 1) va (2, 2) sovuq pozitsiyalar va (n, m) bilan mn > 2 sovuq bo'lsa, agar (agar) (n, m) oddiy o'yinda sovuq.

Sovuq pozitsiyalar uchun formulalar

Vythoff sovuq pozitsiyalar oltin nisbat. Xususan, agar k har qanday natural son va

bu erda φ - oltin nisbat va biz dan foydalanamiz qavat funktsiyasi, keyin (nk, mk) bo'ladi kth sovuq holat. Raqamlarning ushbu ikki ketma-ketligi qayd etilgan Butun sonlar ketma-ketligining onlayn entsiklopediyasi kabi OEISA000201 va OEISA001950navbati bilan.

Ikki ketma-ketlik nk va mk ular Beatty ketma-ketliklari tenglama bilan bog'liq

Umuman olganda, Beatty ketma-ketliklari juftligi uchun bu ikkita ketma-ketlik mavjud bir-birini to'ldiruvchi: har bir musbat butun son har ikkala ketma-ketlikda bir marta aniq ko'rinadi.

Shuningdek qarang

Adabiyotlar

  1. ^ Vythoffning tugunni kesishda o'yini, iqtiboslar Martin Gardner kitobi Penrose plitkalari Trapdoor shifrlariga
  2. ^ Vythoff, V. A. (1907), "Nim o'yinining modifikatsiyasi", Nieuw Archief Wiskunde-ga murojaat qildi, 7 (2): 199–202

Tashqi havolalar