المپدیا

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

ابزار کاربر

ابزار سایت


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

تفاوت‌ها

تفاوت دو نسخه‌ی متفاوت از صفحه را مشاهده می‌کنید.

پیوند به صفحه‌ی تفاوت‌ها

سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۸:سوالات_۲۵_تا_۲۷ [2018/12/20 10:24] (فعلی)
Hamidreza seydi ایجاد شد
خط 1: خط 1:
 +====== سوالات ۲۵ تا ۲۷ ======
 +
 +
 +
 +
 +دنباله‌ای از اعداد طبیعی و متمایز را در نظر بگیرید که از عدد ۱ شروع شده و به عدد $n$ ختم می‌شود. به چنین دنباله‌ای
 +**عول**
 +گوییم، اگر هر عدد دنباله، مضرب عدد قبلی باشد. برای مثال دنباله‌ی
 +$\langle 1, 3, 6, 30, 60 \rangle$
 +یک دنباله‌ی عول است.
 +
 +
 +
 +
 +
 +====== سوال ۲۵ ======
 +
 +
 +
 +
 +تعداد عناصر بلندترین دنباله‌ی عول به ازای
 +$n=810000$
 +چیست؟
 +
 +  - ۹
 +  - ۱۰
 +  - ۱۱
 +  - ۱۲
 +  - ۱۳
 +
 +
 +
 +
 +
 +
 +<​پاسخ>​
 +گزینه‌ی ۵ درست است.
 +
 +
 +
 +با تجزیه‌ی $n$ داریم:
 +$$810000 = 2^4 \times 3^4 \times 5^4$$
 +در هر مرحله دست کم یک عامل ​ در عدد ضرب می‌شود. پس طول بلندترین دنباله‌ی عول
 +۱۳ خواهد بود.
 +
 +
 +
 +
 +</​پاسخ>​
 +====== سوال ۲۶ ======
 +
 +
 +
 +تعداد عناصر بلندترین دنباله‌ی عول به ازای
 +$n=10800$
 +را
 +$k$
 +در نظر بگیرید. تعداد دنباله‌های عول $k$ عنصره به ازای
 +$n=10800$
 +چیست؟
 +
 +
 +  - ۵۱۲۰
 +  - $9!$
 +  - ۲۸۸
 +  - ۱۲۶۰
 +  - $6!$
 +
 +
 +
 +<​پاسخ>​
 +
 +
 +گزینه‌ی ۴ درست است.
 +
 +
 +
 +با تجزیه‌ی عدد داریم:
 +$10800 = 2^4 \times 3^3 \times 5^2$
 +مانند استدلال سوال قبل، طول بلندترین دنباله‌ی عول برابر
 +$k=10$
 +خواهد شد.
 +حال برای آن که طول دنباله ۱۰ شود باید در هر مرحله دقیقن یک عامل در عدد ضرب شود. این تعداد معادل یک جایگشت از ۴ عدد ۲، ۳ عدد ۳ و ۲ عدد ۵ است. پس پاسخ برابر است با:
 +$$\frac{9!}{4!3!2!} = 1260$$
 +
 +
 +
 +</​پاسخ>​
 +
 +
 +
 +====== سوال ۲۷ ======
 +
 +
 +
 +چند دنباله‌ی عول به ازای
 +$n=5120$
 +وجود دارد؟
 +
 +  - ۶۱۴۴
 +  - ۳۰۷۲
 +  - ۱۲۲۸۸
 +  - ۴۰۹۶
 +  - ۵۶۳۲
 +
 +
 +
 +
 +
 +
 +
 +
 +<​پاسخ>​
 +گزینه‌ی ۱ درست است.
 +
 +
 +
 +با تجزیه‌ی عدد داریم:
 +$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*}
 +
 +
 +
 +</​پاسخ>​
 +
 +
 +
 +
 +
 +  * [[سوالات ۲۳ و ۲۴|سوال قبل]]
 +  * [[سوالات ۲۸ تا ۳۰|سوال بعد]]
 +
  

ابزار صفحه