Ponder This Challenge - May 2011 - Distance between bad bars

Ponder This Challenge:

A barcode is composed of a series of variable-width white and black bars.

One of the important features of the barcode is that no bar be too wide; otherwise, the reader might get out of synchronization. Suppose we use the following barcode system, where we take a completely random sequence of bits and use it to build the bars. For example, the 7-bit-long sequence 0111001 will generate four bars of varying lengths: white(1), black(3), white(2), black(1). Such a system will generate, every once in a while, bars that are too wide. Let's call any black bar whose width is 20 bits or more a "bad bar".

What is the expected number of bits in the bars that are between two adjacent bad bars?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  The probability of 20 consecutive bits being black is 2-20, therefore the expected distance between two occurrences is 220.

  There is a 0.5 probability of getting a black bit immediately after the 20 black bits, which should not be counted since it is the same bad bar.

  Therefore the expected distance is 221.

  Stephen Morris sent us a relevant link to this factor 2 "paradox": http://mathfactor.uark.edu/2009/07/morris-world-of-britain-2-proof-and-paradox (link resides outside of ibm.com).

  Since we are seeking the distance between consecutive black bars, we should subtract the length of the bad bar, whose expected value is 21.

  So the answer is 221-21 = 2,097,131.

  This month we didn't ask an IBM-related bonus question, but we do have a bonus answer: IBM invented the bar code.

Solvers

• John T. Robinson (04/30/2011 01:32 AM EDT)
• Dan Dima (04/30/2011 07:21 AM EDT)
• Austin Shapiro (04/30/2011 08:07 PM EDT)
• Jonathan Campbell (05/01/2011 12:41 AM EDT)
• David Friedman (05/01/2011 01:39 AM EDT)
• William Heller (05/01/2011 04:52 AM EDT)
• Hubert Kahlert (05/01/2011 07:21 AM EDT)
• Daniel Bitin (05/01/2011 06:16 PM EDT)
• Jamie Niemasik (05/01/2011 06:49 PM EDT)
• Jan Fricke (05/01/2011 07:23 PM EDT)
• Matt Dobrin (05/02/2011 12:18 AM EDT)
• Joshua Gunderson (05/02/2011 03:43 AM EDT)
• Leif Jensen (05/02/2011 12:54 PM EDT)
• Mark Perkins (05/02/2011 04:31 PM EDT)
• Shlomi Hod & Ofir Reich (05/02/2011 08:59 PM EDT)
• Rogerio Ponce da Silva (05/03/2011 10:07 AM EDT)
• Joe Riel (05/03/2011 12:14 PM EDT)
• Ariel Flat (05/03/2011 01:40 PM EDT)
• John Tromp (05/03/2011 02:22 PM EDT)
• Shilei Zang (05/03/2011 02:51 PM EDT)
• Arthur Breitman (05/03/2011 03:30 PM EDT)
• Gale Greenlee (05/03/2011 04:32 PM EDT)
• Harald van Dijk (05/03/2011 05:07 PM EDT)
• Álvaro Begué (05/03/2011 05:19 PM EDT)
• Nick McGrath (05/04/2011 12:41 PM EDT)
• Joseph DeVincentis (05/04/2011 01:56 PM EDT)
• Lu Wang (05/04/2011 02:27 PM EDT)
• Siyu Yang (05/04/2011 02:59 PM EDT)
• Matthew Paterson (05/04/2011 03:53 PM EDT)
• Joshua Small (05/04/2011 10:51 PM EDT)
• Donald T. Dodson (05/05/2011 04:01 PM EDT)
• Nemo Publius (05/05/2011 04:19 PM EDT)
• Guoxin Zhang (05/06/2011 01:14 PM EDT)
• Adam and Lael Daire (05/06/2011 04:12 PM EDT)
• Mark Mixer (05/08/2011 03:45 PM EDT)
• Are Hjørungnes (05/08/2011 04:09 AM EDT)
• Liubing Yu (05/08/2011 05:01 PM EDT)
• Stephen Morris (05/08/2011 06:10 PM EDT)
• J Noble Pendergrass (05/09/2011 04:35 PM EDT)
• Or Zuk (05/10/2011 04:53 PM EDT)
• James Dow Allen (05/10/2011 05:51 PM EDT)
• John Snyder (05/12/2011 11:28 AM EDT)
• Kipp Johnson (05/12/2011 11:52 AM EDT)
• & Nick Vigo (05/12/2011 11:52 AM EDT)
• Thijmen Krebs (05/12/2011 01:00 PM EDT)
• Geoff Kallweit (05/13/2011 04:05 PM EDT)
• Motty Porat (05/13/2011 06:05 PM EDT)
• John Black (05/13/2011 09:17 PM EDT)
• Jeff Steele (05/15/2011 09:57 AM EDT)
• Akshatha Nagesh & Sumanth Jagannath (05/15/2011 04:33 PM EDT)
• Armin Krauss (05/16/2011 05:20 AM EDT)
• Rino Raj (05/16/2011 09:29 AM EDT)
• Ron Yu (05/16/2011 08:44 PM EDT)
• John G. Fletcher (05/17/2011 01:26 AM EDT)
• Ariel Landau (05/17/2011 03:49 PM EDT)
• Martin Thiim (05/18/2011 10:15 AM EDT)
• Christian Pape (05/18/2011 01:05 PM EDT)
• Piet Orye (05/18/2011 02:33 PM EDT)
• Joaquim Neves Carrapa (05/19/2011 11:50 AM EDT)
• Hamidreza Bidar (05/19/2011 03:00 PM EDT)
• Jon Evans (05/20/2011 03:44 PM EDT)
• Joshua Katz (05/20/2011 04:43 PM EDT)
• Andrea Andenna (05/22/2011 06:50 AM EDT)
• Aliaksei Sanko (05/24/2011 08:40 AM EDT)
• Hendrik Nigul (05/24/2011 08:45 AM EDT)
• Jon Namnath (05/24/2011 07:15 PM EDT)
• Pratik Poddar (05/26/2011 01:03 AM EDT)
• Clive Tong (05/26/2011 07:56 AM EDT)
• Raúl Mora Pastor (05/26/2011 12:00 AM EDT)
• Karthik Kalyanam (05/26/2011 04:15 PM EDT)
• Florian Fischer (05/27/2011 01:12 PM EDT)
• Vignesh Sethuraman (05/29/2011 02:13 PM EDT)
• Ehud Schreiber (05/30/2011 05:04 AM EDT)
• Vivek Nema (05/30/2011 11:21 AM EDT)
• Bi Suzhi (05/30/2011 11:37 AM EDT)
• Rafa Casado (05/30/2011 03:38 PM EDT)
• Harald Bögeholz (05/30/2011 08:41 PM EDT)