جلسهی 15: بدترین حالت The Worst Case
«مطمئن باش» یعنی حتی اگر بدشانسترین اتفاق بیفتد. حدس زدن عدد با نصف کردن، کلید و قفل، شلیک به کشتیِ پنهان، و ردیابهایی که باید در هر حالتی کار کنند.
در این جلسه یاد میگیری
- میفهمی «کمترین تعدادی که مطمئن باشیم» یعنی بدترین حالت را باید شکست داد.
- با نصف کردن (یا تقسیم به چند قسمت) تعداد سؤالها را کم میکنی.
- برای جوابت هم یک روش میدهی و هم نشان میدهی کمتر نمیشود.
درس
من عددی بین ۱ تا ۳۱ در نظر گرفتهام. سؤالهایت فقط این شکلیاند: «عددت حداکثر x است؟» ولی من زرنگم: عددم را از قبل انتخاب نکردهام و همیشه جوابی میدهم که عددهای بیشتری ممکن بماند. با چند سؤال پیدایش میکنی؟
هر سؤالِ بله/نه، عددهای ممکن را دو دسته میکند و حریفِ زرنگ دستهی بزرگتر را نگه میدارد. پس بهترین کار این است که هر بار دقیقاً نصف کنی: ۳۱ ← ۱۶ ← ۸ ← ۴ ← ۲ ← ۱، یعنی ۵ سؤال. کمتر هم نمیشود: با ۴ سؤال فقط ۲ × ۲ × ۲ × ۲ = ۱۶ جوابِ مختلف ممکن است، و ۱۶ جواب برای ۳۱ عدد کافی نیست.
دو نیمهی هر جوابِ المپیادی همینهاست: یک روش (حداکثر k کافی است) و یک دلیل که کمتر نمیشود (دستکم k لازم است).
کلید و قفل: ۸ کلید و یک قفل داری و فقط یکی از کلیدها قفل را باز میکند. در بدترین حالت چند بار امتحان لازم است تا «مطمئن» شوی کدام کلید است؟ ۷ بار! اگر ۷ کلید اول هیچکدام باز نکرد، هشتمی حتماً همان است و لازم نیست امتحانش کنی.
اشتباه رایج: جواب دادنِ ۸. وقتی فقط یک گزینه مانده، دیگر لازم نیست امتحانش کنی.
کشتیِ پنهان: یک کشتیِ ۳خانهای در یک نوار ۱ × ۲۰ پنهان است. به چند خانه شلیک کنیم تا «مطمئن» باشیم یکی به کشتی خورده؟ به خانههای ۳، ۶، ۹، ۱۲، ۱۵ و ۱۸ شلیک کن: هر ۳ خانهی پشت سر هم یکی از اینها را دارد. ۶ شلیک. کمتر نمیشود: با ۵ شلیک، ۱۵ خانهی شلیکنشده در حداکثر ۶ تکهاند و یکی از تکهها دستکم ۳ خانه دارد؛ کشتی همانجاست!
چالشها
- From 1 to 100 (آسان)
- Which Key? (آسان)
- Eight Keys, Eight Lockers (متوسط)
- The Hidden Ship (متوسط)
- The Lost Ring (سخت)
- Mark Every Strip (سخت)
← جلسهی 14: راستگوها و دروغگوها جلسهی 16: استراتژی برد: از آخر به اول →