سوال ۴

با توجه به تعریف مجموعه‌ی زیبا در مسئله‌ی قبل٬ یک جدول $3\times3$ شامل چند مجموعه‌ی زیباست؟

  1. ۹
  2. ۱۰
  3. ۱۱
  4. ۱۹
  5. ۲۰

پاسخ

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

به ازای هر مسیر با طول مینیمم(طول ۶) از $A$ به $B$ یک و فقط یک مجموعه‌ی زیبا یافت می‌شود. به عنوان مثال برای مجموعه‌ی زیبای $a$ (تهی) مسیر ۱ و برای مجموعه‌ی زیبای $b$ مسیر ۲ متناظر هستند.

تعداد مسیر‌های مطلوب در یک شبکه‌ی $m\times n$ برابر $\binom{m+n}{m}$ و در این مسئله برابر $\binom{6}{3}$ یعنی ۲۰ می‌باشد.