پازل: معادله اعداد طبیعی | جایزه هفته: یک دستگاه هارد اکسترنال AC731 اپیسر

به «پازل» ۲۴ خرداد ۱۳۹۸ خوش آمدید! سری «پازل» به‌صورت هفتگی منتشر می‌شود. دویست‌وشصت‌وششمین قسمت از سری «پازل» شامل دو بخش است: پاسخ معمای ۲۶۵ و البته یک «پازل» جدید! با زومیت همراه باشید.

پاسخ: ۷۲ و ۲۳۲

بهترین حالت زمانی اتفاق می‌افتد که ما خوش شانس باشیم و همان ابتدا پاکت A را برای بررسی انتخاب کنیم. اما برای بدست آوردن تعداد میوه‌ای که باید از پاکت A خارج کنیم تا مطمئن شویم پاکتی که در حال بررسی آن هستیم، پاکت A است، ابتدا باید بررسی کنیم که چه ترتیبی از خروج میوه‌ها، به کمترین تعداد میوه جهت بررسی، منجر خواهد شد.

ترتیبی از خروج میوه‌ها، به بررسی کمترین تعداد منجر خواهد شد که ما را زودتر متوجه وجه تمایز پاکت A کند. وجه تمایز بین پاکت A و پاکت B در تعداد دو میوه‌ی شلیل و زردآلو است و وجه تمایز شلیل از وجه تمایز زردآلود بهتر است، چرا که با خارج کردن ۳۱ عدد شلیل میتوانیم مطمئن باشیم پاکت فعلی پاکت B نیست، پس یا پاکت A است یا پاکت C. حال اگر به اندازه‌ی کافی خوش شانس باشیم و در ادامه هم ترتیب خروج میوه‌ها (که تصادفی است) مطابق میل ما باشد، باید حداقل ۴۱ هلو از پاکت خارج شود تا اطمینان پیدا کنیم پاکت در دست بررسی پاکت C نیست و پاکت A را یافته‌ایم. بنابراین در بهترین حالت و با بیشترین خوش شانسی حداقل نیاز داریم تا ۳۱+۴۱ یعنی ۷۲ عدد میوه از پاکت خارج کنیم.

اما بدترین حالت مسئله می‌تواند از دو جنبه رخ دهد: جنبه اول این است که در ابتدا پاکتی را (به‌طور تصادفی) انتخاب کنیم که A نباشد که در این حالت یکی از دو پاکت B یا C است. جنبه دوم، این است که ترتیب خروج میوه‌ها به‌گونه‌ای اتفاق بیوفتد که وجه اشتراک بین پاکت‌ها تا آخرین لحظه ممکن، مانع از فهم ما در مورد گونه‌ی پاکت‌ها شود.

