جلسهی 34: یک مسئلهی بلند: بازیِ گلدانها A Long Problem: The Pot Game
سؤالهای تشریحیِ مرحلهی دوم بلندند و چند قدم دارند. با یک بازیِ دونفره روی یک ردیف گلدان یاد میگیری از کجا شروع کنی: حالتهای کوچک، جدول، حدس، و اثباتِ هر دو طرف.
در این جلسه یاد میگیری
- یک مسئلهی بلند را با حالتهای کوچک و یک جدول شروع میکنی.
- از جدول یک حدس میسازی.
- میدانی جوابِ یک بازی دو اثبات لازم دارد: یک راهبرد برای هر بازیکن.
درس
سارا و کیان یک ردیف گلدانِ خالی دارند. هر بار سارا دو گلدانِ خالیِ کنارِ هم را نشان میدهد و کیان در یکی از آن دو گل میکارد. بازی وقتی تمام میشود که دیگر دو گلدانِ خالیِ کنارِ هم نمانده باشد. کیان میخواهد آخرِ بازی گلها زیاد باشند و سارا میخواهد کم باشند. اگر هر دو بهترین بازی را بکنند، چند گل کاشته میشود؟
مسئلهی بلند را با بازی کردن شروع کن. یک بار جای کیان بازی کن و یک بار جای سارا.
قدمِ بعد: حالتهای کوچک را کامل حل کن و در یک جدول بنویس. ۱ گلدان: ۰ گل. ۲ گلدان: ۱. ۳ گلدان: سارا ۲ و ۳ را نشان میدهد؛ اگر کیان در ۳ بکارد، ۱ و ۲ هنوز خالیاند و یک گلِ دیگر هم کاشته میشود: ۲ گل. با همین دقت جلو برو.
جدول را ببین: تقریباً دو سومِ گلدانها گل میگیرند. حدس: جواب «۲n ÷ ۳، رو به پایین گرد شده» است. حدس هنوز جواب نیست؛ باید ثابتش کنی.
جوابِ یک بازی دو نیمه دارد. نیمهی سارا (بیشتر نمیشود): سارا اول گلدانهای ۲ و ۳ را نشان میدهد.
• اگر کیان در ۳ بکارد، سارا ۱ و ۲ را نشان میدهد؛ سه گلدانِ اول ۲ گل میگیرند و گلدانِ ۳ ردیف را قطع کرده: بقیه یک ردیفِ n − ۳ گلدانی است.
• اگر کیان در ۲ بکارد، گلدانِ ۱ دیگر هیچوقت انتخاب نمیشود: ۱ گل، و بقیه یک ردیفِ n − ۲ گلدانی است.
پس f(n) ≤ بیشینهی f(n − ۳) + ۲ و f(n − ۲) + ۱، و با استقرا f(n) ≤ ۲n ÷ ۳ (رو به پایین).
نیمهی کیان (کمتر نمیشود): گلدانها را ۱ تا n شماره بزن. کیان از دو گلدانِ نشانداده، اول آن را که شمارهاش مضربِ ۳ است انتخاب میکند، بعد آن را که باقیماندهاش بر ۳ یک است. با این قانون هر سهتاییِ کاملِ (۱، ۲، ۳)، (۴، ۵، ۶)، … دستکم ۲ گل میگیرد.
چالشها
- Four Pots (آسان)
- Where to Start (آسان)
- Nine Pots (متوسط)
- Guess the Rule (متوسط)
- A Hundred Pots (سخت)
- Write Sara's Half (سخت)
- Try It in Python: The Pot Game (سخت)
← جلسهی 33: به بزرگترین نگاه کن جلسهی 35: روباهِ نامرئی →