سروش و بهرام روی یک جدول 4×4 بازی میکنند. در ابتدا، بهرام 4 خانهی متمایز را از جدول انتخاب میکند و هر یک از اعدادِ 1 تا 4 را در یکی از آن خانهها پنهان میکند. سروش که از انتخابِ بهرام خبر ندارد، میخواهد با تعدادی پرسش، مکان هر 4 خانهی انتخابیِ بهرام را بههمراه عددشان پیدا کند. سروش در هر پرسش میتواند یک زیرجدول را مشخص کند تا بهرام در پاسخ بگوید چه اعدادی در این زیرجدول وجود دارند. یک زیرجدول، جدولی ناتهی است که از اشتراکِ تعدادی سطرِ متوالی و تعدادی ستونِ متوالی از جدولِ اصلی حاصل میشود. سروش حداقل به چند پرسش نیاز دارد تا تحت هر شرایطی بتواند به هدفش برسد؟
پاسخ
گزینه (۲) درست است.
اثبات نیاز به حداقل ۴ پرسش:
ابتدا نشان میدهیم که به حداقل 4 پرسش نیاز داریم. فرض کنید هدف، پیدا کردن بمب شماره 1 است. از آنجایی که جدول شامل 16 خانه است و با هر پرسش کاندیداها به دو دسته تقسیم میشوند، برای شناسایی بمب حداقل به تعداد زیر پرسش نیاز داریم: log2(16)=4
اثبات شناسایی مکان بمبها با ۴ پرسش:
حال نشان میدهیم با 4 پرسش میتوانیم مکان هر تعداد از بمبها را پیدا کنیم. اگر یکبار دو سطر اول را بپرسیم و یکبار دو سطر وسط را، میتوان شماره سطر همه بمبها را تشخیص داد، زیرا وضعیت هر 4 سطر در این دو پرسش به طور یکتا مشخص میشود. به طور مشخص:
با تکرار همین روش برای ستونها، میتوان شماره ستون همه بمبها را نیز تشخیص داد. بنابراین با 4 پرسش به هدف میرسیم.