المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال۳۶

۴ نهنگ سفید و ۴ نهنگ سیاه به‌طور دسته‌جمعی تصمیم به خودکشی گرفته‌اند. در هر مرحله یک نهنگ، یکی از نهنگ‌های ناهمرنگ خود را انتخاب کرده و به قتل می‌رساند! می‌دانیم پس از ۷ مرحله، دقیقاً یک نهنگ، زنده مانده است. نهنگ‌ها از روی دنباله‌ی قتل‌ها، لیستی به نام «لیست سیاه» ساخته‌اند، به این ترتیب که پس از هر قتل، ابتدا رنگ قاتل، و سپس رنگ مقتول را به انتهای لیست اضافه می‌کنند. در پایان هم تنها نهنگ باقی‌مانده، رنگ خود را به انتهای لیست اضافه می‌کند. چند لیست سیاه متفاوت می‌تواند وجود داشته باشد؟

  1. ۱۲۸
  2. ۴۰
  3. ۷۰
  4. ۱۴۰
  5. ۳۲

پاسخ

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

از آن‌جایی که با دانستن رنگ قاتل می‌توان رنگ مقتول را فهمید، دنباله‌ای را در نظر می‌گیریم که در آن فقط رنگ قاتل‌ها را نوشته‌ایم.

آخرین قاتل همان نهنگ بازمانده است پس آخرین نهنگ مقتول از رنگ مخالف آن است. در نتیجه از مرحله‌ی اول تا قبل از مرحله‌ی آخر از هر دو رنگ حتما حداقل یک نهنگ داریم. پس قاتل‌ها به هر ترتیبی می‌توانند باشند.

فرض می‌کنیم نهنگ آخر سفید باشد (چون حالت‌ها متقارن‌اند). در نتیجه قاتل آخر نیز سفید است. در دنباله ۶ جای خالی داریم که با ۳ سیاه و ۳ سفید پر می‌شوند که تعداد حالت‌ها برابر ۲۰ می‌باشد.

در نتیجه کل حالت‌ها ۴۰ تاست.


ابزار صفحه