فهرست مندرجات
سوالات ۲۰ تا ۲۲
جدولی $n \times n$ داریم (طول ضلع $n$ است) که هر واحد ضلع آن یک چوب کبریت است. ما هر بار زیر مجموعه‌ای از چوبکبریتها (این زیرمجموعه می‌تواند تهی باشد) را برمی‌داریم و سپس تعداد مسیرهای ممکن از گوشه‌ی پایین چپ به بالا راست (فقط با حرکات راست و یا بالا) را می‌شماریم. پس از این کار چوبکبریتها را به حالت اولیه برمی‌گردانیم و دوباره زیرمجموعه‌ای جدید را حذف می‌کنیم.
با توجه به توضیحات بالا به ۳ سوال زیر پاسخ دهید:
سوال ۲۰
فرض کنید $n=۳$ است. به ازای تمام زیرمجموعه‌های ممکن از چوبکبریتها حرکت بالا را انجام داده و عدد نهایی را روی تخته نوشته‌ایم. در نهایت روی تخته چند عدد مختلف وجود دارد؟
- ۱۸
- ۲۰
- ۱۹
- ۲۱
- ۱۶
پاسخ
گزینه (۴) درست است.
تمامی اعداد ۰ تا ۲۰ را می‌توان تولید نمود.
سوال ۲۱
فرض کنید $n=۴$ است. تنها زیرمجموعه‌هایی از چوبکبریتها را در نظر بگیرید که تعداد مسیرهای معتبرشان برابر ۶۰ است. این بار به ازای هرکدام از این زیرمجموعه‌ها تعداد چوب‌کبریت‌های حدف شده را روی تخته می‌نویسیم. کمینه و بیشینه عددی که روی تخته نوشته شده چند است؟
- ۱۰٫۲
- ۸٫۲
- هیچ حالتی ۶۰ مسیر معتبر ندارد.
- ۱۰٫۱
- ۸٫۱
پاسخ
گزینه (۵) درست است.
با حذف یکی از چوب کبریت‌ها ۱۰ مسیر حذف می‌شود و می‌توان به ۶۰ مسیر معتبر رسید. از طرفی چوب کبریت‌های کناری که مجموعا ۱۲ تا هستند ۱۶ مسیر را حذف می‌کنند و بقیه چوب کبریت‌ها حداقل ۱۰ مسیر را حذف خواهند کرد (که مقرون به صرفه نیست آن‌ها را حذف کنیم). می‌توان با حذف ۸ چوب کبریت از آن‌ها ۱۰ مسیر را حذف نمود. از طرفی با اضافه کردن ۴ چوب کبریت از بین این ۱۲ تا حداکثر ۶ مسیر اضافه می‌شود. پس بیش‌ترین تعداد نیز ۸ عدد است.
سوال ۲۲
فرض کنید $n=۵$ است. به ازای چندتا از اعداد مجموعه‌ی {۳۲٫۶۴٫۱۲۸٫۲۴۳٫۲۴۹} می‌توان چوبکبریتها را به شکلی حذف کرد که تعداد مسیرهای معتبر برابر با آن عدد شود؟
- ۳
- ۲
- ۵
- ۴
- ۱
پاسخ
گزینه (۴) درست است.
تنها عدد ۲۴۹ را نمی‌توان ساخت و بقیه اعداد قابل تولید هستند. برای هر یک مثالی وجود دارد که آن را به دست می‌آورد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
