المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۴:سوال ۱۰

سوال ۱۰

درخت روبه‌رو را در نظر بگیرید. می‌خواهیم اعداد ۱۲ ٫… ۱٫۲٫ را در رأس‌های این درخت قرار دهیم به طوری که عدد هر رأس از اعداد فرزندان آن بیش‌تر باشد. به چند حالت این کار امکان‌پذیر است؟

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

پاسخ

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

ریشه درخت حتما عدد ۱۲ است. حال کافیست ۵ عدد برای درخت سمت چپ در نظر بگیریم و ۶ عدد هم برای درخت سمت راست و به صورت بازگشتی مسئله را حل کنیم. درهر مرحله عدد روی ریشه به صورت یکتا مشخص می‌شود و بقیه اعداد باید در زیر درخت‌ها افراز شوند. پاسخ نهایی برابر است با:

$$\binom{11}{5}\binom{3}{4}\binom{1}{2}\binom{3}{5}\binom{1}{2}\binom{1}{2}=147840$$


ابزار صفحه