Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۴:سوال ۱۳

سوال ۱۳

سروش و بهرام روی یک جدول 4×4 بازی می‌کنند. در ابتدا، بهرام 4 خانه‌ی متمایز را از جدول انتخاب می‌کند و هر یک از اعدادِ 1 تا 4 را در یکی از آن خانه‌ها پنهان می‌کند. سروش که از انتخابِ بهرام خبر ندارد، می‌خواهد با تعدادی پرسش، مکان هر 4 خانه‌ی انتخابیِ بهرام را به‌همراه عددشان پیدا کند. سروش در هر پرسش می‌تواند یک زیرجدول را مشخص کند تا بهرام در پاسخ بگوید چه اعدادی در این زیرجدول وجود دارند. یک زیرجدول، جدولی ناتهی است که از اشتراکِ تعدادی سطرِ متوالی و تعدادی ستونِ متوالی از جدولِ اصلی حاصل می‌شود. سروش حداقل به چند پرسش نیاز دارد تا تحت هر شرایطی بتواند به هدفش برسد؟

  1. 3
  2. 4
  3. 5
  4. 6
  5. 7

پاسخ

گزینه (۲) درست است.

اثبات نیاز به حداقل ۴ پرسش:

ابتدا نشان می‌دهیم که به حداقل 4 پرسش نیاز داریم. فرض کنید هدف، پیدا کردن بمب شماره 1 است. از آنجایی که جدول شامل 16 خانه است و با هر پرسش کاندیداها به دو دسته تقسیم می‌شوند، برای شناسایی بمب حداقل به تعداد زیر پرسش نیاز داریم: log2(16)=4

اثبات شناسایی مکان بمب‌ها با ۴ پرسش:

حال نشان ‌می‌دهیم با 4 پرسش می‌توانیم مکان هر تعداد از بمب‌ها را پیدا کنیم. اگر یک‌بار دو سطر اول را بپرسیم و یک‌بار دو سطر وسط را، می‌توان شماره سطر همه بمب‌ها را تشخیص داد، زیرا وضعیت هر 4 سطر در این دو پرسش به طور یکتا مشخص می‌شود. به طور مشخص:

  1. برای سطر اول، فقط جواب پرسش اول تأیید می‌شود.
  2. برای سطر دوم، هر دو پرسش تأیید می‌شود.
  3. برای سطر سوم، فقط پرسش دوم تأیید می‌شود.
  4. و برای سطر چهارم، هیچکدام از پرسش‌ها تأیید نمی‌شود.

با تکرار همین روش برای ستون‌ها، می‌توان شماره ستون همه بمب‌ها را نیز تشخیص داد. بنابراین با 4 پرسش به هدف می‌رسیم.


ابزار صفحه