المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۱:تئوری:سوال ۸

سوال ۸

این جا صحرای نوادا، ۱ آوریل سال ۱۸۲۳. صحرایی مستطیل شکل با ۴۳۳ مایل طول و ۳۵۷ مایل عرض. برادران دالتون، جو، ویلیام، جک و آوریل، سارقان مشهور غرب وحشی، به بانک شهر دالاس دست‌برد زدند و کیسه‌ی پول را به کوچک‌ترین برادر خود آوریل دادند تا آن را مخفی کند. ولی وقتی از او محل اختفا را پرسیدند، آوریل چیزی به یاد نیاورد و فقط می‌دانست کیسه را در یکی از نقاط صحرا که فاصله‌ی آن از اضلاع صحرا مقداری صحیح مایل بوده در دیل زمین نهاده است.

شهردار دالاس از کابوی همیشه تنها، لوک خوش‌شانس، خواست تا دالتون‌ها را دست‌گیر کند. لوک موفق شد تا سه نفر از آن‌ها را به دام اندازد؛ اما جو، بزرگ‌ترین برادر همچنان آزاد است.

جو قصد دارد که کیسه را با گشتن تمام نقاط صحیح صحرا بیابد. روش کار او به این صورت است که در ابتدای دقیقه‌ی $t$ محلی را که درآن قرار دارد می‌گردد و اگر کیسه را نیافت، به یکی از نقاط صحیحی که با مکان فعلیش ۱ مایل فاصله دارد می‌رود و در آغاز دقیقه‌ی $t+1$ به آن‌جا می‌رسد.

لوک که از نقشه‌ی جو باخبر شده قصد دارد او را در همین فرصت به دام اندازد. متاسفانه او از مسیر حرکت جو مطلع نیست. در ابتدا لوک و جو در دو نقطه‌ی صحیح صحرا قرار دارند. فرض کنید در ابتدای دقیقه $t$ قرار داریم . لوک باید راس دقیقه $t+1$ در یکی از چهار نقطه‌ی مجاور باشد. همچنین بنا به سفارش شهردار، او مجبور است جهتی را برای حرکتش انتخاب کند که وی را به مکان فعلی جو(در ابتدای دقیقه‌ی $t$) نزدیک‌تر کند. توجه کنید که لوک از جهت حرکتی که جو، هم‌زمان در آغاز دقیقه‌ی $t$ انتخاب می‌کند بی‌اطلاع است. تیررس لوک ۲ مایل است و وقتی جو در تیررس لوک باشد، تسلیم می‌شود.

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

پاسخ


ابزار صفحه