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

جلسه‌ی 35: روباهِ نامرئی The Invisible Fox

یک روباهِ نامرئی در یک ردیف خانه است و تو با فلاشِ دوربین دنبالش هستی. ترفندِ «در هر خانه یک روباه»، یک نقشه‌ی کم‌قدم، و اثباتِ این‌که کمتر نمی‌شود با شمردنِ خانه‌های امن.

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

درس

یک روباهِ نامرئی در یکی از خانه‌های یک ردیف است. تو هر بار با دوربین از یک خانه عکس می‌گیری. اگر روباه آن‌جا باشد، عکسش را گرفته‌ای! اگر نه، روباه از فلاش می‌ترسد و یک خانه از فلاش دورتر می‌رود؛ روباهی که در خانه‌ی اول یا آخر است سرِ جایش می‌ماند. کمِ کم چند عکس لازم است تا حتماً از روباه عکس بگیری؟
ترفند: «حتماً» یعنی باید همه‌ی جاهای ممکن را با هم دنبال کنی. فرض کن در هر خانه یک روباه هست؛ وقتی همه‌ی روباه‌ها گرفته شدند، کار تمام است.

یک نقشه برای ۶ خانه با ۳ عکس: خانه‌ی ۳، بعد ۱، بعد ۶.
• اول همه‌ی خانه‌ها ممکن‌اند: {۱، ۲، ۳، ۴، ۵، ۶}.
• عکس از ۳: روباهِ ۲ به ۱ می‌رود و ۱ می‌ماند؛ ۴ و ۵ و ۶ به ۵، ۶، ۶ می‌روند: {۱، ۵، ۶}.
• عکس از ۱: روباهِ ۵ به ۶ می‌رود: {۶}.
• عکس از ۶: تمام!
برای ۹ خانه: ۴، ۶، ۱، ۹. نقشه را همیشه با نوشتنِ «جاهای ممکن» بعد از هر قدم ثابت کن.

چرا کمتر نمی‌شود؟ خانه‌ای را «امن» بگو که هیچ روباهی در آن نیست. در هر عکس:
• خودِ خانه‌ی عکس امن می‌شود: حداکثر ۱.
• روباه‌های سمتِ چپ هر کدام یک خانه به چپ می‌روند؛ دو روباه فقط در خانه‌ی ۱ به هم می‌رسند، پس سمتِ چپ حداکثر ۱ خانه‌ی امنِ تازه می‌دهد. سمتِ راست هم همین‌طور.
پس هر عکس حداکثر ۳ خانه‌ی امن اضافه می‌کند. روباه‌های دو سر هیچ‌وقت تکان نمی‌خورند، پس باید از هر دو سر عکس بگیری، و چنین عکسی فقط یک طرف دارد: حداکثر ۲. عکسِ آخر هم حداکثر ۱ (قبلش باید فقط یک خانه‌ی ناامن مانده باشد).
با p عکس: ⁦۱ + ۲ + ۳(p − ۲) ≥ n⁩، یعنی ⁦p ≥ n ÷ ۳ + ۱⁩.

چالش‌ها

  1. Three Cells (آسان)
  2. Why Every Cell? (آسان)
  3. Nine Cells (متوسط)
  4. At Most Three (متوسط)
  5. A Hundred Cells (سخت)
  6. Write the Fox Proof (سخت)
  7. Try It in Python: Follow the Foxes (سخت)

← جلسه‌ی 34: یک مسئله‌ی بلند: بازیِ گلدان‌ها جلسه‌ی 36: شهرهای به‌هم‌پیوسته →