====== سؤال ۱۹ ====== یک لامپ سالم در زیرزمین فقط به یکی از ۱۰ کلید مشابه در هالِ طبقه‌ی بالا وصل است. ۹ کلید دیگر به هیچ لامپی وصل نیستند. کلید متصل به لامپ، اگر در وضعیت رو به بالا قرار گیرد لامپ را روشن و اگر رو به پایین باشد آن را خاموش می‌کند. می‌خواهیم با حداقل تعداد پایین رفتن به زیرزمین، مشخص کنیم کدام‌یک از کلیدها به لامپ زیرزمین وصل است. می‌دانیم که لامپ با ۵ بار خاموش و روشن کردن متوالی حتماً می‌سوزد، و لامپ سوخته از سالم قابل‌تشخیص است. توجه کنید که فقط همان یک لامپ را در اختیار داریم و سوختن آن‌ هم برای ما مهم نیست. با حداقل چند بار پایین رفتن می‌توان جواب مسئله را پیدا کرد؟ (توجه کنید که بالا رفتن‌ها را نمی‌شماریم.) - ۱ - ۲ - ۳ - ۴ - ۵ <راهنمایی> فرض کنید به جای ۱۰ کلید، ۳ کلید داریم. آیا می توان با یک پایین رفتن و بالا آمدن، کلید درست را تشخیص داد؟ <پاسخ> گزینه‌ی (۳) درست است ابتدا راهی ارائه می‌دهیم که با سه بار بررسی کردن متوجه کلید مورد نظر شویم. ابتدا پنج کلید را در وضعیت روشن و پنج کلید را در وضعین خاموش قرار دهید. حال وضعیت لامپ را بررسی کنید. اگر روشن بود، متوجه می‌شویم کلید مورد نظر یکی از پنج کلید در وضعیت روشن است. در غیر این صورت، کلید مورد نظر یکی از پنج کلید در وضعیت خاموش است. حال میان پنج کلید می‌بایست بررسی صورت گیرد. سه کلید را در وضعیت روشن و دو کلید را در وضعیت خاموش قرار دهید. حال وضعیت لامپ را بررسی می‌کنیم. مشابه حالت قبل، پس از بررسی میان دو یا سه کلید شک داریم. در صورتی که بین دو کلید شک داشته باشیم، کافی است کلیدی را در وضعیت روشن و کلید دیگری را در وضعیت خاموش قرار دهیم و وضعیت لامپ را بررسی کنیم. و در صورتی که بین سه کلید شک داشتیم، یک کلید را در وضعیت روشن، یک کلید را در وضعیت خاموش قرار داده، و کلید سوم را پنج بار روشن و خاموش می‌کنیم. در این صورت، اگر لامپ روشن باشد، خاموش باشد و یا سوخته باشد به طور یکتا تعیین می‌شود برای کدام کلید بوده است. حال استدلال می‌کنیم حداقل نیاز به سه بررسی وجود دارد. در پرسش اول، اگر بیش از یک کلید باعث سوختن لامپ شوند نمی‌توان فهمید کدام کلید برای لامپ است. پس حداکثر یک کلید را می‌توان برای سوختن انتخاب کرد و ۹ کلید دیگر به دو دسته تقسیم می‌شوند که برخی روشن هستند و برخی خاموش. پس در گام دوم ممکن است میان پنج کلید شک داشته باشیم. به طور مشابه ممکن نیست بیش از یک کلید را با سوختن تعیین وضعیت کرد پس چهار کلید و دو وضعیت روشن و خاموش باقی می‌ماند که در نتیجه، امکان تعیین کلید مناسب با دو بار بررسی لامپ وجود ندارد. * [[سوال ۲۰|سوال بعد]] * [[سوال ۱۸|سوال قبل]]