موضوع مقاله: بازی ویتوف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بازی ویتوف | مقدمه: در آغاز، هر یک از دو دسته کبریت، تعداد دلخواهی کبریت دارد، مثلاً یکی m چوب کبریت و دیگری n چوب کبریت. | ## بخش 1: بازی ویتوف | که نشان دهندهٔ تعداد کبریت‌های باقی‌مانده در هر یک از دو دسته، پس از انجام هر حرکت، هستند. قواعد بازی قواعد این بازی ایجاب می‌کنند که هر حرکت از یکی از سه نوع زیر باشند: برداشتن کبریت از دستهٔ ۱ برداشتن کبریت از دستهٔ ۲ برداشتن کبریت از هر دو دسته، به تعداد مساوی از هر دسته. بیان جبری این قاعده‌ها به صورت زیر است: جفت (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 می‌انجامند؛ یعنی به موقعیت‌هایی که حریف می‌تواند با حرکت از آن جا بازی را ببرد. | ## بخش 2: بازی ویتوف | اگر با موقعیت برندهٔ نهایی (۰٬۰) آغاز کنیم، می‌توانیم فهرستی از تمام موقعیت‌های برنده در بازی ویتوف به دست آوریم و به این منظور، مثلاً، تمام جفت‌های (x,y) را برای x+y=۱, ۲, … بررسی می‌کنیم. به این طریق، می‌توان نشان داد که همهٔ جفت‌های (x,y) یا موقعیت‌های برنده‌اند یا موقعیت‌های بازنده. که n=1٬2,…، معین می‌کنند که در آن، {an} و {bn}، دنباله‌های بیتی متناظر با عدد گنگ زیرند: ملاحظه می‌کنیم که X همان عدد طلایی معروف است، و داریم: قرار می‌دهیم ودرمی یابیم که و دنباله‌های بیتی متناظر، n(1+Y] و n(1+X] عبارتند از: اگر (x,y) جفتی در W باشد، (y,x) نیز چنین است، زیرا ترتیبی که برای دو دسته کبریت قائل می‌شویم، اهمیتی ندارد. مناسب تر این است که عدد کوچکتر جفت را باan نشان دهیم و جفت را به صورت (an, bn) بنویسیم، یعنی an را اول بیاوریم. اثبات قضیه ابتدا نشان می‌دهیم که جفت‌های (an, bn)= nt], [nt۲ دارای ویژگی‌های زیر هستند: bn-an=n,n=۱٬۲,… ,(a۰, b۰)=(۰٬۰).۱ عدد کوچکتر جفت n ام،anکوچکترین عدد صحیحی است که در هیچ یک از جفت‌های قبلی به کار نرفته است؛ و به عکس، جفت‌های صادق در ویژگی‌های ۱ و ۲ به شکل (۶) هستند. این بدان معنی است که به ازای همهٔ اعداد صحیح مثبت i,j ، ai =bj و هر عدد صحیح مثبت به یکی از مجموعه‌های {ai} یا {bj} تعلق دارد. حال فرض کنید c کوچکترین عدد صحیح مثبتی باشد که به ازای k=۱٬۲,…,n-۱ نه در {ak} نه درbk} {. اما کوچکترین عدد صحیح موجود در این مجموعه‌ها an است، زیرا هر دو دنباله اکیداً صعودی اند و به ازای هر j>۰ ، aj<bj . | ## بخش 3: بازی ویتوف | اثبات عکس قضیه برای اثبات عکس قضیه کافی است، ملاحظه کنیم که ویژگی های(۱) و(۲) برای ساختن جفت‌ها به شیوهٔ بازگشتی در حکم قاعده‌ای هستند. جفت n ام عبارت است از (p,p+n) که در آن، p کوچکترین عدد صحیحی است که قبلاً به کار نرفته‌است. چون این قاعده به تعیین جفت‌ها به‌طور یکتا می‌انجامد، می‌توان نتیجه گرفت که دنباله‌های بیتی تنها دنباله‌هایی هستند که جفت‌هایی با ویژگی های(۱) و(۲) را به دست می‌دهند. حال نشان می‌دهیم که مجموعهٔ W مرکب از جفت‌های (an,bn) به صورت (۶)، واقعاً همهٔ موقعیت‌های برنده را در بردارد به این معنی که حرکت از هر چنین جفتی، به جفتی می‌انجامد که در W نیست و با مفروض بودن جفتی چون (c,d) که در W نباشد، حرکتی وجود دارد که به جفتی در W می‌انجامد. جفتی به شکل ۳ در W نیست، زیرا فقط nامین جفت (t=۰) نیست و با این حال حصول از موقعیتی در W با یک حرکت مجاز، در خارج از مجموعهٔ W هستند. نشان خواهیم داد که می‌توانیم عددی چون s تعین کنیم به قسمی که دست کم یکی از جفت‌های ۱. | ## جمع‌بندی | نتیجه می‌گیریم که همواره حرکت مجازی وجود دارد که جفت غیر برنده‌ای را به جفت برنده‌ای تبدیل کند.