All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Pandigital + (Posted on 2017-05-03) Difficulty: 3 of 5
Let p(n) be the probability that a random n-digit integer has all 10 digits occurring each at least once.
Let us allow leading zeroes; e.g. 0000018274 will be included in the set of 10-digit numbers).

So p(9) is 0 , p(10) = 10!/1010 and p(1000) would be very close to 1.

a. What is the smallest n for which p(n) > 1/2?
b. >3/4?
c. >.95?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Analytic solution with Computer calculations | Comment 1 of 3
Well this gives me the opportunity to use the inclusion/exclusion principle, used in my Dice Proposition puzzle.


It's easier to explain using ternary numbers (fewer digits to worry about).

There, p(5), say, represents the probability of getting all three possible digits in what amounts to five tries. I'll use capital P to designate the probability of a given set, of 1, 2 or 3 of the digits, with the digits specified: for example P(0 and 2) would be the probability of getting both at least one zero and at least one 2. P(0 or 1) would be the probability that at least one of those two digits would appear among the five specified for p(5).

In that terminology p(5) is the equivalent of P(0 and 1 and 2) in this ternary problem.

Using the inclusion/exclusion method:

P(0 and 1 and 2) = P(0) + P(1) + P(2) - P(0 or 1) - P(0 or 2) - P(1 or 2) + P(0 or 1 or 2)

Since the probabilities of each possible digit are equal, the terms can be combined:

3*P(0) - 3*P(0 or 1) + P(0 or 1 or 2)

or more generally

C(3,1)*P(0) - C(3,2)*P(0 or 1) + C(3,3)*P(0 or 1 or 2)

Here, remember that P(0 or 1), for example is equivalent to the probability that not all the digits are 2, and P(0) is the probabilty that not all the digits come from the set {1,2}.

Numerically that's 3*(1-(2/3)^5) - 3*(1-(1/3)^5) + 1, which comes out to about .61728395061729.

Back to Decimal:

p(n) =

10*P(0) - C(10,2)*P(0 or 1) + C(10,3)*P(0 or 1 or 2) - ... + C(10,9)*P(0 or 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8) - P(0 or 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9) 

where capital P(i) is defined contingent on n so that the following substitution represents the case for n:

