المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۵:سوال ۱۰

سوال ۱۰

یک صفحه‌ی شطرنجی نامتناهی را درنظر بگیرید. مهره‌ی اسب در این صفحه به این صورت حرکت می‌کند که دو خانه در یک جهت (افقی یا عمودی) و یک خانه در جهت دیگر حرکت می‌کند.

حداقل تعداد حرکت‌های لازم برای این که اسب بتواند خود را از خانه‌ی ‎$(0‎, ‎0)$‎ به خانه‌ی ‎$(1374‎, ‎1374)$‎ برساند، چند تاست؟

  1. ۴۵۸
  2. ۹۱۶
  3. ۱۳۷۵
  4. ۶۸۷
  5. ۱۳۷۴‎

پاسخ

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

از خانه‌ی $(0,0)$ تا خانه‌ی $(1374,1374)$ خانه در راستای عمودی و ۱۳۷۴ خانه در راستای عمودی و ۱۳۷۴ خانه در راستای افقی و در مجموع ۲۷۴۸ خانه فاصله وجود دارد. در هر حرکت سه خانه توسط اسب طی می‌شود٬ پس برای رسیدن به خانه‌ی مورد نظر حداقل $\frac{2748}{3}$ یعنی ۹۱۶ حرکت لازم است. با ۹۱۶ حرکت می‌توان به خانه‌ی مورد نظر رسید. کافی است یک حرکت در راستای افقی(دو خانه در جهت افقی و یک خانه در جهت عمودی) و یک حرکت در راستای عمودی(دو خانه در جهت عمودی و یک خانه در جهت افقی) انجام داد و این عمل را ۹۱۶ مرتبه متوالیا تکرار کرد.


ابزار صفحه