المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳

می‌خواهیم هر نقطه موجود در دسته‌ی $i+۱$ وصل کنیم ($i ≤۳$) به‌طوری‌ که هیچ دو نقطه‌ای از دسته‌ی $i$ام به یک نقطه از دسته‌ی $i+۱$ام وصل نباشند. هم‌چنین می‌خواهیم هر نقطه موجود در دسته‌ی ۴ را با یک پاره‌خط به دقیقاً یک نقطه در دسته‌ی ۱ وصل کنیم به‌طوری‌که هیچ دو نقطه‌ای از دسته ۴ به یک نقطه از دسته‌ی اول وصل نباشند. به چند طریق می‌توان این کار را انجام داد؟

  1. $4^3×2^4×3^4$
  2. $4^4×2^4×3^4$
  3. $4^3×2^3×3^5$
  4. $4^3×2^5×3^3$
  5. $4^4×2^3×3^3$

پاسخ

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

در شکل مقابل مقصد هر یک از پاره‌خط‌های خارج شده از چهار نقطه به ترتیب به ۲٬۳٬۴ و ۱ طریق مشخص می‌شود که طبق اصل ضرب تعداد کل حالات برابر !۴ می‌شود. این موضوع از دسته ۲ به دسته ۳ و از دسته ۳ به دسته ۴ و نیز از دسته ۴ به دسته ۱ نیز به همین صورت است. بنابراین جواب مورد نظر $(4!^4)$ یا $4^4\times3^4\times2^4$ می‌باشد.


ابزار صفحه