Processing math: 19%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۸

چند دنباله‌ی a1,a2,...,a13 از اعداد ۱ تا ۱۳ وجود دارد که هر عدد دقیقا یک بار در آن ظاهر شده باشد و نیز ai از a3i1 و a3i+1 کوچک تر باشد؟

  1. {\binom{12}{4}}^2 \times 6^3
  2. {\binom{13}{9}}^2 \times 3^3
  3. {\binom{12}{4}}^2
  4. 3^3 \times 24
  5. {\binom{13}{9}}^2

پاسخ

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

باید درخت موجود در شکل زیر را تکمیل کنیم(«» نشانگر آن است که عدد x از عدد y کوچک‌تر است).

عدد a_1 کوچک‌ترین عدد ممکن یعنی ۱ می‌باشد. حال ۱۲ عدد باقی‌مانده را به سه دسته‌ی چهار تایی تقسیم می‌کنیم تا به شاخه‌های a_1 اختصاص دهیم که این کار به \binom{12}{4} \binom{4}{8} \binom{4}{4} طریق ممکن است. در بین دسته‌ی اول کوچک‌ترین عدد را به a_2 و سه عدد دیگر را به 3! طریق بین a_5 و a_6 و a_7 تقسیم می‌کنیم. دسته‌های دیگر را نیز به همین صورت بین a_i های باقی‌مانده تقسیم می‌کنیم٬ بنابراین جواب مورد نظر برابر \binom{12}{4} \binom{4}{8} \times (3!)^3 خواهد شد که جواب صحیح در بین گزینه‌های نیامده است.


ابزار صفحه