المپدیا

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

ابزار کاربر

ابزار سایت


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

معلم مینگو

مینگو یک مجموعه به نام $S$ از اعداد طبیعی 1 تا $n$ دارد. به ازای هر $A \subseteq S$، $F(A)$ را این‌گونه تعریف می‌کنیم: $$F(A)=\{x=\frac{b}{a}~ |~ a,b\in A, x \in \mathbb{N},x>1\}$$

که $\mathbb{N}=\{1,2,3,\ldots\}$ مجموعه‌ی اعداد طبیعی می‌باشد.

اگر $Y_1, Y_2, \ldots, Y_{2^n}$ همه‌ی $2^n$ زیرمجموعه‌ی $S$ باشند، معلم مینگو از او خواسته تا مقدار زیر را محاسبه کند: $$X=\sum_{i=1}^{2^n} |F(Y_i)|$$ نکته: $|F(Y_i)|$ نشان‌دهنده‌ی تعداد اعضای مجموعه‌ی $F(Y_i)$ می‌باشد.

$2$- الف ($10$ نمره) : باقی‌مانده‌ی $X$ بر $\Delta$ به ازای $n=20$ چند است؟

$2$- ب ($12$ نمره) : باقی‌مانده‌ی $X$ بر $\Delta$ به ازای $n=1000$ چند است؟

$2$- ج ($15$ نمره) : باقی‌مانده‌ی $X$ بر $\Delta$ به ازای $n=10^6$ چند است؟


ابزار صفحه