فرشته و وزیر
کشوری با تعداد نامتناهی شهر داریم. این شهرها روی یک جاده بسیار بلند بنا شده‌اند. هر شهر به شهر بعد و قبل خود راه دارد. برای رفتن از هر شهری به شهر‌های مجاور باید صبح حرکت کنیم و ابتدای همان شب به مقصد می‌رسیم و شب باید در همان شهر اطراق کنیم.
وزیر بدجنسی می‌خواهد فرشته را به دام بیندازد. تنها ابزاری که وزیر در اختیار دارد. دام ساعتی خاصی است. او هر شب می‌تواند یک دام در یکی از شهرها قرار دهد و مشخص کند که در یکی از شب‌های بعدی دام به کار بیفتد.
فرشته نیز هر صبح یا به یکی از شهر‌های مجاور می‌رود یا سر جایش ساکن می‌ماند. اگر در شبی که دام به کار می‌افتد فرشته در همان شهری باشد که دام در آن‌جاست فرشته به دام می‌افتد. در غیر این صورت دام همان شب از کار می‌افتد.
آیا فرشته همیشه می‌تواند فرار کند؟ادعای خود را ثابت کنید.
پاسخ
ادعا می‌کنیم که فرشته به دام می‌افتد. فرض کنید در شب صفر هستیم و فرشته در خانه‌ی صفر قرار دارد و ابتدا ما حرکت می‌کنیم. همه‌ی دام‌ها را در شب ۳۲ ام فعال می‌کنیم. ۱۶ دام اول را طوری در خانه‌های ۳۱- تا ۳۱ قرار می‌دهیم که از هر ۴ خانه‌ی متوالی ۱ خانه دارای دام باشد.
تار روز ۱۶ ام ما $\frac{1}{4}$ خانه‌هایی که در شب ۳۲ ام فرشته می‌تواند در آن‌ها باشد را اشغال کرده‌ایم. به همین صورت تا روز ۸ ام $\frac{1}{4}$ دیگر را اشغال می‌کنیم. تا روز ۳۲ ام همه‌ی خانه‌هایی که فرشته می‌تواند در شب ۳۲ام در آن‌ها باشد را اشغال می‌کنیم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
