سوال ۱۸
در بازی خرگوش‌کُشی یک جدول $۱۳۸۵\times ۱۳۸۵$ داریم که در هر خانه‌ی آن یک خرگوش قرار دارد. «مرد چکُش‌زن» بازی را شروع می‌کند. او در ابتدا یک خرگوش را به دلخواه خود با چکش می‌کشد. سپس در هر مرحله اگر در سطر یا ستونی که خرگوش قبلی را کشته، خرگوش زنده‌ای باشد٬ مجبور است یکی از خرگوش‌های آن سطر یا آن ستون را بکشد (به دلخواه یکی از آنها را بکشد). در غیر این صورت، خرگوش زنده‌ای را از هر جای جدول به دلخواه می‌کشد و بازی ادامه پیدا می‌کند. هدف ما پیدا کردن تعداد روش‌هایی است که مرد چکش‌زن می‌تواند همه‌ی خرگوش‌ها را بکشد. باقیماندهی این عدد بر ۲۳ چند است؟
- ۰
- ۱
- ۲
- ۲۱
- ۲۲
پاسخ
گزینه‌ی (۱) درست است.
می‌خواهیم ثابت کنیم تعداد حالات بر !1385 بخش‌پذیر است. فرض کنید برای هر سطر اولین زمانی که خرگوشی را در آن کشتیم شماره‌‌ی آن سطر را روی تخته می‌نویسیم. بدین ترتیب یک جایگشت از سطرها روی تخته نوشته می‌شود. حال در نظر داشته باشید که تعداد حالاتی که یک جایگشت را می‌سازند با یکدیگر برابرند چون با جایگزین کردن سطرها قوانین مسئله حفظ می‌شود و در نتیجه به ازای هر حالتی از یک جایگشت، یک حالت متناظر برای جایگشت‌های دیگر نیز وجود دارد (می‌توان همین روند را برای ستون‌ها نیز بیان کرد). در نتیجه پاسخ مسئله بر !1385 بخش‌پذیر است و باقیماندهی آن بر 23 صفر خواهد بود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
