المپدیا

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

ابزار کاربر

ابزار سایت


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

در جست و جوی مصطفی (۲۰ نمره)

مصطفی بعد از این که متوجه شد معین. دوست صمیمی او با امیر توطئه کرده است تا او را شکست بدهد، از ناراحتی سر به بیابان می‌گذارد. $n$ نفر از دوستان مصطفی از این موضوع مطلع می‌شوند و به دنبال او به بیابان می‌روند تا او را پیدا کنند و بر گردانند.

کنند. مصطفی روی بکی از این نقاط پنهان شده و به‌علت ناراحتی بسیا از جایش تکعان نمی‌خورد. تنها کسی او را می‌بیند که دقیقا روی همان نقطه باشد.

این $n$ نفر در نقاطی دلخواه از بیابان مستقر شده و هر کدام جهتی را انتخاب می کنند (بالاء پایین» چپ يا راست). پس از شروع. هر کدام در جهتی که انتخاب کرده حر کت می کند و هر تانیه یک قدم بر می‌دارد (یک واحد حر کت می‌کند و به نقطه‌ی صحیح بعدی می‌رود).

اگر دو نفر از روبه‌رو, در یک نقطه‌ی صحیح به هم برخورد کنند. هردو جهت خود را به سمت راست خود تغییر می‌دهند ‎٩۰(‏ درجه در جهت عقربه‌های ساعت) و در جهت جدید. حرکت خود را ادامه می‌دهند. دقت کنید اگر دو نفر از جهت دیگری به هم برسند یا بین دو نقطه‌ی صحیح با هم روبه‌رو شوند. از کنار هم عبور کرده و تغییر جهت دمی دهند.

ایا دوستان مصطفی همواره می‌توانند طوری در بیابان قرار گیرند و جهت‌های مناسبی انتخاب کنند. که حتما مصطفی را پیدا کنند؟

پاسخ

اثبات می‌کنیم نقاطی از بیابان وجود دارد که دوستان مصطفی آن را نخواهند دید. در اول کار یک دایره به اندازه کافی بزرگ دور تمامی $n$ دوست در نظر می‌گیریم (چون متناهی هستند می‌توانیم). حال اگر تمامی دوستان همیشه درون این دایره بمانند قطعا نمی‌توانند نقاط بیرون دایره را ببینند و ما به خواسته خود می‌رسیم. پس بالاخره یکی از دوستان از دایره خارج می‌شود. حال اثبات می‌کنیم اگر فردی از دایره خارج شود دیگر نمی‌تواند تغییر جهت دهد:

  • برهان خلف: فرض کنید فردی از دایره خارج شده و نیز پس از این، تغییر جهت هم بدهد. یعنی با فرد دیگری برخورد کرده باشد. حال اولین برخورد دو فرد، خارج از دایره را در نظر بگیرید. این دو نفر را گراز خنگ و گاو دانا می‌نامیم. گراز خنگ و گاو دانا از لحظه خروج از دایره، مسیری مستقیم را طی کرده‌اند زیرا این اولین برخورد است. به علت مستقیم بودن مسیر ها، نقطه برخورد گراز خنگ و گاو دانا روی خط واصل نقاط خروج این دو نفر از دایره است. چون دایره یک شکلی محدب است خط واصل هر دو نقطه‌ای از آن کاملا درون دایره است. پس نقطه برخورد گاو دانا و گراز خنگ درون دایره است، که این با فرض ما تناقض دارد.

پس اگر فردی از دایره خارج شود دیگر نمی‌تواند تغییر جهت دهد. در آخر نقاطی از بیابان که دیده می‌شوند، نقاط درون یک دایره متناهی و $n$ خط است. که اینها همه‌ی نقاط صحیح را شامل نمی‌شوند. پس با هر روش حرکت دوستان، مصطفی می‌تواند نقطه‌ای برای مخفی شدن پیدا کند.


ابزار صفحه