tag:blogger.com,1999:blog-4115025577315673827.post6344463137714046713..comments2020-02-26T09:38:33.024+05:30Comments on CSE Blog - quant, math, computer science puzzles: Bad BarCodePratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-4115025577315673827.post-27260295474417117182011-05-30T22:28:17.409+05:302011-05-30T22:28:17.409+05:30@Florian,
Possible reasons:
1) You need to wait. T...@Florian,<br />Possible reasons:<br />1) You need to wait. They update it in 3-4 days.<br />2) Your answer is correct but your solution might be wrong.<br /><br />I have been an IBM Research Ponder This Fan since last 18 months now and I don`t think they have made a mistake even once. <br /><br />Cheers!Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-35559757950950096762011-05-30T22:01:30.782+05:302011-05-30T22:01:30.782+05:30I found the same thing: 2^(n+1) - (n+1).
A bad b...I found the same thing: 2^(n+1) - (n+1).<br /><br />A bad bar appears every 2^(n+1) bits, and it is (n+1) bits long on average. For n=20, it gives 2097131.<br /><br />But I submitted that answer and they did not credit me in the solver's list. So they must have a different interpretation of the problem.Florianhttps://www.blogger.com/profile/00144691058227091333noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-54186330818386540782011-05-30T21:57:53.945+05:302011-05-30T21:57:53.945+05:30Yes, I also find 2^(n+1) - (n+1).
For n=20, that i...Yes, I also find 2^(n+1) - (n+1).<br />For n=20, that is 2097131.<br />I submitted that solution. They didn't put my name on the solver's list. So they must have a different interpretation of the problem.Florianhttps://www.blogger.com/profile/00144691058227091333noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-13080376262053402462011-05-30T00:26:44.328+05:302011-05-30T00:26:44.328+05:30Not a problem. :)Not a problem. :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-29104515694484364172011-05-29T23:04:29.709+05:302011-05-29T23:04:29.709+05:30thanx pratik, agree with u.
i misread the problem...thanx pratik, agree with u.<br /><br />i misread the problem. in the problem, actually only black bars are bad, i thought white bars can also be bad.cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-88692322936193089742011-05-29T22:45:21.152+05:302011-05-29T22:45:21.152+05:30My solution generalized for length of black bar = ...My solution generalized for length of black bar = n (here n = 20) is as follows:<br /><br />x/(2^n) = i from 1 to n (i/2^i)<br />x/(2^n) = 2 - (n+2)/2^n<br />x = 2^(n+1) - (n+2)<br /><br />Answer = x+1 = 2^(n+1) - (n+1)<br /><br />For n = 1,<br /><br />Expected gap between two black bars = Expected number of whites between two blacks given that there is atleast one white is definitely greater than 1.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-25679972639482440572011-05-29T22:27:23.681+05:302011-05-29T22:27:23.681+05:30assume wlog that after a bad bar, the next bar sta...assume wlog that after a bad bar, the next bar starts with a 1.<br /><br />look at next n-1 bits for first occurrence of 0.<br /><br />following cases arise:<br /><br />10: probab= 1/2<br />110: probab=1/2^2<br />.<br />.<br />1^(n-1)0: probab=1/2^(n-1)<br />1^n: probab=1/2^(n-1)<br /><br /><br />if y is the required answer,<br />we get recurrence euqation,<br /><br />y=1/2(1+y)+...1/2^(n-1)[n-1+y].<br /><br />above simplifies to y= 2^n-(n+1).<br /><br />if n=20, y= 2^20-21cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86179041847151349222011-05-29T22:10:23.817+05:302011-05-29T22:10:23.817+05:30@pratik, if n is the limit for bad bar, ur soluti...@pratik, if n is the limit for bad bar, ur solution gives 2^(n+1)-(n+1).<br /><br />if we put n=1, then we get 2^2-2=2, but we should get 0. <br /><br />if we put n=2, ur solution gives 2^3-3=5, but we should get 1.<br /><br />answer i got is 2^n-(n+1) based on ur solution only.cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-42981569100498328252011-05-29T14:38:22.947+05:302011-05-29T14:38:22.947+05:30Solution I sent to IBM:
Answer: (2^21) - 21
Let t...Solution I sent to IBM:<br />Answer: (2^21) - 21<br /><br />Let the expected number of bits in the bars that are between two<br />adjacent bad bars be x+1.<br /><br />Consider the state that I have just got a bad bar and a white bit. The<br /><br />expected number of bits to get the next bad bar is x.<br /><br />E(next bad bar)=x<br />This can be seen in two cases.<br />E(next bad bar | first new bit is white i.e. 0) = x+1<br />E(next bad bar | first 2 new bits are 10) = x+2<br />E(next bad bar | first 3 new bits are 110) = x+3<br />E(next bad bar | first 4 new bits are 1110) = x+4<br />E(next bad bar | first 5 new bits are 11110) = x+5<br />E(next bad bar | first 6 new bits are 111110) = x+6<br />and so on upto<br />E(next bad bar | first 20 new bits are [{1}^19]{0}) = x+20<br /><br />One case is left<br />E(next bad bar | first 20 new bits are [{1}^20]) = 0<br /><br />Hence,<br />x= (1/2)^1*(x+1) + (1/2)^2*(x+2) + (1/2)^3*(x+3) + (1/2)^4*(x+4)..<br />+(1/2)^20*(x+20)<br />Rearranging terms, we get<br />x/(2^20) = 1/2 + 2/4 + 3/8 + 4/16 + 5/32 .. 20/(2^20)<br />Calculating RHS,<br />2*(1/2+1/4+1/8+1/16+... 1/2^20 - 20/2^21) = 2*(1-22/2^21)<br /><br />x = (2^21)-22<br />Answer = x+1 = (2^21)-21Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-69410624542828822192011-05-29T14:38:06.007+05:302011-05-29T14:38:06.007+05:30@Pritish.. I too did not try to evaluate your expr...@Pritish.. I too did not try to evaluate your expression. Although the solution looks correct, we cannot be sure until the numbers match.<br /><br />I am sure this is not true in research, but for fun problem solving, if you are not getting a simple expression, then probably you are not doing it the right way :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-56952440551064670472011-05-26T05:47:51.156+05:302011-05-26T05:47:51.156+05:30Does blogspot support LaTeX? I couldn't find i...Does blogspot support LaTeX? I couldn't find it.<br />Use http://www.codecogs.com/latex/eqneditor.php to view the math part.<br /><br />Constants assumed :<br />n = Length of bar code.<br />b = Minimum length of a bad bar.<br /><br />Suppose two consecutive bars are as follows :<br />Bar_1 starts at <i>i</i>, ends at <i>j</i>,<br />Bar_2 starts at <i>k</i>, ends at <i>l</i>.<br /><br />Thus,<br />size of gap in between = <i>k-j+1</i><br />Combined length of these two bars combined with the gap in between = <i>l-i+1</i> = <i>y</i> (say)<br />number of bar codes in which this particular bad bar configuration occurs<br /> = <i>2^{n-y-2}</i> -- if y < n and the configuration is not at the ends.<br /> = <i>2^{n-y-1}</i> -- if y < n and the configuration is one of the ends.<br /> = 1 -- if y = n<br /><br />For a combined length of <i>y</i>, the number of white blocks in between can be anything from 1 to y-2b (let y-2b = z),<br />then the expected value of the number of white space in between<br />= <i>\frac{\sum_{k=1}^{z} (z-k+1)*k}{\sum_{k=1}^{z} (z-k+1)}</i><br />= <i>\frac{z+2}{3}</i><br /><br />The number of two consecutive bars with combined length (with the gap in between) of y<br /> = 2*2^{n-y-1} + (n-y-1)*2^{n-y-2} = (n-y+3)*2^{n-y-2} -- if n > y<br /> = 1 -- if n = y<br /><br />Thus, the expected value of the number of gaps<br />= \frac{[(n-2b+2)/3] + \sum_{y=2b+1}^{n-1} [(y-2b+2)/3]*[(n-y+3)*2^{n-y-2}]}{1 + \sum_{y=2b+1}^{n-1} [(n-y+3)*2^{n-y-2}]}<br /><br />Now, I am too lazy to evaluate this complicated thing, but that should be fairly straightforward, but nevertheless pretty tedious. :(Pritishhttps://www.blogger.com/profile/04147166709938295125noreply@blogger.com