دنبالهای از اعداد طبیعی و متمایز را در نظر بگیرید که از عدد ۱ شروع شده و به عدد $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$ چیست؟
پاسخ
گزینهی ۴ درست است.
با تجزیهی عدد داریم: $10800 = 2^4 \times 3^3 \times 5^2$ مانند استدلال سوال قبل، طول بلندترین دنبالهی عول برابر $k=10$ خواهد شد. حال برای آن که طول دنباله ۱۰ شود باید در هر مرحله دقیقن یک عامل در عدد ضرب شود. این تعداد معادل یک جایگشت از ۴ عدد ۲، ۳ عدد ۳ و ۲ عدد ۵ است. پس پاسخ برابر است با: $$\frac{9!}{4!3!2!} = 1260$$
چند دنبالهی عول به ازای $n=5120$ وجود دارد؟
پاسخ
گزینهی ۱ درست است.
با تجزیهی عدد داریم: $n = 2^{10} \times 5$ دو حالت داریم:
با استفاده از اتحادهای ترکیبیاتی پاسخ برابر است با: \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*}