Processing math: 75%

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

سوال ۲۵

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

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

پاسخ

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

با تجزیه‌ی n داریم: 810000=24×34×54 در هر مرحله دست کم یک عامل در عدد ضرب می‌شود. پس طول بلندترین دنباله‌ی عول ۱۳ خواهد بود.

سوال ۲۶

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

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

پاسخ

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

با تجزیه‌ی عدد داریم: 10800=24×33×52 مانند استدلال سوال قبل، طول بلندترین دنباله‌ی عول برابر k=10 خواهد شد. حال برای آن که طول دنباله ۱۰ شود باید در هر مرحله دقیقن یک عامل در عدد ضرب شود. این تعداد معادل یک جایگشت از ۴ عدد ۲، ۳ عدد ۳ و ۲ عدد ۵ است. پس پاسخ برابر است با: 9!4!3!2!=1260

سوال ۲۷

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

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

پاسخ

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

با تجزیه‌ی عدد داریم: n=210×5 دو حالت داریم:

  • عامل پنج در یک مرحله‌ی مستقل ضرب شود. در این صورت اگر عامل‌های ۲ در k مرحله ضرب شوند، تعداد حالات برابر تعداد جواب‌های معادله‌ی x1++xk=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*}


ابزار صفحه