المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۲

فرض کنید شبکه‌ای ‎$4\times 5$‎ از نقاط داریم که خانه‌ها با فاصله‌های منظم ‎۱‎ از هم قرار دارند و بین بعضی از خانه‌ها با فاصله ‎۱‎ خطوطی رسم شده است. یک ماشین در اختیار داریم که اگر شبکه‌ای را به او بدهیم یک شبکه عیناً مثل همان برای ما می‌سازد. در این صورت، ما دو شبکه عین هم خواهیم داشت. ما هم حق داریم این دو شبکه را هر طوری که بخواهیم روی هم بیندازیم: می‌توانیم شبکه‌ها را از صفحه جدا کنیم و در فضا بچرخانیم، فقط ابعاد دو شبکه باید بر هم منطبق باشند. یعنی باز هم یک شبکه ‎$5\times 6$‎ از نقاط خواهیم داشت. حالا دو نقطه مجاور به هم وصل هستند. اگر در حداقل یکی از شبکه‌هایی که روی هم رفته‌اند این دو به هم وصل بوده باشند مثلاً از شبکه راست به چپ برسیم. می‌خواهیم با تعدادی بار استفاده از این ماشین شبکه پر شود (تمام خانه‌های مجاور با فاصله ‎۱‎ به هم وصل شوند) حداقل تعداد خطوط اولیه چقدر می‌تواند باشد؟

  1. ۸
  2. ۹
  3. ۱۰
  4. ۱۱
  5. ۱۳

پاسخ

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

اگر شبکه‌ی زیر را چهار بار به ماشین بدهیم شکل مطلوب به‌دست خواهد آمد.


ابزار صفحه