المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۵:سوال ۱۹

سؤال ۱۹

یک لامپ سالم در زیرزمین فقط به یکی از ۱۰ کلید مشابه در هالِ طبقه‌ی بالا وصل است. ۹ کلید دیگر به هیچ لامپی وصل نیستند. کلید متصل به لامپ، اگر در وضعیت رو به بالا قرار گیرد لامپ را روشن و اگر رو به پایین باشد آن را خاموش می‌کند. می‌خواهیم با حداقل تعداد پایین رفتن به زیرزمین، مشخص کنیم کدام‌یک از کلیدها به لامپ زیرزمین وصل است. می‌دانیم که لامپ با ۵ بار خاموش و روشن کردن متوالی حتماً می‌سوزد، و لامپ سوخته از سالم قابل‌تشخیص است. توجه کنید که فقط همان یک لامپ را در اختیار داریم و سوختن آن‌ هم برای ما مهم نیست. با حداقل چند بار پایین رفتن می‌توان جواب مسئله را پیدا کرد؟ (توجه کنید که بالا رفتن‌ها را نمی‌شماریم.)

  1. ۱
  2. ۲
  3. ۳
  4. ۴
  5. ۵

پاسخ

گزینه (؟) درست است.

در ابتدا کلید‌ها را به دو دسته پنج‌تایی تقسیم می‌کنیم و پنج‌تای اول را رو به بالا(در حالت $U$) و پنج‌تای دوم را رو به پایین (در حالت $D$) قرار می‌دهیم٬ سپس به زیر زمین رفته و لامپ را نگاه می‌کنیم اگر روشن باشد می‌فهمیم که کلید در دسته اول قرار دارد٬ در غیر این صورت کلید در دسته دوم قرار خواهد داشت. بعد از شناسایی دسته مورد نظر٬ ۳تا از کلیدها را در وضعیت $U$ و ۲تای دیگر را در وضعیت $D$ قرار می‌دهیم و برای بار دوم به زیرزمین می‌رویم که اگر لامپ روشن باشد٬ کلید مورد نظر در دسته ۳تایی و در غیر این صورت در دسته ۲تایی خواهد بود. پس از شناسایی دسته مورد نظر( در بدترین حالت سه‌تایی)٬‌ دو تا از آن‌ها را در وضعیت $U$ و یکی دیگر را در وضعیت $D$ قرار داده و برای بار سوم به زیرزمین می‌رویم که اگر لامپ روشن بود کلید مطلوب در دسته ۲تایی بوده و در غیر این صورت آن کلید٬ کلید سوم است. بدترین حالت این است که لامپ روشن بوده و دو کلید مجهول باقی مانده باشد که در این صورت یکی از آن دو کلید را در وضعیت $U$ و دیگری را در وضعیت $D$ قرار داده و برای بار چهارم(آخرین‌بار) به زیرزمین رفته و با توجه به روشن و یا خاموش بودن لامپ٬ کلید مورد نظر را شناسایی می‌کنیم.


ابزار صفحه