المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

در جدول نشان‌داده شده در شکل زیر، دو خانه مجاور هستند اگر یک ضلع مشترک داشته باشند. مهدی می‌خواهد از خانه‌ی «آ» به خانه‌ی «ب» برود. او از هر خانه می‌تواند به هر کدام از خانه‌های مجاورش برود. ناصر می‌خواهد راه او را با گذاشتن مانع در بعضی خانه‌ها ببندد. اگر در خانه‌ای مانع قرار داشته باشد، مهدی دیگر نمی‌تواند به آن خانه برود. ناصر به چند روش می‌تواند راه مهدی را ببندد؟ توجه کنید در خانه‌ی «آ» و «ب» نمی‌توان مانع قرار داد.

  1. 63
  2. 127
  3. 49
  4. 77
  5. 69

پاسخ

گزینه‌ی ۴ درست است.

دو حالت را می‌شماریم:

  1. اگر در خانه‌ی وسط مانع قرار داده شود، دو مسیر از «آ» به «ب» موجود است. هر کدام از این مسیرها سه خانه‌ی خالی دارد که برای مسدود کردن آن باید در حداقل یکی از آن‌ها مانعی قرار داده شود. این کار به $(2^3-1)\times (2^3-1) = 49$ روش قابل انجام است.
  2. اگر در خانه‌ی وسط مانع قرار داده نشود، تعداد راه‌های قرار دادن مانع در خانه‌های ستاره‌دار که راه مهدی را ببندد به شرح زیر است:
  • ۲ راه با ۲ مانع: یک راه مانع گذاشتن در دو خانه‌ی مجاور «آ» و یک راه مانع گذاشتن در دو خانه‌ی مجاور «ب».
  • ۴ راه با ۳ مانع: هر روش قرار دادن سه مانع در خانه‌های ستاره‌دار، راه مهدی را می‌بندد.
  • ۱ راه با ۴ مانع.

مانع گذاشتن در دو خانه‌ی بالا چپ و پایین راست اختیاری است. بنابراین تعداد راه‌ها در این حالت برابر است با $(2 + 4 + 1)\times 2^2 = 28$.

پس در مجموع تعداد راه‌ها برابر است با $49 + 28 = 77$.


ابزار صفحه