بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 34: یک مسئله‌ی بلند: بازیِ گلدان‌ها A Long Problem: The Pot Game

سؤال‌های تشریحیِ مرحله‌ی دوم بلندند و چند قدم دارند. با یک بازیِ دونفره روی یک ردیف گلدان یاد می‌گیری از کجا شروع کنی: حالت‌های کوچک، جدول، حدس، و اثباتِ هر دو طرف.

در این جلسه یاد می‌گیری

درس

سارا و کیان یک ردیف گلدانِ خالی دارند. هر بار سارا دو گلدانِ خالیِ کنارِ هم را نشان می‌دهد و کیان در یکی از آن دو گل می‌کارد. بازی وقتی تمام می‌شود که دیگر دو گلدانِ خالیِ کنارِ هم نمانده باشد. کیان می‌خواهد آخرِ بازی گل‌ها زیاد باشند و سارا می‌خواهد کم باشند. اگر هر دو بهترین بازی را بکنند، چند گل کاشته می‌شود؟
مسئله‌ی بلند را با بازی کردن شروع کن. یک بار جای کیان بازی کن و یک بار جای سارا.

قدمِ بعد: حالت‌های کوچک را کامل حل کن و در یک جدول بنویس. ۱ گلدان: ۰ گل. ۲ گلدان: ۱. ۳ گلدان: سارا ۲ و ۳ را نشان می‌دهد؛ اگر کیان در ۳ بکارد، ۱ و ۲ هنوز خالی‌اند و یک گلِ دیگر هم کاشته می‌شود: ۲ گل. با همین دقت جلو برو.
جدول را ببین: تقریباً دو سومِ گلدان‌ها گل می‌گیرند. حدس: جواب «⁦۲n ÷ ۳⁩، رو به پایین گرد شده» است. حدس هنوز جواب نیست؛ باید ثابتش کنی.

جوابِ یک بازی دو نیمه دارد. نیمه‌ی سارا (بیشتر نمی‌شود): سارا اول گلدان‌های ۲ و ۳ را نشان می‌دهد.
• اگر کیان در ۳ بکارد، سارا ۱ و ۲ را نشان می‌دهد؛ سه گلدانِ اول ۲ گل می‌گیرند و گلدانِ ۳ ردیف را قطع کرده: بقیه یک ردیفِ ⁦n − ۳⁩ گلدانی است.
• اگر کیان در ۲ بکارد، گلدانِ ۱ دیگر هیچ‌وقت انتخاب نمی‌شود: ۱ گل، و بقیه یک ردیفِ ⁦n − ۲⁩ گلدانی است.
پس ⁦f(n)⁩ ≤ بیشینه‌ی ⁦f(n − ۳) + ۲⁩ و ⁦f(n − ۲) + ۱⁩، و با استقرا ⁦f(n) ≤ ۲n ÷ ۳⁩ (رو به پایین).
نیمه‌ی کیان (کمتر نمی‌شود): گلدان‌ها را ۱ تا n شماره بزن. کیان از دو گلدانِ نشان‌داده، اول آن را که شماره‌اش مضربِ ۳ است انتخاب می‌کند، بعد آن را که باقی‌مانده‌اش بر ۳ یک است. با این قانون هر سه‌تاییِ کاملِ (۱، ۲، ۳)، (۴، ۵، ۶)، … دست‌کم ۲ گل می‌گیرد.

چالش‌ها

  1. Four Pots (آسان)
  2. Where to Start (آسان)
  3. Nine Pots (متوسط)
  4. Guess the Rule (متوسط)
  5. A Hundred Pots (سخت)
  6. Write Sara's Half (سخت)
  7. Try It in Python: The Pot Game (سخت)

← جلسه‌ی 33: به بزرگ‌ترین نگاه کن جلسه‌ی 35: روباهِ نامرئی →