المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۱

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

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

پاسخ

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

شکل مقلبل شکلی است که از هر نقطه‌ی آن می‌توان به نقطه‌ی دیگری رفت و کم‌ترین پاره خط ممکن را نیز داراست(۱۴ پاره‌خط). معلوم است که با حذف هر پاره‌خط دلخواهی از آن دو نقطه یافت خواهند شد که به هم‌مسیری نداشته باشند٬ بنابراین لازم است به شکل فوق یک یا چند پاره‌خط اضافه کنیم. اگر مجاز بودیم از پاره‌خط‌های غیر واحد نیز استفاده کنیم می‌توانستیم $A$ را به $B$ وصل کنیم که دراین صورت شکل به‌دست آمده(پانزده ضلعی فضایی) خاصیت مورد نظر را داشت٬ ولی چون مجاز به استفاده از پاره‌خط‌های غیر واحد نیستیم به ناچار $B$ را به $C$ و $A$ را به $D$ وصل می‌کنیم که شکل حاصل خاصیت مورد نظر را خواهد داشت و در ضمن دارای ۱۶ پاره‌خط به طول واحد می‌باشد.


ابزار صفحه