10*(1-(9/10)^n) - C(10,2)*(1-(8/10)^n) + C(10,3)*(1-(7/10)^n) - ... + C(10,9)*(1-(1/10)^n) - 1

    4   kill "pandig+.txt"
    5   open "pandig+.txt" for output as #2
   10   for N=1 to 100
   20   Tot=0
   30   for I=1 to 10
   40      Term=combi(10,I)*(1-((10-I)//10)^N)*(-1)^(I-1)
   50      Tot=Tot+Term
   60   next
   70   print N,Tot,Tot/1
   75   print #2,N,Tot,Tot/1
   80   next

finds

               probability
  n   rational            decimal approximation
   1  0   0 
   2  0   0 
   3  0   0 
   4  0   0 
   5  0   0 
   6  0   0 
   7  0   0 
   8  0   0 
   9  0   0 
  10  567/1562500   0.00036288 
  11  6237/3125000   0.00199584 
  12  193347/31250000   0.006187104 
  13  891891/62500000   0.014270256 
  14  26675649/976562500   0.027315864576 
  15  143594451/(3125x10^6)   0.04595022432 
  16  10985907933/(15625x10^7)   0.0703098107712 
  17  31279509261/(3125x10^8)   0.1000944296352 
  18  21042596876301/(15625x10^10)   0.1346726200083263999 
  19  54125483631219/(3125x10^11)   0.1732015476199007999 
  20  671054134991877/(3125x10^12)   0.2147373231974006399 
  21  1614524160366117/(625x10^13)   0.2583238656585787199 
  22  236763267123649959/(78125x10^13)   0.3030569819182719474 
  23  271972926778836591/(78125x10^13)   0.3481253462769108364 
  24  122760128744112321/(3125x10^14)   0.3928324119811594271 
  25  54575491469075577/(125x10^15)   0.4366039317526046159 
  26  1496829579280832563767/(3125x10^18)   0.4789854653698664203 
  27  3247709559153727376709/(625x10^19)   0.5196335294645963802 
  28  34893950629539961690731/(625x10^20)   0.558303210072639387 
  29  74354284708591053185019/(125x10^21)   0.5948342776687284254 
  30  24575671455185092431306663/(390625x10^20)   0.6291371892527383661 
  31  103309351627654392774534981/(15625x10^22)   0.6611798504169881137 
  32  1079649425698155662929610031/(15625x10^23)   0.6909756324468196242 
  33  2245540231325863045575464463/(3125x10^24)   0.7185728740242761745 
  34  1162571749958790105933707292969/(15625x10^26)   0.7440459199736256677 
  35  479679774018898077792619889283/(625x10^27)   0.7674876384302369244 
  36  24656352941464094518259205701241/(3125x10^28)   0.7890032941268510245 
  37  50544101526286159123775820994617/(625x10^29)   0.8087056244205785459 
  38  6458679336808762545011618737341693/(78125x10^29)   0.8267109551115216057 
  39  3293500769359589784930588003763413/(390625x10^28)   0.8431361969560549849 
  40  33519397476006770622816892955319189/(390625x10^29)   0.8580965753857733279 
  41  68101871989013104864349691655490799/(78125x10^30)   0.8717039614593677422 
  42  138135263903957941276240328899531879503/(15625x10^34)   0.8840656889853308241 
  43  279776174841570667623827928185793700629/(3125x10^35)   0.8952837594930261363 
  44  565908970243105819274589689854474583919/(625x10^36)   0.9054543523889693108 
  45  228666892936369630216872051534797359443/(25x10^37)   0.9146675717454785208 
  46  36054975529202343291429654249040207702473/(390625x10^35)   0.9230073735475799882 
  47  290797383708258262753863345560109632558799/(3125x10^38)   0.9305516278664264408 
  48  2929288373226460095302724132118847017674861/(3125x10^39)   0.9373722794324672304 
  49  5897097360015813777241205577483673494626109/(625x10^40)   0.9435355776025302043 
  50  14829724264494253692571244783859722474239215237/(15625x10^42)   0.9491023529276322362 
  51  29816510081599368816476345831691507788276164587/(3125x10^43)   0.954128322611179802 
  52  299582628521801879031968833819882653723334636077/(3125x10^44)   0.9586644112697660128 
  53  601723172953395427160854315746092422549492792461/(625x10^45)   0.9627570767254326834 
  54  75503799469196254316909028388540898694196780839027/(78125x10^45)   0.9664486332057120552 
  55  15152774475381711824066695130847742737390601166961/(15625x10^45)   0.9697775664244295567 
  56  759983466143077997052562676602336355943974923595979/(78125x10^46)   0.9727788366631398362 
  57  1524194011336303865864543916024741090121240787675703/(15625x10^47)   0.9754841672552344741 
  58  1528003620098572469747040585608424677462026934794432971/(15625x10^50)   0.9779223168630863805 
  59  3062872920911427714160143540016402303785716667401174289/(3125x10^51)   0.9801193346916568684 
  60  30690587448369831810648637422738555333290988195411480447/(3125x10^52)   0.9820987983478346179 
  61  61492627154535185194682444376156870816095039389568564367/(625x10^53)   0.983882034472562963 
  62  3849563760055779018423888122998663987861595575272161210397/(390625x10^52)   0.9854883225742794286 
  63  15420860667233163144122093150097566437352582520301248342897/(15625x10^54)   0.9869350827029224412 
  64  30882438992008591800652193686632601253481233197645983870039/(3125x10^55)   0.9882380477442749376 
  65  12367642765013658147960547213936516505761769048673282264939/(125x10^56)   0.9894114212010926518 
  66  30952125667916151347652825038745285994698675525593268606920301/(3125x10^58)   0.9904680213733168431 
  67  61963713304061252906501668877187313990408810459942302936560667/(625x10^59)   0.9914194128649800464 
  68  620172516461414280878220098987189726562180164644434169796804973/(625x10^60)   0.9922760263382628493 
  69  1241309084264834707063976905774938580510294028512699832847097197/(125x10^61)   0.9930472674118677656 
  70  776360637161210011569348038755878790557990632599566471718550833161/(78125x10^61)   0.9937416155663488148 
  71  48553062201027986569649583459600376219624851865925570855685492033/(48828125x10^57)   0.9943667138770531648 
  72  1943221582712465025180055430841460742343296169092972217613506255087/(1953125x10^60)   0.9949294503487820928 
  73  486052749793625443460238141801102045762777968601067397476391159457/(48828125x10^58)   0.9954360315773449081 
  74  15560813272085758656152934738764613075693942325665813229037651394165639/(15625x10^66)   0.9958920494134885539 
  75  1245378176569287244601772318529906043642580080295812287996816015480917/(125x10^67)   0.9963025412554297956 
  76  311460013921328164004742264887135051550804965499722491506573892512303891/(3125x10^68)   0.9966720445482501247 
  77  623127903763954732975497328227737681907623668844052569558914017909271107/(625x10^69)   0.9970046460223275727 
  78  2434824282615148985102871339760643873097879704609285733228672475094255079/(244140625x10^64)   0.9973040261591650242 
  79  155870859270573193730735158341158902539786230611753571173285841714737716087/(15625x10^70)   0.9975734993316684398 
  80  1559087578167581477410242265249402465532199448684558163257815006030968506341/(15625x10^71)   0.9978160500272521455 
  81  3118857392269179984780497784963845338279540599566101325059742251607585304021/(3125x10^72)   0.9980343655261375951 
  82  1559735727146624250422692767135119883142884336181663247316287401482624374386173/(15625x10^74)   0.9982308653738395202 
  83  3120024149862584753291799134115108792006648060076625256282728729436810882101859/(3125x10^75)   0.998407727956027121 
  84  6241043215347530958786922244672573448003202475965576024866497313986687696922897/(625x10^76)   0.9985669144556049533 
  85  499355095222927602184019053985670668407797620557677957307886017554287735384793/(5x10^77)   0.9987101904458552043 
  86  1560686164608882340629043048644276246171023143788384288917639705387870129668252659/(15625x10^77)   0.998839145349684698 
  87  1560867515583257392325064973658864851726585636112786637570011269480594772737276479/(15625x10^77)   0.998955209973284731 
  88  15610307379729634441449575845792835060959470521078901563634318861732863447274356121/(15625x10^78)   0.9990596723026966042 
  89  31223552866679346922398561835991468287229206703981781552709558833568342742924416389/(3125x10^79)   0.9991536917337391014 
  90  156130986232712317800431094347137986965239208162190145774908346305129614156226444779907/(15625x10^82)   0.9992383118893588339 
  91  312285772551118314382250816660005290582544251197782844935661318930550964519013871246537/(3125x10^83)   0.9993144721635786059 
  92  3123071931617868090015533528220035903024656187906088298468417582662408894161394433196007/(3125x10^84)   0.9993830181177177887 
  93  6246529442764527549444183654063284781039499904355095745266521457615398154823411275711031/(625x10^85)   0.9994447108423244078 
  94  390429779448117663983046172038709227051591252165642876639931868328334413471488425342238931/(390625x10^84)   0.9995002353871812197 
  95  312359440109914085610780435959285776632918885643497418874958190571430128093987019686589753/(3125x10^86)   0.9995502083517250739 
  96  15618674761236805457242649217139773214183312153429255487282348831554532901699344883918950583/(15625x10^87)   0.9995951847191555492 
  97  31238614500291180054846938278735423200763473426764065223999398182713381537788580416096913751/(3125x10^88)   0.9996356640093177617 
  98  15619876497156952599857992009868641221497962270826043293811996266215125205667186851401624559641/(15625x10^90)   0.9996720958180449663 
  99  31240777650123918475441450858123526253613737113992198554375639903423969118715106504926227480959/(3125x10^91)   0.9997048848039653911 
 100   312416998493046001572329000213994444808820158829131349249531876637988573456837082185196018390217/(3125x10^92)   0.999734395177747205 

(Strings of zeros converted to powers of 10 by a separate QB program)
 
So the answers:
 

a: 27   3247709559153727376709/6250000000000000000000   0.5196335294645963802 
b: 35   479679774018898077792619889283/625000000000000000000000000000   0.7674876384302369244 
c: 51     0.954128322611179802

for those curious, the numerator and denominator, reduced to lowest terms, for p(51) are:

29816510081599368816476345831691507788276164587
31250000000000000000000000000000000000000000000 


  Posted by Charlie on 2017-05-03 14:19:51
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information