تمرین های کتاب (مبحث توپ و ظرف)

حل:

الف) طوری که احتمال وجود دو تا پسورد مساوی کمتر از احتمال متمایز بودن پسوردها باشد.

تعداد ظرفها: تعداد شماره های 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