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

جلسه‌ی 15: بدترین حالت The Worst Case

«مطمئن باش» یعنی حتی اگر بدشانس‌ترین اتفاق بیفتد. حدس زدن عدد با نصف کردن، کلید و قفل، شلیک به کشتیِ پنهان، و ردیاب‌هایی که باید در هر حالتی کار کنند.

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

درس

من عددی بین ۱ تا ۳۱ در نظر گرفته‌ام. سؤال‌هایت فقط این شکلی‌اند: «عددت حداکثر x است؟» ولی من زرنگم: عددم را از قبل انتخاب نکرده‌ام و همیشه جوابی می‌دهم که عددهای بیشتری ممکن بماند. با چند سؤال پیدایش می‌کنی؟

هر سؤالِ بله/نه، عددهای ممکن را دو دسته می‌کند و حریفِ زرنگ دسته‌ی بزرگ‌تر را نگه می‌دارد. پس بهترین کار این است که هر بار دقیقاً نصف کنی: ⁦۳۱ ← ۱۶ ← ۸ ← ۴ ← ۲ ← ۱⁩، یعنی ۵ سؤال. کمتر هم نمی‌شود: با ۴ سؤال فقط ⁦۲ × ۲ × ۲ × ۲ = ۱۶⁩ جوابِ مختلف ممکن است، و ۱۶ جواب برای ۳۱ عدد کافی نیست.
دو نیمه‌ی هر جوابِ المپیادی همین‌هاست: یک روش (حداکثر k کافی است) و یک دلیل که کمتر نمی‌شود (دست‌کم k لازم است).

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

کشتیِ پنهان: یک کشتیِ ۳خانه‌ای در یک نوار ⁦۱ × ۲۰⁩ پنهان است. به چند خانه شلیک کنیم تا «مطمئن» باشیم یکی به کشتی خورده؟ به خانه‌های ۳، ۶، ۹، ۱۲، ۱۵ و ۱۸ شلیک کن: هر ۳ خانه‌ی پشت سر هم یکی از این‌ها را دارد. ۶ شلیک. کمتر نمی‌شود: با ۵ شلیک، ۱۵ خانه‌ی شلیک‌نشده در حداکثر ۶ تکه‌اند و یکی از تکه‌ها دست‌کم ۳ خانه دارد؛ کشتی همان‌جاست!

چالش‌ها

  1. From 1 to 100 (آسان)
  2. Which Key? (آسان)
  3. Eight Keys, Eight Lockers (متوسط)
  4. The Hidden Ship (متوسط)
  5. The Lost Ring (سخت)
  6. Mark Every Strip (سخت)

← جلسه‌ی 14: راستگوها و دروغگوها جلسه‌ی 16: استراتژی برد: از آخر به اول →