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