جلسهی 17: تقارن و جفتسازی Symmetry and Pairing
گاهی برای بردن کافی است کارِ حریف را «آینهوار» تکرار کنی. نیمِ دو ستونی، نیمِ چند ستونی با قانون XOR، و بازیِ برداشتن از دو سرِ ردیف.
در این جلسه یاد میگیری
- استراتژیِ تقارن (تقلید آینهای) را در بازیها پیدا میکنی.
- در نیمِ دو و چند ستونی برنده را تشخیص میدهی.
- در بازیِ برداشتن از دو سر، با جفت کردنِ جایگاهها دستکم نصف را میگیری.
درس
دو ستون سنگ، هر کدام ۵ تا. در هر نوبت از یکی از ستونها هر چند تا که بخواهی برمیداری؛ هر کس آخرین سنگ را بردارد میبرد. تو شروع میکنی. چرا همیشه میبازی؟
تقارن: وقتی دو ستون برابرند، کامپیوتر فقط حرکتِ تو را روی ستونِ دیگر تکرار میکند و ستونها دوباره برابر میشوند. آخرین سنگ هم مال اوست. پس «دو ستونِ برابر» حالتِ باخت است و اگر ستونها نابرابر باشند، نفر اول با برابر کردنشان میبرد. اینجا امتحان کن:
نیم با چند ستون: عددِ هر ستون را در مبنای ۲ بنویس و رقمها را ستونی «بدونِ دهبر» جمع کن (هر ستون از رقمها: اگر تعدادِ ۱ها زوج بود ۰، فرد بود ۱). به این کار XOR میگویند. اگر نتیجه ۰ باشد، نوبتی باخت است؛ وگرنه برد. مثال: ۱، ۲، ۳ ← ۰۱، ۱۰، ۱۱ ← ۰۰ = باخت. ۳، ۵، ۷ ← ۰۱۱، ۱۰۱، ۱۱۱ ← ۰۰۱ = برد. (دو ستونِ برابر هم XORشان ۰ است؛ همان تقارن!)
برداشتن از دو سر: کارتهایی با عدد در یک ردیفاند و هر نوبت یکی از دو کارتِ سرِ ردیف برداشته میشود. اگر تعداد کارتها زوج باشد، نفر اول میتواند «همهی کارتهای جایگاهِ فرد» یا «همهی کارتهای جایگاهِ زوج» را بگیرد: هر بار که او یک فرد برمیدارد، دو سرِ ردیف زوج میشوند و حریف مجبور است زوج بردارد. پس با دیدن اینکه جمعِ کدام دسته بیشتر است، دستکم نصف را میگیرد.
چالشها
- Four and Seven (آسان)
- Six and Six (آسان)
- One, Two, Three (متوسط)
- Three, Five, Seven (متوسط)
- Cards at Both Ends (سخت)
- Coins on a Round Table (سخت)
← جلسهی 16: استراتژی برد: از آخر به اول جلسهی 18: فرایندها و الگوریتمها →