دنبالهای از اعداد طبیعی و متمایز را در نظر بگیرید که از عدد ۱ شروع شده و به عدد n ختم میشود. به چنین دنبالهای عول گوییم، اگر هر عدد دنباله، مضرب عدد قبلی باشد. برای مثال دنبالهی ⟨1,3,6,30,60⟩ یک دنبالهی عول است.
تعداد عناصر بلندترین دنبالهی عول به ازای n=810000 چیست؟
پاسخ
گزینهی ۵ درست است.
با تجزیهی n داریم: 810000=24×34×54 در هر مرحله دست کم یک عامل در عدد ضرب میشود. پس طول بلندترین دنبالهی عول ۱۳ خواهد بود.
تعداد عناصر بلندترین دنبالهی عول به ازای n=10800 را k در نظر بگیرید. تعداد دنبالههای عول k عنصره به ازای n=10800 چیست؟
پاسخ
گزینهی ۴ درست است.
با تجزیهی عدد داریم: 10800=24×33×52 مانند استدلال سوال قبل، طول بلندترین دنبالهی عول برابر k=10 خواهد شد. حال برای آن که طول دنباله ۱۰ شود باید در هر مرحله دقیقن یک عامل در عدد ضرب شود. این تعداد معادل یک جایگشت از ۴ عدد ۲، ۳ عدد ۳ و ۲ عدد ۵ است. پس پاسخ برابر است با: 9!4!3!2!=1260
چند دنبالهی عول به ازای n=5120 وجود دارد؟
پاسخ
گزینهی ۱ درست است.
با تجزیهی عدد داریم: n=210×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*}