حل:
الف) طوری که احتمال وجود دو تا پسورد مساوی کمتر از احتمال متمایز بودن پسوردها باشد.
تعداد ظرفها: تعداد شماره های 4 رقمی = 10 به توان 4
p=(1-1/10000)(1-2/10000)...(1-(n-1)/10000)
p>1-p ==> p>1/2
1-a/b < e^-a/b ==> p < product( e^-i/10000) {1<= i < n} ==> p < e^-sum(i)/10000
p < e^-n*(n-1)/20000
ln: -1 < -n(n-1)/20000
20000 > n(n-1)
==> n =...
20000 > n^2 ==> 100=n مثلا
ب) طوری که دو شماره مساوی نداشته باشیم..
تعداد ظرفها: تعداد شماره های 9 رقمی = 10 به توان 9
بقیه حل مثل الف
ج) اگر 13 رقمی باشد..
الف که همان جواب قبلی است، چون فقط 4 رقم آخر مهم است.
ب تعداد ظرفها به تعداد شماره های 13 رقمی است.
__________________________________________________
راه ساده تر حل سوال این است که از مساله توپ و ظرف استفاده کنیم: اگر n*ln(n) توپ داشته باشیم هیچ ظرفی خالی نیست. (با احتمال خوب)
الف)
10^4*log(10^4) > 12*10^4
ب)
10^9*log(10^9) > 27*10^9
ج)
10^13*log(10^13) > 39*10^13
حل:
تقارن ندارد و احتمالها یکنواخت هم نیستند، پس حالت خاص نیست. با matlab حساب کردم این شد:
>> P^33
ans =
0.2346 0.3048 0.2631 0.1975
0.2346 0.3048 0.2631 0.1975
0.2346 0.3048 0.2631 0.1975
0.2346 0.3048 0.2631 0.1975
جوابش همون طور که می بینید همه ی سطرهاش مساویند.
حل:
راه حل دوم: با رسم گراف آن می بینیم که احتمال تغییر وضعیت 1-p و احتمال ماندن در هر وضعیت p است.
حل:
با یک random walk گراف را رنگ می کنیم. راس اولی که در آن هستیم، قرمز می کنیم و راس بعدی را آبی و ادامه می دهیم. (بقیه اش سخت بود راه حل رو بخونید:)
جواب
حجم: 282 کیلوبایت
مرجع: http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s02/www/sol7.ps
1- یک تاس n وجهی داریم که احتمال آمدن هر وجه آن pi است. ثابت کنید آنتروپی آن وقتی ماکسیمم است که pi=1/n باشد.
H(X) = sum(H(Xi))
طبق نامساوی حسابی هندسی (مثلا) مجموع وقتی ماکسیمم می شود که همه با هم برابر باشند.
i,j: H(Xi) = H(Xj) ==> pi = pj = 1/n
2-
فرض می کنیم یک سکه با احتمال q داریم و می خواهیم اعداد n بیتی بسازیم.
دو به توان آنتروپی n بار پرتاب سکه:
2^(n*H(q)) = q^nq * (1-q)^n(1-q)
چیزی که باید ثابت کنیم این است:
C(n,nq) >= q^nq * (1-q)^(n-nq) / ( 2*sqrt(n) )
از باز کردن سمت چپ استفاده می کنیم:
C(n,nq) = n!/ ( (nq)! (n-nq)! )
طبق فرمول استرلینگ داریم:
n! > sqrt(2*pi*n)*(n/e)^n
1/n! > 1/ ( sqrt(2*pi*n) * (n/e)^n * e^1/(12n) )
به جای صورت و مخرج از فرمولهای بالا جایگذاری می کنیم و ساده می کنیم.
جمله ی (n/e)^n را هم به دو جمله با توانهای nq و n-nq می شکنیم:
C(n,nq) >= (e^1/12n) / ( q^-nq * (1-q)^-n(1-q) * e^(1/12nq+1/12(n-nq) )
C(n,nq) >= 2^nH(q)
پس کافی است ثابت کنیم:
e^ (1/12n-1/12nq-1/12(n-nq) ) >= 1/ (2*sqrt(n) )
ساده می کنیم:
1/12n-1/12nq-1/12(n-nq) = 1/(12n) * ( 1-1/q-1/(1-q) )
1/ ( 2*sqrt(n) ) = 1/2* n^-1/2
نامساوی حسابی هندسی:
1/q+1/(1-q) = 1/( q*(1-q) ) >= 4
1-1/q-1/(1-q) <= -3
e^ (1/12n-1/12nq-1/12(n-nq) ) >= e^-3*(1/12n) = e^-1/(4n)
یعنی باید ثابت کنیم
e^ -1/(4n) >= 1/ (2*sqrt(n) )
e^-1/(4n) = (1/e)^1/(4n) >= (1/2)^1/(4n) >=
من فکر کردم همین نامساوی اجتماع چندتا پیشامد کمتر از جمع احتمال تک تکشونه خوبه براش!