المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۲۸:سوال ۲۲

تفاوت‌ها

تفاوت دو نسخه‌ی متفاوت از صفحه را مشاهده می‌کنید.

پیوند به صفحه‌ی تفاوت‌ها

سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۸:سوال_۲۲ [2018/12/18 08:25] (فعلی)
Hamidreza seydi ایجاد شد
خط 1: خط 1:
 +====== سوال ۲۲ ======
 +
 +
 +
 +گراف زیر را در نظر بگیرید:​
 +
 +
 +
 +
 +
 +{{ :​سوالات_المپیاد:​مرحله‌ی_اول:​دوره‌ی_۲۸:​untitled10.png |}}
 +
 +
 +
 +یک گنج در یکی از رأس‌های گراف مخفی شده است. ​
 +**روزبه**
 + یک دستگاه گنج‌یاب دارد. او در هر مرحله می‌تواند یک دور به طول پنج از گراف را به دستگاه بدهد و بفهمد گنج در رأس‌های این دور هست یا خیر. روزبه دست‌کم به چند مرحله استفاده از دست‌گاه نیاز دارد تا مطمئن باشد می‌تواند جای گنج را بفهمد؟
 +
 +
 +
 +
 +  - ۱
 +  - ۳
 +  - ۴
 +  - ۶
 +  - ۹
 +
 +
 +
 +<​پاسخ>​
 + ​گزینه‌ی ۳ درست است.
 +
 +
 +ابتدا روشی با چهار مرحله ارائه می‌دهیم. روزبه در ابتدا یک دور به طول پنج انتخاب می‌کند. چه پاسخ خیر باشد و چه بله، رأس‌های کاندید برای گنج در یک دور به طول پنج هستند. حال روزبه یک دور به طول پنج انتخاب می‌کند که شامل دو رأس مجاور از پنج رأس کاندید باشد.
 +
 +
 +  * اگر جواب خیر باشد، سه رأس کاندید برای گنج می‌ماند. حال یک دور به طول پنج انتخاب می‌کنیم که شامل دو رأس مجاور از این سه رأس باشد. اگر جواب خیر باشد با یک پرسش دیگر (دوری که شامل یکی از دو رأس کاندید باشد) مسئله حل می‌شود و اگر هم جواب بله باشد که گنج پیدا شده‌ است.
 +  * اگر جواب بله باشد با یک پرسش دیگر (دوری که شامل یکی از دو رأس کاندید باشد) مسئله حل می‌شود. ​
 +
 +حال ثابت می‌کنیم روشی با بهتر از چهار مرحله وجود ندارد. در ابتدا ۱۰ رأس کاندید برای گنج داریم. در هر مرحله رأس‌های کاندید به دو دسته‌ی $X$ (درون دور انتخاب شده) ‌و $Y$ (خارج دور انتخاب شده) تقسیم می‌شوند. ممکن است در هر مرحله پاسخ طوری باشد که تعداد خانه‌های کاندید بیش‌تری باقی بماند. پس دست کم
 +$\lceil log_2 10 \rceil = 4$
 +مرحله نیاز است.
 +
 +
 +</​پاسخ>​
 +
 +  * [[سوال ۲۱|سوال قبل]]
 +  * [[سوالات ۲۳ و ۲۴|سوال بعد]]
  

ابزار صفحه