title: Finding position of missing bits in stream
body: <p>not sure if this is the right channel... Please advise :-) </p>
  
  <ol>
  <li>You generate a stream of n bits (1 &amp;  0). 
  
  <ol start="2">
  <li>I remove k bits and broadcast the stream of n-k bits. </li>
  <li>You start listening to my stream at some point in time (i.e. you probably missed the beginning of the stream).  </li>
  </ol></li>
  </ol>
  
  <p>Task:
  Tell me <em>the original position of the bits that I have removed from your stream</em>, for the part that you received. </p>
  
  <p>Additional information: </p>
  
  <ol>
  <li>Your stream must contain at least 1000 bits, but you can design it any way you like, and you may store it in memory. </li>
  <li>I will remove no more than 3 consecutive bits. </li>
  <li>I will remove no more than 10 bits from the original stream.</li>
  <li>I will broadcast the stream exactly once - no looping etc. </li>
  </ol>
  
  <p>Is this solvable? Maybe with checksums, integrated position encoding...? 
  How many bits of my stream do you require to give your answer with absolute certainty?</p>
  
  <p>I found this: <a href="https://cs.stackexchange.com/questions/2079/determine-missing-number-in-data-stream">https://cs.stackexchange.com/questions/2079/determine-missing-number-in-data-stream</a> but there the numbers that may be removed are unique. </p>