tag:blogger.com,1999:blog-4115025577315673827.post1589264224604978087..comments2020-02-26T09:38:33.024+05:30Comments on CSE Blog - quant, math, computer science puzzles: Need for NeedlesPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-4115025577315673827.post-14692711832704600752013-03-25T23:27:00.325+05:302013-03-25T23:27:00.325+05:30Minor correction: x_i is the displacement (+ve or ...Minor correction:<br />x_i is the displacement (+ve or -ve) from the right end of the i-th needle to the left end of the (i+1)th needle, NOT (i-1)th NEEDLE (i=2,3,4,...,n)Arnabhttps://www.blogger.com/profile/13734216328461677608noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-24772155974978071532013-03-25T02:47:57.728+05:302013-03-25T02:47:57.728+05:30I solved this problem using some intuition, not su...I solved this problem using some intuition, not sure if it is entirely rigorous...<br />Consider x_1,x_2,...,x_n+1<br />x_1 is the distance from the left end of the stick to the left end of the first needle<br />x_n+1 is the distance from the right end of the last needle to the right end of the stick<br />x_i is the displacement (+ve or -ve) from the right end of the i-th needle to the left end of the (i-1)th needle (i=2,3,4,...,n)<br />Now, for any arrangement,<br />x_1 + x_2 +...+ x_n+1 = 1-nh<br />0&lt;= x_1,x_n+1 &lt;=1-h<br />For the sample space: -h &lt;= x_2,x_3,...,x_n &lt;= 1-2h<br />For the valid cases: 0 &lt;= x_2,x_3,...,x_n &lt;= 1-nh<br />Define y_i = x_i + h<br /><br />Sample space is the solution space for:<br />x_1 + y_2 + y_3 +...+ y_n + x_n+1 = 1-h<br />0 &lt;= x_1,y_2,y_3,...,y_n,x_n+1 &lt;= 1-h<br /><br />Valid cases is the solution space for:<br />x_1 + x_2 +... + x_n+1 = 1-nh<br />0 &lt;= x_1,x_2,...,x_n+1 &lt;= 1-nh<br /><br />Suppose we have a k dimensional hyper-space. Then the area of the (k-1) dimension hyper-plane formed by using k distinct unit vectors, each scaled by a factor &#39;a&#39; is equal to c_k*a^(k-1), where c_k is some constant for a k dimensions [This is based on intuition. It would be great if someone could provide a formal proof for the same].<br /><br />The solution space for the sample space and the valid space is a n-dimensional hyper-plane on a (n+1) dimension hyper-space. For the sample space, the unit vectors are scaled by a factor of (1-h) while for the valid space, the scaling factor is (1-nh).<br /><br />Using this, the probability comes out to be [(1-nh)/(1-h)]^nArnabhttps://www.blogger.com/profile/13734216328461677608noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-33978804494172898702011-05-26T16:39:29.559+05:302011-05-26T16:39:29.559+05:30Dropping the needles so that they all fall within ...Dropping the needles so that they all fall within the stick is equivalent to randomly picking n numbers (the left endpoints) each uniformly and independently drawn from [0,1-h]. Under this interpretation, the volume of the sample space is (1-h)^n. The volume of the region where the first needle is to the left of the second is to the left of the third ... is to the left of the nth is given by n-dimensional integral as in <br /><br /><a href="http://www.quantnet.com/cgi-bin/mathtex.cgi?%5Cint_0%5E%7B1-nh%7D%5Cint_%7Bx_1+h%7D%5E%7B1-%28n-1%29h%7D%5Ccdots%5Cint_%7Bx_%7Bn-1%7D+h%7D%5E%7B1-h%7D1dx_ndx_%7Bn-1%7D%5Ccdots%20dx_1" rel="nofollow"> Equation Image </a><br />Solving this gives [(1-nh)/(1-h)]^nPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-14429342192490862652011-05-22T18:19:51.819+05:302011-05-22T18:19:51.819+05:30We have n! permutations for arrangment of sticks p...We have n! permutations for arrangment of sticks properly. Lets integrate from length i&#39;th stick leaves for rest n-i sticks to be put. (Ai)<br />Which gives us :<br />Prob. = (l-h)^n * IGR[(n-1)h to l-h] of (IGR[(n-2)h to Ai] of (IGR.... (IGR[h to An-2] dAn-1 dAn-2.. dA1.<br />Substituting Bi = Ai - (n-i)h,<br />It solves to 1/n! * ((l-nh)/(l-h))^n<br />Multiplying by n! for total number of ways to arrange sticks,<br />we get ((l-nh)/(l-h))^nStainless...https://www.blogger.com/profile/13692804410410651536noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-76088861253729968262011-05-14T09:58:13.910+05:302011-05-14T09:58:13.910+05:30ans = 0 if (1-nh) &lt;=0 = [(1-nh)/(1-h)]^n o...ans = 0 if (1-nh) &lt;=0<br /> = [(1-nh)/(1-h)]^n otherwise<br /><br />simple n dimentional integration. However cant think of an elegant solutionsidhttps://www.blogger.com/profile/04179126136399818676noreply@blogger.com