tag:blogger.com,1999:blog-4115025577315673827.post4596564614575784793..comments2019-10-08T12:02:40.465+05:30Comments on CSE Blog - quant, math, computer science puzzles: Polya's Urn ProblemUnknownnoreply@blogger.comBlogger26125tag:blogger.com,1999:blog-4115025577315673827.post-82541874398221635952014-06-22T19:36:59.582+05:302014-06-22T19:36:59.582+05:30Represent 10 in base 10,9,8,7,6,5,4,3,2,1Represent 10 in base 10,9,8,7,6,5,4,3,2,1Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-14859309945740302732014-01-21T20:41:39.482+05:302014-01-21T20:41:39.482+05:30what is the explanation for next term in 10-11-12-...what is the explanation for next term in 10-11-12-13-14-20-22-101-?varun sethhttps://www.blogger.com/profile/12213627012541433525noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-62607047837436674202014-01-21T20:40:25.237+05:302014-01-21T20:40:25.237+05:30Please tell me the explanation for this one next t...Please tell me the explanation for this one next term in sequence 10-11-12-13-14-20-22-101-?varun sethhttps://www.blogger.com/profile/12213627012541433525noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-3338883966438620822013-08-02T22:09:16.857+05:302013-08-02T22:09:16.857+05:30For Polya's Urn puzzle, can't we do it the...For Polya's Urn puzzle, can't we do it the following way :<br /><br />Let E(n-1) be the expected number of balls in smaller urn.<br /><br />E(n) = E(n-1)/n-1 * (1 + E(n-1)) + (1 - E(n-1)/n-1) * E(n-1);<br /><br />On solving -> E(n-1) = n/n-1 * E(n-1)<br />Since E(3) = 1, therefore E(n) = n/3.Anurag Vermahttps://www.blogger.com/profile/07803458076601856186noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-58389905078509596672011-10-15T23:53:19.050+05:302011-10-15T23:53:19.050+05:30http://connect2ppl.wordpress.com/2009/12/08/calcul...http://connect2ppl.wordpress.com/2009/12/08/calculating-probability-via-generating-functions/<br /><br />Is it not an overkill?<br /><br />I mean if you let K_{n} = (2n+1)*P{n}<br />And then it becomes<br /><br />K_{n} = K_{n-1} + 1<br /><br />Btw, generating functions are still the only way I know of for solving difference equations with more than one parameters. Is there any better way for solving something like<br /> P(a,b) = k_{1} * P(a-1,b) + k_{2} * P(a-1, b-3)<br />where k_{1}, k_{2} are constants.Rohit Sarafhttps://www.blogger.com/profile/12284434839314009959noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-66939635209895564672009-12-17T21:18:17.829+05:302009-12-17T21:18:17.829+05:30Just so that people understand things:
We are tal...Just so that people understand things:<br /><br />We are talking about the Poyla's Urn problem only <a href="http://pratikpoddarcse.blogspot.com/2009/11/polyas-urn-problem.html" rel="nofollow">http://pratikpoddarcse.blogspot.com/2009/11/polyas-urn-problem.html</a><br /><br />I wrote a comment on gurmeet's blog <a href="http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-polyas-urn-problem/" rel="nofollow">http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-polyas-urn-problem/ </a><br /><br />@Giridhar.. Thanx for that.. great argument..Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-9451199212413079402009-12-17T19:47:24.427+05:302009-12-17T19:47:24.427+05:30In response to your comment on http://gurmeetsingh...In response to your comment on http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-polyas-urn-problem/ <br /><br />It is difficult to refute ur argument, hence let us take help of math ( in accordance with diophantine who said " equations are more intelligent than their creators " ) --<br />Let us represent the outcome of n-2 throws with sequence of length n-2 containing 1& 2's ( corresponding to the bin they land into ).<br />Let P(x, n-x) stand for the probability of having x balls in the first bin and n-x balls in the second bin.<br />Note that the probability of individual sample points containing x 1's and (n-x) 2's is each equal to [(x-1)!(n-x-1)!]/(n-1)!.<br />The number of sample points with x 1's and (n-x) 2's is equal to (n-2)!/[(x-1)!(n-x-1)!]<br />Multiplying these two results we get<br />P(x, n-x) = 1/(n-1).<br /><br />In retrospect we see sequences with high probability are less in number and sequences with less probability are high in number, leveling out the things finally.<br /><br />Thanks,<br />Giridhar.Giridharhttps://www.blogger.com/profile/06086734346209959881noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-10563906395415224622009-12-16T23:15:06.186+05:302009-12-16T23:15:06.186+05:30No math question can be boring :P
Not so difficul...No math question can be boring :P<br /><br />Not so difficult question. I could come up with the answer n/(2n+1) using induction.<br /><br />But awesome solution using probability-generating function. Never knew that something like that exists. Thanks a lot.<br /><br />Solution to the problem at <a href="http://connect2ppl.wordpress.com/2009/12/08/calculating-probability-via-generating-functions/" rel="nofollow">http://connect2ppl.wordpress.com/2009/12/08/calculating-probability-via-generating-functions/</a>Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-52137527168658017372009-12-16T18:14:26.405+05:302009-12-16T18:14:26.405+05:30Thanks Pratik.
Here is one question :
You have co...Thanks Pratik.<br /><br />Here is one question :<br />You have coins C_1, C_2, . . . , C_n . For each k, coin C_k is biased so that, when tossed, it has probability 1/(2k+1) of falling heads. If the n coins are tossed, what is the probability that number of heads is odd? Express the answer as a rational function of n ? ( Boring Question ?? )<br /><br />It is easy to guess and prove using Mathematical Induction.<br />You can find one non-Inductive solution <br />@ http://connect2ppl.wordpress.com/Giridharhttps://www.blogger.com/profile/06086734346209959881noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55560404812046789432009-12-16T11:56:35.637+05:302009-12-16T11:56:35.637+05:30@gridhar..
Thanx..
The question asked by you is re...@gridhar..<br />Thanx..<br />The question asked by you is really open ended.. :P<br /><br />Many "good" probability questions are solved by symmetries. You might want to read about the major probability paradoxes. <a href="http://en.wikipedia.org/wiki/Category:Probability_theory_paradoxes" rel="nofollow">http://en.wikipedia.org/wiki/Category:Probability_theory_paradoxes</a><br /><br />Of course, the argument given for the 300th problem was really involved and not trivial. I don't know if there are problems in which similar argument gives a solution.<br /><br />I don't think I have helped you. Sorry.<br /><br />You can post some pointers if you find. You can also post interesting problems.<br /><br />For the wordpress thing, the work is on. Will be up in a few days. Thanx.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-37683312229404614062009-12-16T11:05:03.184+05:302009-12-16T11:05:03.184+05:30Impressed with your solution for 300 people theate...Impressed with your solution for 300 people theater problem. Specifically with the use of symmetry in discerning that probability should be 1/2.<br />Having an eye on symmetry reduces work that we need to do, Can you give me any pointers for developing intuition for symmetry. I know i am asking an open ended question, but any help will be appreciated.<br />Thanks,<br />Giridhar.<br /><br />PS : Wordpress.com has LATEX Support. Many are converting from blogger.com especially for this reason. It will make life easier posting math related things.Giridharhttps://www.blogger.com/profile/06086734346209959881noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-41811567618283744442009-11-17T01:25:52.755+05:302009-11-17T01:25:52.755+05:30To be exact, let the speed be w/k. Let the radius ...To be exact, let the speed be w/k. Let the radius at which duck moves be r.<br /><br />2pi*r*k > 2pi*1<br />So, rk > 1<br /><br />Now, (1-r)*k < pi<br />Keeping rk = 1<br />k = pi+1<br />So, the minimum speed is w/(4.14) <br />:)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-68040568140460661042009-11-17T01:22:04.943+05:302009-11-17T01:22:04.943+05:30w/4 :)
This is a real difficult one. But (being h...w/4 :)<br /><br />This is a real difficult one. But (being honest), I solved this problem 3-4 years back.<br /><br />The solution is interesting indeed.<br /><br />Duck moves in a circle of radius 1/4. Here 2*pi*1/4.<br />Since here the duck would complete the circle as fast as the wolf, duck can get "diametrically" opposite to the wolf. And after that, duck has to cover distance 3/4 while wolf has to cover pi*1 which he will not be able to do. So, a speed just greater than w/4 would work. :)<br /><br />Thanx for the interesting puzzles :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-87845800928869190792009-11-17T01:09:32.028+05:302009-11-17T01:09:32.028+05:30very nice :)
last one for now...
there's a d...very nice :)<br /><br />last one for now...<br /><br />there's a duck swimming in a circular lake with a wolf at the edge. wolf won't enter water. duck in water is slower than wolf on land. duck on land is faster than the wolf on land. given the lake diameter 'd' and wolf speed 'w', what is the minimum speed of the duck in water so that he can escape? what should be his escape strategy?Ramhttps://www.blogger.com/profile/09757925157716852610noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-57374586955200321052009-11-17T00:00:27.992+05:302009-11-17T00:00:27.992+05:30Thanx for that correction..
Solution to the woods...Thanx for that correction..<br /><br />Solution to the woods problem:<br />Since each person consumed 8/3 woods. A gave 5-8/3 = 7/3 woods to C and B gave 3-8/3 = 1/3 woods to C.<br />So, Out of the 8 dollars, A gets 7 and B gets 1 :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-17653851275391235022009-11-16T23:55:15.892+05:302009-11-16T23:55:15.892+05:30very impressive. just a nitpick: it should be '...very impressive. just a nitpick: it should be 'since there is no pref what so ever to EITHER OF THESE 2 SEATS'. other seats do have preferences from their respective assigned persons. only these two don't (so far).<br /><br />here's another:<br />A. B & C live together and share everything equally. one day A brings home 5 logs of wood, B brings 3 logs and C brings none. then they use the wood to cook together and share the food. since C did not bring any wood, he gives $8 instead. how much to A and how much to B?Ramhttps://www.blogger.com/profile/09757925157716852610noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-68200012290213054642009-11-16T23:36:18.900+05:302009-11-16T23:36:18.900+05:30Induction of course does it..
The other solution ...Induction of course does it..<br /><br />The other solution is as follows:<br /><br />Observe that when the 300th passenger finally boards, the seat remaining would be either the one assigned to him or the one assigned to the first passenger. Every other seat has either been taken by the rightful owner or by someone who reached there first. Since there is no pref what so ever to any seat, the prob is 1/2.<br />:)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-8732574377526708702009-11-16T23:29:44.116+05:302009-11-16T23:29:44.116+05:30perfect answer, but tell me your solution (other t...perfect answer, but tell me your solution (other than induction).Ramhttps://www.blogger.com/profile/09757925157716852610noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-47493819680473514872009-11-16T23:26:20.209+05:302009-11-16T23:26:20.209+05:30The answer is 1/2 for any number of people :)The answer is 1/2 for any number of people :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-35895348023498903182009-11-16T23:17:25.039+05:302009-11-16T23:17:25.039+05:30Good one! Here's another:
300 people waiting ...Good one! Here's another:<br /><br />300 people waiting to enter a movie theatre in the order of their seat number (their seat numbers are from 1 to 300). first guy in line ignores seat number and just sits randomly on some seat. everyone else sits in their assigned number if available, and some random seat if not. what is the prob that the 300th guy gets to sit in his own seat?Ramhttps://www.blogger.com/profile/09757925157716852610noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-10662981051647315622009-11-16T23:08:10.082+05:302009-11-16T23:08:10.082+05:30Thanx Ram...
thats an easy one.. :)
next is 1010 ...Thanx Ram...<br /><br />thats an easy one.. :)<br />next is 1010 and then is 1111111111 :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-45964124926159396592009-11-16T22:50:00.772+05:302009-11-16T22:50:00.772+05:30i didn't notice you already had it - my bad. i...i didn't notice you already had it - my bad. its one of my favorites.<br /><br />here's another:<br />10-11-12-13-14-20-22-101-?Ramhttps://www.blogger.com/profile/09757925157716852610noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-53341761162915755042009-11-14T16:25:05.805+05:302009-11-14T16:25:05.805+05:30@Ram .. I posted this puzzle a few days back!!
11...@Ram .. I posted this puzzle a few days back!!<br /><br />11 women can identify the pin... Except the last one, everyone can.. Last one could tell the parity of white pins ahead of her... Others can then find their pin.. :)<br />Reference: <a href="http://pratikpoddarcse.blogspot.com/2009/08/cap-puzzle.html" rel="nofollow">http://pratikpoddarcse.blogspot.com/2009/08/cap-puzzle.html</a> :)<br />Thanx.. Gimme more.. ;)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-64488986621666448142009-11-14T15:28:39.624+05:302009-11-14T15:28:39.624+05:30here's one for you.
12 chinese women in a str...here's one for you.<br /><br />12 chinese women in a straight line one behind the other. someone comes and places a pin in the hair of each woman in the line. the pin can either be black or white, with equal possibility.the 12th woman in the line can see the pins of all the other 11 women. the 11th in the line can see the pins of the 10 women in front of her, and so on such that the first woman in the line can see noone's pin. starting from the 12th woman, each woman has to call out the color of her own pin (everyone else can hear). what strategy can they follow to maximize the number of correctly called out pin colors? what is the minimum number of correct pins guaranteed by such a strategy?<br /><br />other than calling out 'black' or 'white' no other form of communication is allowed. no pauses, intonations, etc. can be used to convey information.Ramhttps://www.blogger.com/profile/09757925157716852610noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-28445138777749799942009-11-14T09:15:49.563+05:302009-11-14T09:15:49.563+05:30Thanx Ram...
Will try that from the next set :)Thanx Ram...<br />Will try that from the next set :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.com