سوال ۵

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

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

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

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

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

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