المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۸:سوالات ۲۵ تا ۲۷

سوالات ۲۵ تا ۲۷

دنباله‌ای از اعداد طبیعی و متمایز را در نظر بگیرید که از عدد ۱ شروع شده و به عدد $n$ ختم می‌شود. به چنین دنباله‌ای عول گوییم، اگر هر عدد دنباله، مضرب عدد قبلی باشد. برای مثال دنباله‌ی $\langle 1, 3, 6, 30, 60 \rangle$ یک دنباله‌ی عول است.

سوال ۲۵

تعداد عناصر بلندترین دنباله‌ی عول به ازای $n=810000$ چیست؟

  1. ۹
  2. ۱۰
  3. ۱۱
  4. ۱۲
  5. ۱۳

پاسخ

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

با تجزیه‌ی $n$ داریم: $$810000 = 2^4 \times 3^4 \times 5^4$$ در هر مرحله دست کم یک عامل در عدد ضرب می‌شود. پس طول بلندترین دنباله‌ی عول ۱۳ خواهد بود.

سوال ۲۶

تعداد عناصر بلندترین دنباله‌ی عول به ازای $n=10800$ را $k$ در نظر بگیرید. تعداد دنباله‌های عول $k$ عنصره به ازای $n=10800$ چیست؟

  1. ۵۱۲۰
  2. $9!$
  3. ۲۸۸
  4. ۱۲۶۰
  5. $6!$

پاسخ

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

با تجزیه‌ی عدد داریم: $10800 = 2^4 \times 3^3 \times 5^2$ مانند استدلال سوال قبل، طول بلندترین دنباله‌ی عول برابر $k=10$ خواهد شد. حال برای آن که طول دنباله ۱۰ شود باید در هر مرحله دقیقن یک عامل در عدد ضرب شود. این تعداد معادل یک جایگشت از ۴ عدد ۲، ۳ عدد ۳ و ۲ عدد ۵ است. پس پاسخ برابر است با: $$\frac{9!}{4!3!2!} = 1260$$

سوال ۲۷

چند دنباله‌ی عول به ازای $n=5120$ وجود دارد؟

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

پاسخ

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

با تجزیه‌ی عدد داریم: $n = 2^{10} \times 5$ دو حالت داریم:

  • عامل پنج در یک مرحله‌ی مستقل ضرب شود. در این صورت اگر عامل‌های ۲ در $k$ مرحله ضرب شوند، تعداد حالات برابر تعداد جواب‌های معادله‌ی $x_1 + \ldots + x_k=10$ در مجموعه‌ی اعداد طبیعی است که برابر $\binom{9}{k-1}$ می‌باشد. انتخاب مرحله‌ی عدد پنج نیز $k+1$ حالت دارد.
  • مانند استدلال حالت قبل $\binom{9}{k-1}$ حالت برای پخش عوامل دو در یک دنباله‌ی به طول $k$ داریم، اما این بار انتخاب مرحله‌ی عدد پنج $k$ حالت دارد.

با استفاده از اتحادهای ترکیبیاتی پاسخ برابر است با: \begin{align*} S &= \sum_{k=1}^{10} (k+1) \binom{k-1}{9} + \sum_{k=1}^{10} k \binom{k-1}{9}\\ &= 2 \sum_{k=1}^{10} (k-1) \binom{k-1}{9} + 3\sum_{k=1}^{10} \binom{k-1}{9}\\ &= 2 \times 9 \times 2^{9-1} + 3 \times 2^9\\ &= 6144\\ \end{align*}


ابزار صفحه