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