المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۲۶

۳۲ لامپ موجود است و هرکدام به یک کلید متصل است. در ابتدا بعضی از لامپ ها روشن و بعضی خاموش‌اند. ناگهان یک سیم متصل به یکی از لامپ‌ها اتصال کوتاه می‌کند خراب‌ شده و باعث سوختن فیوز و درنتیجه قطع کل برق می‌شود. فیوز سوخته قابل‌استفاده‌ی مجدد نیست و باید تعویض شود. اگر کلیدِ لامپی که اتصالی دارد در وضعیت روشن قرار داشته باشد و فیوز سالمی را جایگزین کنیم فیوز جدید نیز خواهد سوخت. برای پیدا کردن کلید متصل به اتصال کوتاه چند عدد فیوز سالمِ جدید لازم است؟

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

پاسخ

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

ابتدا یک عدد فیوز می‌بندیم که اگر نسوزد معلوم می‌شود کلید مورد نظر متصل به یکی از لامپ‌های خاموش می‌باشد. با عوض کردن وضعیت کلید لامپ‌های خاموش به صورت متوالی٬ به محض سوختن فیوز می‌فهمیم که کلید مورد نظر آخرین کلیدی است که وضعیت آن را تغییر داده‌ایم. و اما اگر فیوز بسته شده بسوزد می‌فهمیم که کلید مطلوب به یکی از لامپ‌های روشن متصل است٬ در این حالت کل لامپ‌ها را به دو دسته ۱۶ تایی تقسیم می‌کنیم و وضعیت کلید تمام ۱۶ لامپ دسته اول را تغییر داده و فیوز دوم را می‌بندیم که باز اگر فیوز بسوزد متوجه می‌شویم که کلید مطلوب در دسته ۱۶ تایی دوم قرار دارد و اگر فیوز دوم نسوزد می‌فهمیم که آن کلید در دسته ۱۶ تایی اول قرار دارد.

اگر به همین ترتیب دسته شناسایی شده را به دو دسته ۸تایی و سپس ۴تایی٬… تقسیم کنیم به جواب مورد نظر خواهیم رسید.


ابزار صفحه