- Number the rats 1, 2, 4, 8, 16, 32, 64, 128, 256, and 512. Notice that they are numbered after significant bits.
- Number the bottles from 1 to 1000 using binary.
- For each bottle:
- Inspect the binary number assigned to it
- For each bit of the binary number, starting from the least significant bit:
- If it is 1, then have the rat with the corresponding significant bit taste it
- For example, if the LSB is 1, then have bat #1 taste it; if the second LSB is 1, have bat #2, taste it; if the third LSB is 1, have bat #4 taste it.
Claim: this algorithm can discern precisely which bottle was poisoned.
Proof: since it is known that exactly one bottle is poisoned, it does not matter if the binary encoding of two bottles share a bit or more.
Great -- a classic algorithmic logic puzzle!
ReplyDelete