بازی ویتوف

قواعد این بازی ایجاب می‌کنند که هر حرکت از یکی از سه نوع زیر باشند:

1. برداشتن کبریت از دستهٔ ۱
2. برداشتن کبریت از دستهٔ ۲
3. برداشتن کبریت از هر دو دسته، به تعداد مساوی از هر دسته.

بیان جبری این قاعده‌ها به صورت زیر است: جفت (m,n) به یکی از جفت‌های زیر تبدیل می‌شود:

1. (m-t,n)
2. (m,n-t)
3. (m-t,n-t)

در همهٔ حالات،t ≥ ۱، زیرا دست کم یک کبریت برداشته می‌شود. تعداد کبریت‌هایی که برداشته می‌شوند، به میل بازیکن بستگی دارد؛ بازیکن اگر بخواهد می‌تواند تمام دستهٔ کبریت را بردارد. برنده کسی است که آخرین کبریت را بردارد. به عنوان نمونه، یک بازی می‌تواند به این ترتیب باشد: بعد از این که A بازی کرد، A به (۱۶٬۱۳) می‌رسد؛ B بازی می‌کند و (۱۲٬۹) حاصل می‌شود؛ A بازی می‌کند و (۵٬۹) حاصل می‌شود؛ B بازی می‌کند و (۲٬۶) حاصل می‌شود؛ A بازی می‌کند و (۲٬۱) حاصل می‌شود؛ B بازی می‌کند و باید به یکی از حالات (۱٬۱)و (۰٬۱)و (۲٬۰) یا (۱٬۰) دست یابد؛ در آخر A بازی می‌کند و به (۰٬۰) می‌رسد و برنده می‌شود.

باید توجه کرد که جفت (۲٬۱) که A در حرکت ماقبل آخر خود به آن دست یافت، یک موقعیت برنده‌است زیرا صرف نظر از این که B کدام یک از ۴ حرکت ممکن را انجام دهد، A می‌تواند در حرکت بعدی برنده شود.

به‌طور کلی ما جفتی چون (a,b) را به عنوان موقعیت برنده برای بازیکن A تعریف می‌کنیم، اگر استراتژیی وجود داشته باشد که صرف نظر از هر حرکتی که B بعد از موقعیت (a,b) انجام دهد، A بتواند بازی را (نه لزوماً در یک حرکت) ببرد. مثلاً (۲٬۱) در بازی بالا یک موقعیت برنده‌است. هر چهار حرکت مجاز از (۲٬۱)، به موقعیت‌های بازنده برای B می‌انجامند؛ یعنی به موقعیت‌هایی که حریف می‌تواند با حرکت از آن جا بازی را ببرد.

اگر با موقعیت برندهٔ نهایی (۰٬۰) آغاز کنیم، می‌توانیم فهرستی از تمام موقعیت‌های برنده در بازی ویتوف به دست آوریم و به این منظور، مثلاً، تمام جفت‌های (x,y) را برای x+y=۱, ۲, … بررسی می‌کنیم. به این طریق، می‌توان نشان داد که همهٔ جفت‌های (x,y) یا موقعیت‌های برنده‌اند یا موقعیت‌های بازنده. ولی معلوم شده‌است که از این فرایند خسته کننده، می‌توان کاملاً صرف نظر کرد. ویتوف خود همهٔ موقعیت‌های برنده را با استفاده از یک فرمول، مشخص کرد.

موقعیت‌های برنده را جفت‌های (0٬0) و (a_n, b_n) و ... که n=1٬2,…، معین می‌کنند که در آن، {a_n} و {b_n}، دنباله‌های بیتی متناظر با عدد گنگ زیرند:

${\displaystyle X={\frac {-1+{\sqrt {5}}}{2}}}$

ملاحظه می‌کنیم که X همان عدد طلایی معروف است، و داریم:

${\displaystyle {\frac {1}{x}}={\frac {2}{-1+{\sqrt {5}}}}={\frac {1+{\sqrt {5}}}{2}}=1+X}$

قرار می‌دهیم

${\displaystyle t=1+X={\frac {1+{\sqrt {5}}}{2}}=Y}$

ودرمی یابیم که

${\displaystyle 1+Y={\frac {3+{\sqrt {5}}}{2}}=t^{2}=1+t}$

