تعداد n جعبه داریم با شماره های 1 تا n. در ابتدای کار میزی خالی داریم. حال در مرحلهی iام 0<i≤n اگر k جعبه روی میز بود به احتمال 1k+1 جعبه i در هر یک از جعبههای روی زمین قرار میگیرد و از بین میرود و به احتمال 1k+1 در جایی خالی روی میز قرار میگیرد. امید ریاضی تعداد جعبههایی که در نهایت روی زمین قرار میگیرد را e(n) بگیرید.
2- الف (10 نمره) : ثابت کنید e(n) از Ω(logn) است.
2- ب (25 نمره) : ثابت کنید e(n) از O(√n) است.
2- ج (10 نمره) : θ(e(n)) را بیابید. مثلا e(3)=2312 است.