ترتیب‌های ممکن برای خروج میوه‌ها به بدترین شکل، انواع بسیار زیادی دارد که در اینجا تنها یک نمونه از آن را برای درک مسئله بررسی می‌کنیم. فرض می‌کنیم پاکت انتخابی اول (به شکل تصادفی) پاکت C باشد؛ حال در صورتی که ۴۰ هلو، ۳۰ شلیل و ۴۰ زردآلو از پاکت خارج کنیم، هنوز مشخص نیست که کدام پاکت را بررسی می‌کنیم و حتی هنوز مشخص نیست که کدام پاکت را بررسی نمی‌کنیم! ۱۱۱اُمین میوه‌ای که خارج می‌کنیم قطعا هلو نیست و یکی از دو میوه شلیل یا زردآلو است؛ در صورتی که زردآلو باشد می‌فهمیم که پاکت A نیست و در صورتی که شلیل باشد می‌فهمیم که پاکت B نیست و باز هم از آنجا که هدف ما پیدا کردن بدترین حالت ممکن است، فرض می‌کنیم که ۱۱۱اُمین میوه تا ۱۱۵اُمین میوه شلیل باشد. توجه کنید که بعد از خروج ۱۱۱اُمین میوه ما می‌دانیم که پاکت فعلی قطعا B نیست، اما هنوز امیدواریم که پاکت A باشد به همین دلیل به خارج کردن میوه از آن ادامه می‌دهیم. حال به نقطه‌ای رسیدیم که از پاکت، یا زردآلو خارج می‌شود یا هلو که باتوجه‌به اینکه پاکت C را برداشته بودیم (به‌طور تصادفی) زرد آلو خارج می‌شود، یعنی برای آنکه متوجه شویم پاکت فعلی A نیست، تنها ۴ میوه در پاکت باقی ماند و ۱۱۶ میوه از آن خارج شد! حال که متوجه شدیم پاکت مورد نظر را پیدا نکرده‌ایم سراغ پاکت بعدی می‌رویم. توجه کنید که در اینجا (برای پاسخ مسئله) تفاوتی نمی‌کند کدام یک از پاکت ها را برداریم، چرا که پاکتی که B نیست A است و بالعکس (اما در هنگام بررسی پاکت اول، پاکتی که B نبود لزوما A نبود) و تنها بدترین حالت مسئله از جنبه دوم (که بالاتر ذکر شد) اهمیت دارد. در اینجا هم ترتیب خروج ۴۵ هلو ، ۳۰ شلیل و ۴۰ زردآلو شامل حداکثر وجه مشترک بین پاکت های A و B است، اما با خروج ۱۱۶اُمین میوه از دومین پاکت مشخص خواهد که پاکت دوم پاکت A بود یا پاکتی که هنوز باز نشده است. در صورتی که ۱۱۶اُمین میوه ی خروجی از پاکت دوم زردآلو باشد، پاکت مورد نظر، پاکتی است که حتی یک میوه از آن خارج نشده است! بنابراین در بدترین حالت نیاز داریم ۱۱۶ + ۱۱۶ یعنی ۲۳۲ میوه از پاکت‌ها خارج کنیم تا به‌طور قطعی پاکت A را یافته باشیم.

در طرح سؤال پاکت میوه از یک سؤال کنکور الهام گرفته شد.

۸۴۵ نفر از کاربران در «پازل ۲۶۵ زومیت» شرکت کردند که ۲۲۳ نفر موفق به ارائه‌ی پاسخ صحیح شدند. اما ۳ برندگان خوش‌شانس این قسمت از پازل:

فرض کنید ۵۰ عدد مختلف طبیعی (اعداد طبیعی منظور ۱، ۲، ۳ و ... است ) بین اعداد ۱ تا ۲۰۰ داریم در صورتی که X و Y و Z سه تا از این ۵۰ عدد باشند؛ حداقل چند "بررسی" (بررسی اعداد در رابطه‌ی زیر) در بدترین حالت نیاز است تا به‌طور قطعی بتوانیم بگوییم به ازای هر X و Y و Z رابطه ی زیر صدق می‌کند یا به‌طور قطعی بتوانیم بگوییم X و Y و Z وجود دارد که در رابطه ی زیر صدق نمی‌کند؟

X+Y > Z

منبع طرح معما‌های سری «پازل» اینترنت نیست؛ اما در دنیای اینترنت، ممکن است پاسخ هر چیزی یافت شود. پس اگر جوابی در اینترنت یافتید، به دوستان خود احترام بگذارید و آن را منتشر نکنید. علاوه‌بر این، از آنجا که بخش نظرات مقاله‌های «پازل»، محل تبادل نظر و راهنمایی محسوب می‌شود، جهت احترام به حقوق خود و سایر کاربران، از ارسال نظرات غیرمرتبط خودداری کنید.

تا ساعت ۱۲ ظهر روز پنجشنبه فرصت دارید به این معما پاسخ دهید. برای بهتر شدن «پـازل» نظرات و پیشنهادهای خود را درباره این بخش، حتماً با ما در میان بگذارید.