المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۸:سوال ۳۳

سوال ۳۳

یک جدول $۸\times ۸$ را در نظر بگیرید. مهره‌ی «نهنگ»٬ مهره‌ای است که اگر در یک خانه از این جدول $۸\times ۸$ قرار بگیرد٬ مطابق شکل تمامی خانه‌هایی که اکیدا بالاتر و سمت چپ‌تر از خانه‌ی خودش هستند٬ را تهدید می‌کند. به چند طریق می‌توان یک مهره‌ی نهنگ سیاه و یک مهره‌ی نهنگ سفید را در این جدول قرار داد٬ به طوری که هیچ‌ یک دیگری را تهدید نکند؟ (دقت کنید که نمی‌توان دو مهره نهنگ را در یک خانه قرار داد)

  1. ۴۶۲۱
  2. ۴۸۷
  3. ۸۶۵۱
  4. ۸۶۷
  5. ۲۱۵

پاسخ

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

وضعیت قرار گیری دو نهنگ نسبت به هم را به ۲ حالت زیر تقسیم می‌کنیم:

  • هم‌سطر یا هم‌ستون باشند: در این صورت برای نهنگ سیاه ۶۴ حالت و برای نهنگ سفید ۱۴ انتخاب داریم:$64×14=896$
  • در ۲ سر قطر یک مستطیل قرار گرفته باشند: تعداد زیرمستطیل‌های جدول $8×8$ برابر است با $\binom{8}{2}\times \binom{8}{2}$ (انتخاب ۲ خط افقی برای ضلع بالا و پایین مستطیل و ۲ خط عمودی برای ضلع چپ و راست آن)

برای هر مستطیل، مهره‌ها فقط می‌توانند در ۲ سر قطر غیر اصلی آن (به شکل رو‌به‌رو) قرار بگیرند که البته می‌توانند با هم جابه‌جا شوند.پس در این حالت $\binom{8}{2}\times \binom{8}{2}\times2=1568$ روش برای آنها وجود دارد.

با این توضیحات جواب مسئله ۲۴۶۴ می‌شود که متاسفانه در بین گزینه‌ها نیست.


ابزار صفحه