====== سوال ۵ ======


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

{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۹:untitled112.png |}}


  - 63
  - 127
  - 49
  - 77
  - 69

<راهنمایی>
روی مانع دار شدن خانه ی وسط حالت بندی کنید.
</راهنمایی>

<پاسخ>
 گزینه‌ی ۴ درست است.



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

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

  * ۲ راه با ۲ مانع: یک راه مانع گذاشتن در دو خانه‌ی مجاور «آ» و یک راه مانع گذاشتن در دو خانه‌ی مجاور «ب».
  * ۴ راه با ۳ مانع: هر روش قرار دادن سه مانع در خانه‌های ستاره‌دار، راه مهدی را می‌بندد.
  * ۱ راه با ۴ مانع.


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


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

  * [[سوال ۴|سوال قبل]]
  * [[سوال ۶|سوال بعد]]