tag:blogger.com,1999:blog-4115025577315673827.post8305332686147400195..comments2020-05-20T14:21:54.596+05:30Comments on CSE Blog - quant, math, computer science puzzles: Order of cardsPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-4115025577315673827.post-89076628511748299972010-12-25T02:23:44.740+05:302010-12-25T02:23:44.740+05:30@Gangal. :P
On doing more calculations, another s...@Gangal. :P<br /><br />On doing more calculations, another sleeker representation is 29.2896825.<br /><br />We could have guessed this using the following line of thought:<br /><br />(We know that!) H(n)-ln(n) reduces monotonically to Euler Mascheroni constant (0.577)<br /><br />H(10)-ln(10) < H(5)-ln(5)<br /><br />So, H(10) < ln(2)+1+0.5+0.33+0.25+0.2<br /><br />H(10) < 2.28+ln2 < 2.98<br /><br />Also, H(10)-ln(10) > 0.577<br /><br />H(10) > 2.879<br /><br />So, we could have guessed that our answer 10*H(10) lies between 28.79 and 29.8 <br />[Not a bad estimation!]<br /><br />[Of course, you needed to know the values of ln(10) and ln(2) for this, which I happened to remember from JEE days]Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-35089910205691306032010-12-25T01:50:46.474+05:302010-12-25T01:50:46.474+05:30106,286,400 / 10!, if you may!106,286,400 / 10!, if you may!Shantanuhttps://www.blogger.com/profile/14364941861652089030noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-65671080657512786172010-12-08T10:15:30.267+05:302010-12-08T10:15:30.267+05:30@Goutham (Scrouge of God)..
Your solution is corre...@Goutham (Scrouge of God)..<br />Your solution is correct.<br /><br />Just for clarity, the solution I gave to Prateek was:<br /><br />Let the random variable Xi be the amount in dollars I get in the ith draw. <br />So, X1=10<br />X2, X3 .. etc are not independent<br /><br />X= X1+X2+X3+.. X10<br />We need to find E[X]<br /><br />Note that E[Xi]=10*P(last number is the largest if I draw i numbers from a set of n numbers) = 10*1/i<br /><br />So, E[Xi]=10/i<br />E[X1]=10<br />E[X2]=10/2<br />E[X3]=10/3<br />and so on<br /><br />By linearity of expectation,<br />E[X]=10(1+1/2+1/3+1/4..+1/10)<br /><br />Hence proved.<br />I agree with Goutham that my solution is sleeker :P. Thanks.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-49163648756247775492010-12-07T14:46:51.717+05:302010-12-07T14:46:51.717+05:30Another solution (Already seen yours, which is a l...Another solution (Already seen yours, which is a lot sleeker I must say .. but I had to prove to Prateek that it could be done this way too! :D)<br /><br />So lets say E(n) is the expected value of winnings for the same game involving n cards <br /><br />So E(1) = 10<br /><br />E(2) = 15 [10 if its 2,A, 20 if its A,2] and so on.. <br /><br />One thing to note is that once the Highest card (10) appears there is no chance of winning any more money. <br /><br />Now for E(10)<br /><br />Probability that 10 appears in the first draw = 1/10 <br />Money won = 10$<br /><br />Probability that 10 appears in the second draw = 1/10 <br />Money won = 10$ (for 2nd draw) + (Money won in first draw)<br /><br />Probability that 10 appears in the third draw = 1/10 <br />Money won = 10$ (for 3nd draw) + (Money won in first 2 draws)<br /><br />Probability that 10 appears in the fourth draw = 1/10 <br />Money won = 10$ (for 4th draw) + (Money won in first 3 draws)<br /><br />Now we have to calculate the "Money won in the first i draws", This can be mapped back to the original game.<br />For example, lets look at the last case, That 10 appears in the 4th draw, so any 3 cards can appear in the first 3<br />draws, these 3 cards can be mapped to A,2,3 and Expected Value of winnings is just E(3) and similarly for all cases<br /><br />so now<br /><br />E(10) = 1/10*(10) + 1/10*(10 + E(1)) + 1/10*(10 + E(2)) + .... + 1/10*(10 + E(9))<br /><br />For a general n<br /><br />n*E(n) = 10 + (10 + E(1)) + ... + (10 + E(n-1))<br />n+1*E(n+1) = 10 + (10 + E(1)) + ... + (10 + E(n-1)) + (10 + E(n))<br /><br />=> n+1(E(n) - E(n+1)) = 10 <br /><br />=> E(n+1) - E(n) = 10/(n+1) <br /><br />=> E(10) - E(1) = 10/2 + 10/3 + 10/4 + .. + 10/10<br /><br />=> E(10) = 10(1 + 1/2 + 1/3 + ... + 1/10)Gouthamhttps://www.blogger.com/profile/07692608143797361326noreply@blogger.com