المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۴

در دو گوشه‌ی متقابل یک صفحه‌ی شطرنجی ‎$2000\times 2000$‎ دو مهره‌ی اسب قرار دارد. این دو مهره به‌نوبت حرکت می‌کنند. حرکت مهره‌ی اسب ‎۱‎ خانه در جهت عمودی یا افقی و ‎۲‎ خانه در جهت دیگر است. کم‌ترین مجموع تعداد حرکات لازم برای دو مهره چه‌قدر است تا این دو مهره روی یک خانه قرار بگیرند؟

  1. ۱۳۳۰
  2. ۱۳۳۱
  3. ۱۳۳۲
  4. ۱۳۳۳
  5. ۱۳۳۴

پاسخ

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

در هر حرکت اسب از یک خانه به خانه‌ای غیر هم‌رنگ آن می‌رود. معلوم است که دو خانه‌ی متقابل موارد اشاره در جدول $2000\times2000$ هم‌رنگ می‌باشند(مثلا سفید). اگر دو مهره هم‌دیگر را در خانه‌ای هم‌رنگ با خانه‌های مبدا ملاقات کنند آن‌گاه هر دو اسب به تعداد زوجی حرکت انجام داده‌اند که مجموع حرکاتشان زوج می‌شود. اگر دو مهره هم‌دیگر در خانه‌ای غیر هم‌رنگ یا خانه‌های مبدا ملاقات کنند٬ آن‌گاه هر دو اسب به تعداد فردی حرکت انجام داده‌اند که باز مجموع حرکاتشان زوج می‌شود. بنابراین عدد خواسته شده عددی زوج است. دو اسب مجموعا ۱۰۰۰ خانه در جهت افقی و ۱۰۰۰ خانه در جهت عمودی و مجموعا ۲۰۰۰ واحد جابه‌جا می‌شوند و با هر حرکت اسب سه واحد جابه‌جایی اتفاق می‌افتد.

بنابراین برای رسیدن به هدف حداقل $ \lceil \frac{2000}{3} \rceil$ یعنی ۱۳۳۳ حرکت لازم است که کوچک‌ترین عدد زوج بزر‌گ‌تر از ۱۳۳۳ عدد ۱۳۳۴ می‌باشد.


ابزار صفحه