۷ لامپ در یک ردیف به صورت سری به هم وصل شده‌اند. می‌دانیم دقیقاً دو تا از لامپ‌ها خراب هستند و به همین خاطر هیچ‌کدام روشن نمی‌شوند. برای پیدا کردن لامپ‌های خراب، در هر آزمون می‌توانیم دو سر سیم برق را به دو سر یک زیربازه از لامپ‌ها (شامل یک یا چند لامپ) وصل کنیم. اگر همه‌ی لامپ‌های درون این بازه سالم باشند همه روشن می‌شوند و اگر حداقل یکی از این لامپ‌ها خراب باشد، هیچ‌کدام روشن نمی‌شوند. با حداقل چند آزمون می‌توان هر دو لامپ خراب را پیدا کرد؟
3
4
5
6
7
راهنمایی
با آزمودن لامپ ۱،۲ باهم و بعد ۳،۴ باهم شروع کنید و روی جواب این دو آزمایش حالت بندی کنید.
پاسخ
گزینه‌ی ۳ درست است.
برای این کار ۵ آزمون لازم است. با ۴ آزمون این کار ممکن نیست زیرا تعداد حالات ممکن $\binom 7 2 = 21$ است و با ۴ آزمون فقط می‌توان $2^4=16$ حالت را از هم تمیز داد. در آزمون اول لامپ ۱ و ۲ و در آزمون دوم لامپ ۳ و ۴ را امتحان می‌کنیم. حال اگر
در هر دو آزمون لامپ‌ها روشن شدند، دو لامپ خراب در بین ۵، ۶ و ۷ هستند که با آزمون لامپ ۵ و لامپ ۶ (هر کدام به تنهایی) لامپ‌های خراب پیدا می‌شود. در این حالت در مجموع ۴ آزمون انجام می‌شود.
در هر دو آزمون لامپ‌ها روشن نشدند، یک لامپ خراب در بین ۱ و ۲ و یک لامپ خراب در بین ۳ و ۴ هست. برای تعیین هر کدام از لامپ‌های یک آزمون نیاز است. در این حالت نیز در مجموع ۴ انجام می‌شود.
در یک آزمون لامپ‌ها روشن شدند و در دیگری روشن نشدند. بدون کم شدن از کلیت مسئله فرض می‌کنیم لامپ ۳ و ۴ روشن شدند و لامپ ۱ و ۲ روشن نشدند. در این حالت در آزمون سوم لامپ‌های ۵ و ۶ را امتحان می‌کنیم. حال اگر
لامپ ۵ و ۶ روشن نشدند، یک لامپ خراب بین ۱ و ۲ و دیگری بین ۵ و۶ است که هر کدام با یک آزمون پیدا می‌شوند. در این حالت با ۵ آزمون لامپ‌های خراب پیدا می‌شوند.
لامپ ۵ و ۶ روشن شدند، جواب بین ۱، ۲ و ۷ است. با دو آزمون (هر آزمون یک لامپ) وضعیت هر سه لامپ مشخص می‌شود. در این حالت نیز با ۵ آزمون لامپ‌های خراب پیدا می‌شوند.