بازی های ترکیبیاتی

بازی های ترکیبیاتی از مباحث شیرین المپیاد کامپیوتر است .

در این بازی ها اکثرا اشاره به این میشود که چند بازیکن هوشمند مشغول انجام بازیی هستند . کدام یک میبرد .

تعاریف اولیه :

استراتژی برد : کسی که در تمام شرایط در صورت هوشمندانه بازی کردن برنده شود را «شخص دارای استراتژی برد» مینامیم

هوشمند : در این مسائل ذکر میشود که بازیکنان نادان نیستند ! یعنی بهترین عملکرد و حالت خود را انجام میدهند .

سوال : در یک کیسه n سنگ ریزه وجود دارد . علی در هر نوبت میتواند 0،1،2 سنگ از کیسه بردارد . حامد میتواند در هر نوبت 1،2،3 سنگ از کیسه بردارد . بازی را علی شروع میکند . برنده کسی است که آخرین سنگ را از کیسه بیرون بیاورد . چه کسی بازی را به ازای n=12345 میبرد ؟

پاسخ : به ازای n های مساوی 1 ، 2 به وضوح علی میبرد زیرا خود علی شروع کننده ی بازی است و قادر است این تعداد سنگ را از کیسه بیرون بیاورد و برنده شود .

به ازای n بزرگتر مساوی 3 با بررسی متوجه خواهید شد که همواره حامد میبرد . اثبات به خواننده واگذار میشود . راهنمایی اثبات :استقرا روی n