و دنباله‌های بیتی متناظر، [(n(1+Y] و[(n(1+X] عبارتند از:

اگر (x,y) جفتی در W باشد، (y,x) نیز چنین است، زیرا ترتیبی که برای دو دسته کبریت قائل می‌شویم، اهمیتی ندارد. مناسب تر این است که عدد کوچکتر جفت را باa_n نشان دهیم و جفت را به صورت (a_n, b_n) بنویسیم، یعنی a_n را اول بیاوریم.

ابتدا نشان می‌دهیم که جفت‌های

دارای ویژگی‌های زیر هستند:

b_n-a_n=n,n=۱٬۲,… ,(a_۰, b_۰)=(۰٬۰).۱

عدد کوچکتر جفت n ام،a_nکوچکترین عدد صحیحی است که در هیچ یک از جفت‌های قبلی به کار نرفته است؛ و به عکس، جفت‌های صادق در ویژگی‌های ۱ و ۲ به شکل (۶) هستند.

برای اثبات ویژگی (۱)، می‌نویسیم:

با در نظر گرفتن رابطه ی

خواهیم داشت:

و چون n یک عدد صحیح مثبت است، [n+nt]=n+[nt]، پس

برای اثبات ویژگی (۲)، به یاد می‌آوریم که دنباله‌های بیتی مکمل‌اند. این بدان معنی است که به ازای همهٔ اعداد صحیح مثبت i,j ، a_i =b_j و هر عدد صحیح مثبت به یکی از مجموعه‌های {a_i} یا {b_j} تعلق دارد.

حال فرض کنید c کوچکترین عدد صحیح مثبتی باشد که به ازای k=۱٬۲,…,n-۱ نه در {a_k} نه درb_k} {. پس c، به ازای k ≥ n، یا باید در {a_k} باشد یا در {b_k}. اما کوچکترین عدد صحیح موجود در این مجموعه‌ها a_n است، زیرا هر دو دنباله اکیداً صعودی اند و به ازای هر j>۰ ، a_j<b_j . بنابراین، c=a_n .

برای اثبات عکس قضیه کافی است، ملاحظه کنیم که ویژگی های(۱) و(۲) برای ساختن جفت‌ها به شیوهٔ بازگشتی در حکم قاعده‌ای هستند. جفت n ام عبارت است از (p,p+n) که در آن، p کوچکترین عدد صحیحی است که قبلاً به کار نرفته‌است. چون این قاعده به تعیین جفت‌ها به‌طور یکتا می‌انجامد، می‌توان نتیجه گرفت که دنباله‌های بیتی تنها دنباله‌هایی هستند که جفت‌هایی با ویژگی های(۱) و(۲) را به دست می‌دهند.

حال نشان می‌دهیم که مجموعهٔ W مرکب از جفت‌های (a_n,b_n) به صورت (۶)، واقعاً همهٔ موقعیت‌های برنده را در بردارد به این معنی که حرکت از هر چنین جفتی، به جفتی می‌انجامد که در W نیست و با مفروض بودن جفتی چون (c,d) که در W نباشد، حرکتی وجود دارد که به جفتی در W می‌انجامد.

فرض کنید (a_n,b_n) جفت مفروضی در W باشد. پس از یک حرکت مجاز، یکی از جفت‌های زیر ممکن است حاصل شود:

۱)(a_n-t,b_n)

۲)(a_n,b_n-t)

a_n-t,b_n-t)(۳)

جفت‌هایی به شکل ۱ و ۲ در W نیستند، زیرا هر یک از آن‌ها شامل عددی متعلق به جفت n ام است و هر عدد صحیح مثبت در یک و تنها یک جفت متعلق به W می‌آید؛ یعنی اگر b_n در (a_n,b_n) بیاید، نمی‌تواند در هیچ موقعیت برندهٔ دیگری بیاید. جفتی به شکل ۳ در W نیست، زیرا فقط nامین جفت (t=۰) نیست و با این حال حصول از موقعیتی در W با یک حرکت مجاز، در خارج از مجموعهٔ W هستند. حال فرض کنید جفت (c,d) در W نباشد. نشان خواهیم داد که می‌توانیم عددی چون s تعین کنیم به قسمی که دست کم یکی از جفت‌های

۱. (c-s,d)

۲. (c,d-s)

۳. (c-s,d-s)

در W باشد.

در حالت c=d، انتخاب می‌کنیم: s=c=d و با یک حرکت به موقعیت برندهٔ نهایی (۰٬۰) می‌رسیم: (c-s,d-s)=(۰٬۰).

فرض کنید c≠d؛ و سپس اعداد را طوری نامگذاری کنید که c<d. حال هر عدد صحیح مثبت در دقیقاً یکی از دنباله‌های بیتی قرار دارد، پس برای عدد صحیح c یکی از دو حکم زیر برقرار است:

۱) به ازای k ای، c=a_k

۲) به ازای l ای، c=b_l ؛

یعنی c به یکی از موقعیت‌های برندهٔ زیر تعلق دارد

۱) (c,b _k)=(a_k,b _k)

۲) (a_l,c)=( a_l,b_l)

•حالت ۱)

اگر b_k<d، قرار می‌دهیم s=d-b_k و به (c,d-s)=(a_k,b_k) حرکت می‌کنیم که در W است.

اگر d<b_k، آن گاه از c<d<b_k نتیجه می‌شود : ۰<d-c<b_k-c=k . عدد صحیح مثبت n=d-c را محاسبه می‌کنیم؛ بنابر آخرین نابرابری، n<k. قرار می‌دهیم:

به (c-s,d-s)=(a_n,b_n) حرکت می‌کنیم که در W هست.

•حالت ۲)

در این حالت نتیجه می‌شودa_l<d، زیرا به ازای هر l، a_l<b_l، و بنا به فرض، b_l=c<d. قرار می‌دهیم s=d-a_l، و به (c,d-s)=(b_l,a_l در W حرکت می‌کنیم.

نتیجه می‌گیریم که همواره حرکت مجازی وجود دارد که جفت غیر برنده‌ای را به جفت برنده‌ای تبدیل کند.

• بازی‌های منصفانه
• بازی نیم

• ابتکارهایی در ریاضیات-راس هانسبرگر-ترجمه سیامک کاظمی-ریاضیات پیش دانشگاهی۲۳-مرکز نشر دانشگاهی، تهران-۱۳۷۱