title: Algorithm Design- Identify single bottle in wine cellar with fewest testers
body: <p>This is for extra credit in an algorithms class.  The problem states</p>
  
  <blockquote>
    <p>A king has a wine cellar of N bottles, and a single bottle has been poisoned.<br>
        The poison takes approximately a month to work.  The king wants the exact bottle
        identified using the fewest testers possible within a months time.</p>
  </blockquote>
  
  <p>My solution is</p>
  
  <ul>
  <li><p>Split up the <code>N</code> bottles into <code>M</code> lots and use ``M testers</p>
  
  <ul>
  <li><p>The first tester tastes both the first and last lot</p></li>
  <li><p>The second tester tastes both the first and second lots.</p></li>
  <li><p>The third tester tastes both the second and third lots.</p></li>
  <li><p>Continue on for M lots, with testers overlapping lots.</p></li>
  </ul></li>
  <li><p>When the two testers that tasted the tainted wine become ill, the lot has been identified.  The <code>M-2</code> testers left each taste one bottle from the tainted lot, and the third tester that becomes ill identifies the tainted bottle.</p></li>
  </ul>
  
  <p>However, this algorithm requires double the time allotted to work: one month to identify the tainted lot, and a second month to identify the tainted bottle.  Is there a more efficient algorithm?</p>