بازی جوانه ها

بازی جوانه‌ها یاSprout بازی ای برای دو بازیکن است. این بازی را دو ریاضی دان به نام هایJohn H. Conway و Michael S. Paterson در  سال 1967 در دانشگاه کمبریج ابداع کردند. بازی با رسم تعدادی نقطه آغاز می‌شود.

هر بازیکن در نوبت خود با خطی دو عدد از نقطه‌ها را به هم متصل می‌کند و نقطه ای روی این خط رسم می‌کند. این خط می‌تواند یک نقطه را به خودش وصل کند. بازنده کسی است که در نوبتش قادر به انجام حرکتی نباشد.

• هیچ خطی نباید خطوطی که قبلاً رسم شده  است را قطع کند.
• به هر نقطه حداکثر 3 خط می‌توان وصل کرد. به طور مثال در بازی زیر از نقاط A و B دیگر نمی توان استفاده کرد.

طبق معمول قبل از ادامه ی ماجرا می‌توانید با Applet زیر بازی کنید. برای شروع بازی روی کادر زیر کلیک کنید. البته این برنامه مقابل شما بازی نمی کند و فقط وسیله ای برای انجام بازی و بررسی حالت های مختلف است. در پنجره ی کوچک تر می‌توانید تعداد نقاط اولیه را تعیین کنید. حرکات غیر قابل قبول با رنگ زرد و نقاط مرده ( نقاطی که محل اتصالی ندارند ) با رنگ خاکستری مشخص می شوند. در ضمن با زدن دکمه ی وسط ماوس می‌توانید در هر جا یک نقطه ی جدید قرار دهید.

برای دیدن این بخش شما به نرم افزار جاوا نیاز دارید

حال چند سؤال ساده مطرح می‌ کنیم:

• آیا این بازی همیشه در تعداد متناهی مرحله تمام می‌شود و یا ممکن است هرگز تمام نشود؟ چرا؟

در نگاه اول به نظر می‌رسد که بازی همیشه ادامه پیدا می کند، اما اگر توجه کنید می‌بینید که چون روی هر نقطه سه محل اتصال وجود دارد، پس هر حرکت دو محل اتصال را می‌بندد و فقط یک محل اتصال باقی می‌ ماند. بنابر این محل های اتصال و در نتیجه بازی در جایی تمام خواهد شد. به کمک تکنیک شمارش محل های اتصال، می‌توانید به سؤال های زیر پاسخ دهید.

• اگر بازی را با n نقطه آغاز کنیم، بازی حداکثر می‌تواند شامل چند حرکت باشد؟
• آیا ممکن است بازی ای با حرکاتی کم تر از حداکثر حرکت های ممکن تمام شود؟
• اگر در یک بازی با n نقطه ابتدایی، حداکثر حرکات ممکن انجام شده باشد، چه کسی برنده خواهد بود؟ نفر اول یا دوم؟

*****

 به نظر شما برای برنده شدن در این بازی چه باید کرد؟ این که چه کسی برنده است به زوج یا فرد بودن تعداد کل حرکت های بازی بستگی دارد. پس با کنترل تعداد حرکات می‌توان برنده شد.

برای این که بدانیم چه طور می‌توان تعداد حرکات را کنترل کرد به وضعیت های پایان بازی توجه می‌کنیم. فرض کنیم n نقطه ی اولیه داریم و بازی مجموعاً دارای m حرکت می باشد، بنابر این تعداد نقطه‌ها در پایان m+n و مجموع محل های اتصال باقی مانده 1= 3n-m است ( با 3n محل اتصال شروع می‌کنیم و هر حرکت یکی از محل های اتصال کم می‌کند. )

هر نقطه ی زنده ای ( یعنی نقطه ای که هنوز محل اتصالی دارد،L ) در پایان بازی دو نقطه ی مرده ( D )، به عنوان نزدیک ترین همسایه هایش دارد. همان طور که در شکل می‌بینید این همسایگی تنها در دو صورت اتفاق می‌افتد. به بقیه ی نقاط مرده، نقاط رها می‌گوییم.

هیچ نقطه ی مرده ای نمی تواند همسایه ی دو نقطه زنده باشد، چرا که در این صورت می‌توانیم با وصل کردن دو نقطه ی زنده به بازی ادامه دهیم. بنابر این تعداد نقاط رها از این فرمول به دست می‌آید:

p = (m + n ) - ( l+ l ) = ( n + m ) -  ( n - m) = m -  n

m =  n +  p

از این فرمول می‌توان نتایج زیر را به دست آورد:

• تعداد حرکات یک بازی حداقل 2n تاست.
• تعداد نقاط رها، مضرب چهار است.
• اگر در هر مرحله ای از بازی بتوانیم به شکلی اطمینان پیدا کنیم که بازی در پایان، حداقل شامل p نقطه ی رها خواهد بود، آن گاه بازی حداقل 2n +  p حرکت ادامه پیدا خواهد کرد.

چک کنید

• اگر در هر جای بازی بتوانیم به شکلی اطمینان پیدا کنیم که بازی در پایان حداقل شامل l نقطه ی زنده می شود، آن گاه بازی حداکثر 3n - lحرکت خواهد داشت.

با استفاده از اطلاعاتی که تا این مرحله به دست آورده ایم، بازی زیر را که از 4 نقطه ی ابتدایی آغاز شده است، بررسی می‌کنیم. واضح است که اگر ناحیه ی بسته ی تشکیل شده توسط خطوط بازی - مثل ناحیه های بسته A وB وC در شکل - شامل یک نقطه ی زنده باشد - مثل p وr و q - آن گاه تا پایان بازی آن ناحیه شامل یک نقطه ی زنده خواهد بود.

پس بازی حداقل 3 نقطه ی زنده خواهد داشت. اگر دقت کنید می‌بینید که بازی حداقل یک نقطه ی رها دارد. بنابراین این بازی باید حداکثر 9 حرکت و حداقل  8 حرکت، ادامه پیدا کند. بنابراین بازی دقیقاً 9 حرکت طول خواهد کشید و این یعنی برنده شدن نفر اول.

در بازی هایی که تعداد نقاط کم تری دارند می‌توان با بررسی حالت‌ها و استفاده از تکنیک های بالا نشان داد که چه کسی می‌تواند برنده باشد. مثلاً در بازی های 1، 2 و 6 نقطه ای، نفر دوم می‌تواند همیشه برنده باشد و در بازی های 3، 4 و 5 نقطه ای، نفر اول.

جدول زیر نشان می‌دهد که چه کسی و با چند حرکت می‌تواند در بازی های با کم تر از 6 نقطه برنده باشد، سعی کنید تک تک حرکات این بازی‌ها را بیابید و برای ما به آدرس بفرستید. ( یعنی دقیقاً توضیح دهید که مثلاً چه طور و با چه حرکاتی نفر اول می‌تواند در 11 حرکت، بازی 5 نقطه ای را ببرد. )

برای بازی هایی با نقاط بیش تر کار سخت تر است. در سال 1990 سه ریاضی دان در آزمایش گاه هایBell با کمک کامپیوتر نشان دادند که در بازی های 7 و 8 نقطه ای، نفر دوم و در بازی های 9، 10 و 11 نقطه ای، نفر اول می‌تواند همیشه برنده باشد و تلاش برای بررسی بازی های با تعداد نقاط بیش تر هم چنان ادامه دارد.