سوال ۱۰
در شکل رو‌به‌رو یک جدول کامل $۸ \times ۱$ نمایش داده شده است. با حذف دقیقاً یکی از اضلاع (افقی یا عمودی) به طول ۱ از یک جدول کامل٬ یک جدول ناقص به دست می‌آید. برای مثال٬ در این شکل ۲۵ ضلع وجود دارد که با حذف هر کدام٬ یک جدول ناقص تولید می‌شود.
قیمت یک جدول ناقص برابر است با تعداد مسیرهای به طول ۹ که از نقطه‌ي پایین سمت چپ به نقطه‌ی بالای سمت راست و فقط با عبور از ضلع‌ها به دست می‌آید.
فرض کنید $S$ مجموعه‌ی تمام قیمت‌های جداول ناقص است. باقی‌مانده‌ی تعداد اعضای غیرتکراری $S$ بر ۵ چند است؟
- ۰
- ۱
- ۲
- ۳
- ۴
پاسخ
گزینه‌ی (4) درست است.
باتوجه به اینکه این ضلع عمودی یا افقی انتخاب شده باشد حالت‌بندی می‌کنیم:
- افقی: در اینصورت تنها همان مسیری که شامل آن ضلع باشد حذف می‌شود. پس قیمت همگی آنها ۸ است.
- عمودی: مجموعه‌ی قیمت حالاتی که از ضلع سمت چپ انتخاب شود با سمت راست برابر است. قیمت حالات حذف ضلع سمت چپ به ترتیب برابر است با ۱ تا ۸.
پس در نهایت قیمت جداول اعداد ۱ تا ۸ شدند که باقیمانده‌اش بر ۵ برابر ۳ است.