بازی ویتوف

در ۱۹۰۷، ریاضیدانی به نام ویتوف یک بازی ابداع کرد که در آن دو نفر بازی می‌کردند و هر یک به نوبت کبریت‌هایی از دو دسته کبریت بر می‌داشتند. در آغاز، هر یک از دو دسته کبریت، تعداد دلخواهی کبریت دارد، مثلا یکی m چوب کبریت و دیگری n چوب کبریت. جریان این بازی را می‌توانیم به وسیله جفت‌های (a,b)، تعقیب کنیم. که نشان دهنده تعداد کبریت‌های باقی‌مانده در هر یک از دو دسته، پس از انجام هر حرکت، هستند. به این ترتیب، بازی با جفت (m,n) آغاز می‌شود.
قواعد بازی
قواعد این بازی ایجاب می‌کنند که هر حرکت از یکی از سه نوع زیر باشند:
برداشتن کبریت از دسته ۱
برداشتن کبریت از دسته ۲
برداشتن کبریت از هر دو دسته، به تعداد مساوی از هر دسته.
بیان جبری این قاعده‌ها به صورت زیر است:
جفت (m,n) به یکی از جفت‌های زیر تبدیل می‌شود:
(m-t,n)
(m,n-t)
(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 ، دنباله‌های بیتی متناظر با عدد گنگ زیرند:
ملاحظه می‌کنیم که X همان عدد طلایی معروف است، و داریم:
قرار می‌دهیم
ودرمی یابیم که
و دنباله‌های بیتی متناظر، (n(1+Y و(n(1+X عبارتند از:
اگر (x,y) جفتی در W باشد، (y,x) نیز چنین است، زیرا ترتیبی که برای دو دسته کبریت قائل می‌شویم، اهمیتی ندارد. مناسب‌تر این است که عدد کوچکتر جفت را باa n نشان دهیم و جفت را به صورت (a n , b n ) بنویسیم، یعنی a n را اول بیاوریم.
اثبات قضیه
ابتدا نشان می‌دهیم که جفت‌های
(a n , b n )=(nt, )
دارای ویژگی‌های زیر هستند:
b n -a n =n,n=۱،۲,… ,(a ۰ , b ۰ )=(۰،۰).۱
عدد کوچکتر جفت n ام،a n کوچکترین عدد صحیحی است که در هیچ یک از جفت‌های قبلی به کار نرفته است؛ و به عکس، جفت‌های صادق در ویژگی‌های ۱ و ۲ به شکل (۶) هستند.
برای اثبات ویژگی (۱)، می‌نویسیم:
b n - a n = -nt
با در نظر گرفتن رابطه‌ی
t ۲ =۱+t
خواهیم داشت:
b n - a n =n(۱+t)-nt=n+nt-nt
و چون n یک عدد صحیح مثبت است، n+nt=n+nt، پس
b n - a n =n+nt-nt=n
برای اثبات ویژگی (۲)، به یاد می‌آوریم که دنباله‌های بیتی مکمل اند. این بدان معنی است که به ازای همه اعداد صحیح مثبت 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 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
a n )
c-(b n -n)=
c-b n +(d-c)=
d-b n
به (c-s,d-s)=(a n ,b n ) حرکت می‌کنیم که در W هست.
•حالت ۲)
در این حالت نتیجه می‌شودa l l l ، و بنا به فرض، b l =c l ، و به (c,d-s)=(b l ,a l در W حرکت می‌کنیم.
نتیجه می‌گیریم که همواره حرکت مجازی وجود دارد که جفت غیر برنده‌ای را به جفت برنده‌ای تبدیل کند.
بازی‌های منصفانه
بازی نیم