مسابقه‌ی تصادفی

 
 
 لامپ سالم
لامپ سالممسابقه كامپيوتر
مسابقه شماره ۲۵۰

 سوال

 

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

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

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  2437
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  2437