Puzzles
Binary & Bit Logic
These puzzles reward thinking in terms of bits: yes-or-no answers, binary codes, and information that either splits a problem in half or is entirely canceled out. The same handful of ideas here map directly onto real algorithms, from binary search to XOR tricks used in low-level programming.
1. 1000 Bottles, One Poisoned
A king has 1000 identical bottles of wine, and exactly one is poisoned. The poison is undetectable except that it kills a taster within 24 hours. The king has condemned prisoners to use as tasters and only 24 hours before his banquet begins.
Rules
- One dose can mix any bottles
- Only one round of testing
- Results arrive after 24 hours
Your task — Find the fewest tasters needed to guarantee identifying the poisoned bottle among all 1000.
Difficulty — Hard
Hint 1 — Same idea, bigger number.
Hint 2 — How many bits cover 1000?
Hint 3 — Ten binary digits are enough.
Main idea — Since each taster still only answers alive or dead, the number of tasters needed is simply the number of binary digits required to uniquely number every bottle, however many there are.
Solution
- Number the bottles 0 through 999 in binary, using 10 digits per bottle, since 2 to the 10th power is 1024.
- Use 10 tasters, one per digit; each taster drinks from every bottle whose label has a 1 in their assigned digit.
- Read the pattern of deaths as a 10-digit binary number. That number is the poisoned bottle.
Reasoning
The mechanism is identical to the small-scale version, just extended: every bottle still gets its own unique code, and a taster still dies exactly when the poisoned bottle has a 1 in their assigned digit.
Since 2 to the 10th power is 1024, comfortably more than 1000, ten digits are enough to give every bottle a distinct code, so ten tasters are both necessary and sufficient.
2. Find the Odd Coin Using Binary Encoding
You have 8 identical-looking coins, and exactly one is fake and heavier than the rest, though you don't know which. You have a detector that can test any group of coins at once and simply lights up YES if the fake coin is somewhere in that group, or NO if it isn't.
Rules
- The detector only answers yes or no
- Any subset of coins can be tested
- All tests can be decided in advance
Your task — Find the fewest detector tests needed to identify the fake coin, and how to choose each test's coins.
Difficulty — Medium
Hint 1 — Each test is one bit.
Hint 2 — Assign every coin a binary code.
Hint 3 — Test coins with a 1 in that digit.
Main idea — Each test is really just one yes or no bit of information, so giving every coin its own binary code and testing by digit position finds the fake in the fewest possible tests.
Solution
- Number the coins 0 through 7 in 3-digit binary.
- Run 3 tests: Test A includes every coin with a 1 in the first digit, Test B the second digit, Test C the third digit.
- Read the YES and NO results as a 3-digit binary number. That number identifies the fake coin.
Reasoning
Because each coin has a unique 3-digit code, and the detector lights up exactly when the fake coin's digit matches the tested position, the pattern of answers reconstructs the fake coin's code exactly.
Three tests are enough because three binary digits are sufficient to give each of the 8 coins a distinct identity.
3. 100 Prisoners: Light Bulb Strategy
100 prisoners are each sent, one at a time in an unpredictable order chosen by the warden, into a room containing a single light bulb, currently off. Every prisoner will eventually enter the room infinitely many times. Whenever a prisoner is inside, they may leave the switch as it is or toggle it. At any point, any prisoner may instead declare that all 100 have visited the room at least once.
Rules
- Only one bulb, on or off, is visible
- Each prisoner may only toggle or leave it
- All 100 must have visited before declaring
Your task — Devise a strategy the prisoners can agree on beforehand that guarantees they eventually declare correctly.
Difficulty — Hard
Hint 1 — Pick one prisoner as counter.
Hint 2 — Others turn it on once only.
Hint 3 — Counter turns it off, tallying.
Main idea — Assigning one prisoner as a dedicated counter, and having everyone else contribute exactly one on-toggle in their lifetime, turns the bulb into a running tally only the counter can read.
Solution
- Designate one prisoner as the counter before the process begins.
- Every other prisoner turns the bulb on the first time they ever find it off, and does nothing on every later visit.
- The counter turns the bulb off every time they find it on, adding one to their tally each time.
- Once the counter's tally reaches 99, they declare that all 100 prisoners have visited the room.
Reasoning
Because each non-counter prisoner contributes exactly one on-toggle across all their visits, the counter's tally of off-toggles exactly equals the number of distinct non-counter prisoners who have visited so far.
Since every prisoner enters the room infinitely often, this tally is guaranteed to eventually reach 99, at which point every prisoner besides the counter has certainly visited, and the counter's own presence completes the full 100, making the declaration certain to be correct.
4. Find the Missing Number Using XOR
An array contains every integer from 1 to n exactly once, except one number is missing. You may scan the array only once.
Rules
- Numbers 1 through n, one missing
- Every remaining number appears exactly once
- Only a single pass is allowed
Your task — Find the missing number using a method that needs only one pass and no extra memory.
Difficulty — Easy
Hint 1 — XOR a number with itself?
Hint 2 — XOR 1 through n together.
Hint 3 — XOR that with the array.
Main idea — XOR-ing every number from 1 to n together, then XOR-ing that with every number actually present, cancels out every number that appears in both, leaving only the missing one.
Solution
- Compute the XOR of every integer from 1 to n.
- Compute the XOR of every number actually present in the array.
- XOR these two results together. Every shared number cancels to zero, leaving exactly the missing number.
Reasoning
XOR-ing a number with itself gives zero, and XOR-ing anything with zero leaves it unchanged.
Since every number from 1 to n except the missing one appears in both the full range and the array, those pairs cancel out, and only the missing number, present in the range but not the array, survives, all found in one pass with constant extra memory.
5. One Box Different: Identify Using Questions
You have 8 sealed, identical-looking boxes. Exactly one contains a prize, and a friend who knows which one it is will only answer yes or no questions of the form, "Is the prize in this specific subset of boxes?"
Rules
- Only yes or no answers are given
- Any subset can be asked about
- Exactly one box holds the prize
Your task — Find the fewest questions needed, in the worst case, to guarantee identifying the correct box.
Difficulty — Medium
Hint 1 — Split the boxes in half.
Hint 2 — Each answer removes half.
Hint 3 — Three splits cover all eight.
Main idea — Asking about a subset that's always exactly half of the remaining candidates halves the possibilities every time, so the number of questions matches how many times 8 can be halved down to 1.
Solution
- Ask whether the prize is among 4 specific boxes; the answer narrows the field to those 4 or the other 4.
- Ask the same kind of question about half of the remaining 4, narrowing to 2.
- Ask one more question splitting those 2 boxes, which identifies the exact box, for 3 questions total.
Reasoning
Each yes or no answer can only ever eliminate half of the remaining candidates in the best possible strategy, so the number of questions needed is the smallest number of halvings that brings 8 boxes down to 1, which is 3.
Any fewer than 3 questions could distinguish at most 4 boxes, not all 8, so 3 is both achievable and provably minimal.
6. Switches Representing Binary Numbers
A control panel has 4 switches in a row, each either up, representing 1, or down, representing 0. The leftmost switch represents the highest place value, just like the leftmost digit in a written binary number.
Rules
- 4 switches, each up or down
- Leftmost switch is the highest place value
- Positions read left to right as digits
Your task — Find the decimal number shown when the switches read up, down, up, down from left to right, and find how many distinct numbers 4 switches can represent in total.
Difficulty — Easy
Hint 1 — Each switch is a power of two.
Hint 2 — Add up every up switch's value.
Hint 3 — Four switches, two choices each.
Main idea — Each switch simply contributes its own power of two when it's up, so reading the switches is exactly the same as reading a binary number.
Solution
- From left to right, the switches represent the values 8, 4, 2, and 1.
- Up, down, up, down means the 8 and 2 positions are active, giving 8 plus 2, which is 10.
- Since each of the 4 switches independently has 2 possible states, the total number of distinct representable numbers is 2 to the 4th power, which is 16.
Reasoning
A binary number is simply a sum of powers of two, one for each digit that's a 1, and a switch panel works the same way, with each switch standing in for one binary digit.
Because every switch can independently be up or down, the total count of distinct patterns, and therefore distinct representable numbers, is 2 multiplied by itself once per switch, giving 16 for 4 switches, covering every whole number from 0 to 15.
7. Counterfeit Coin: Unknown Direction
You have 12 identical-looking coins. Exactly one is counterfeit, and it is either heavier or lighter than the rest, though you don't know which. You have a two-pan balance scale and no weights.
Rules
- The scale only compares two groups
- The fake coin's direction is unknown
- No weights are provided
Your task — Find the fewest weighings needed to identify the counterfeit coin and whether it's heavier or lighter.
Difficulty — Hard
Hint 1 — Three groups of four to start.
Hint 2 — Reuse coins across weighings.
Hint 3 — Track each coin's outcome pattern.
Main idea — Carefully rotating which coins sit on which pan across three weighings gives every coin its own unique pattern of outcomes, pinning down both its identity and whether it's heavy or light.
Solution
- Split the 12 coins into three groups of 4 and weigh any two groups against each other.
- Depending on whether they balance or tip, select a smaller, carefully chosen set of coins, some swapped between pans and some set aside, for a second weighing.
- Use the pattern of results from the first two weighings to choose a precise third weighing among the remaining suspects.
- The exact sequence of balanced, left-heavy, or right-heavy outcomes across all three weighings uniquely identifies the counterfeit coin and its direction.
Reasoning
With 12 coins and an unknown direction, there are 24 total possibilities to distinguish, and three weighings, each with three outcomes, can distinguish up to 27 possibilities, just enough to cover all 24.
The key is designing each weighing so every coin appears on the left pan, the right pan, or neither in a distinct pattern of its own across the three weighings, so no two of the 24 possibilities ever produce the same sequence of outcomes, making three weighings both necessary and sufficient.