Brain Teasers

You have 8 identical-looking balls and a balance scale. One ball is slightly heavier than the rest. Find it using the fewest weighings.

Divide into three groups: 3, 3, and 2 balls. Weigh the two groups of 3 against each other.

If balanced: the heavy ball is in the pair of 2. Weigh one against the other — the heavier one is it. Total: 2 weighings.

If unbalanced: take the 3 balls from the heavier side. Weigh 2 of those 3. If balanced, the unweighed one is heavy; if not, the heavier side is. Total: still 2 weighings.

// Step 1: Weigh group A (3) vs group B (3)
// Balanced: heavy is in group C (2), weigh them
// Unbalanced: take heavier group (3), weigh 2 of them

Ternary decision tree: Each balance weighing has 3 outcomes (left heavy, right heavy, balanced). Two weighings give 3² = 9 outcomes — sufficient to identify 1 of 8 balls.

For n balls, minimum weighings = ceil(log3(n)). With 27 balls, 3 weighings suffice; with 3 balls, just 1 weighing identifies the heavy one.

100 doors are initially closed. In pass i (for i = 1 to 100), you toggle every ith door. After all 100 passes, which doors are open?

Door n is toggled exactly once for each divisor of n. A door ends up open if it was toggled an odd number of times — meaning n must have an odd number of divisors.

Most integers have divisors in pairs (d and n/d). Only perfect squares break this: their square root is its own pair, resulting in an odd divisor count.

Perfect squares up to 100: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 — exactly 10 doors remain open.

// Open doors = perfect squares <= 100
// 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 (count: 10)
// Door n is open iff n has an odd number of divisors
// n has odd divisors iff n is a perfect square

Divisors pair up: For non-square n, each divisor d has a distinct partner n/d — the two toggles cancel. For perfect squares, sqrt(n) is unpaired, leaving an odd count.

This puzzle illustrates that mathematical structure (perfect squares) can emerge from an apparently mechanical process — a useful example for teaching number theory.

100 prisoners stand in a line, each wearing a randomly assigned black or white hat. Each prisoner can see all hats in front but not their own. Starting from the back, each must guess their own hat color aloud. Maximize correct guesses.

The last prisoner (who sees all 99 hats in front) announces a color encoding parity: say black if they see an odd count of black hats, white if even.

Each subsequent prisoner tracks the parity from what they heard and what they see, and deduces their own hat color by comparing expected vs actual parity.

This guarantees 99 correct guesses with certainty. The last prisoner has a 50/50 chance since they encode information rather than guess their actual hat.

// Last person: say black if odd black seen, white if even (parity signal)
// Person k: count black hats ahead + adjust for heard guesses
// If parity matches expected: hat is white; else: hat is black
// Result: 99 certain + 1 random = minimum 99 correct

Parity encoding: The last prisoner transmits one bit of global information (parity) for free, enabling all 99 others to determine their hat color with certainty.

For k colors, use mod k arithmetic: the last prisoner announces a value such that (sum of all hat values) mod k equals 0, and each person deduces their hat by subtraction.

A farmer must cross a river with a fox, a chicken, and a bag of grain. The boat holds only the farmer plus one item. Left alone: fox eats chicken; chicken eats grain.

The chicken is the constrained item — it cannot be left with either the fox or the grain. The non-obvious solution requires the farmer to bring the chicken back midway.

Steps: 1) Take chicken across. 2) Return alone. 3) Take fox across. 4) Bring chicken back. 5) Take grain across. 6) Return alone. 7) Take chicken across.

A symmetric alternative: take grain instead of fox in step 3 (then bring grain back and take fox in a different order). Both solutions use 7 crossings.

// Trip 1: Farmer + Chicken -> other side
// Trip 2: Farmer <- alone
// Trip 3: Farmer + Fox -> other side
// Trip 4: Farmer + Chicken <- return  (key insight!)
// Trip 5: Farmer + Grain -> other side
// Trip 6: Farmer <- alone
// Trip 7: Farmer + Chicken -> other side

Bring chicken back: Trip 4 is the counterintuitive step — bringing the chicken back prevents any unsafe pairing while transporting fox and grain separately.

State-space search (BFS over all configurations) can solve all such puzzles algorithmically, handling any number of objects with arbitrary conflict constraints.

You have a 7-unit gold bar and a worker who must be paid 1 unit per day for 7 days. You can make exactly 2 cuts. How do you pay exactly each day?

Cut the bar into pieces of 1, 2, and 4 units (powers of 2). These three pieces can represent any integer from 1 to 7 via binary exchange.

Day 1: give 1. Day 2: give 2, take back 1. Day 3: give 1+2. Day 4: give 4, take back 1+2. Day 5: give 4+1. Day 6: give 4+2, take back 1. Day 7: give 4+2+1.

This uses the same logic as binary representation: 1+2+4 = 7 and any value 1-7 is representable.

// Pieces: 1, 2, 4 units (two cuts)
// Day 1: give 1        | give:1
// Day 2: give 2, get 1 | give:2
// Day 3: give 1        | hold:1+2
// Day 4: give 4, get 2+1 | give:4
// Day 5: give 1        | hold:4+1
// Day 6: give 2, get 1 | hold:4+2
// Day 7: give 1        | total paid: 7

Binary powers strategy: Cutting at 1, 2, 4 is the only way to cover all 7 values with 2 cuts — these are the minimum cuts needed for binary representation of numbers 1 through 7.

For n days with k cuts, the optimal pieces are 1, 2, 4, ..., 2^(k-1), and the remainder. This greedy doubling covers up to 2^(k+1) - 1 total days.

You have two ropes, each of which takes exactly 60 minutes to burn completely. However, burning is non-uniform — you cannot simply fold or measure to get 30 minutes. How do you measure exactly 45 minutes?

Light rope 1 from BOTH ends simultaneously, and light rope 2 from ONE end only. Since rope 1 burns from two ends, it finishes in exactly 30 minutes.

When rope 1 is fully burnt (at 30 min mark), light the OTHER end of rope 2. Rope 2 has 30 minutes of burn left, and lighting both ends halves that to 15 minutes.

Total elapsed time: 30 + 15 = 45 minutes. No physical measurement is needed — just simultaneous lighting events.

// Timeline:
// t=0:    Light rope1 (both ends), rope2 (one end)
// t=30:   Rope1 done. Light rope2 second end.
// t=45:   Rope2 done. Total = 45 minutes.

// Key insight:
// Burning from both ends halves the remaining burn time,
// regardless of non-uniformity.

Core insight: Lighting a rope from both ends halves whatever burn time remains, so you can create 15-min intervals by splitting 30 minutes.

This puzzle generalizes: with n ropes you can measure any multiple of (60 / 2^n) minutes — each additional rope gives you one more halving step.

On an island, N people have blue eyes (and others have non-blue eyes). Everyone can see everyone else's eye color but not their own. No one discusses eye color. A visitor publicly announces: at least one person on this island has blue eyes.

The rule: if anyone ever deduces their own eye color at night, they must leave the island the next morning. Base case — if N=1, that person sees no other blue-eyed people, so they know they must be the one, and leaves on night 1.

For N=2: each person sees 1 blue-eyed person. Night 1, neither leaves (each thinks the other might be the only one). But when neither leaves after night 1, each deduces: the other person saw a blue-eyed person too, so I must also have blue eyes. Both leave on night 2.

By induction: all N blue-eyed people leave on night N. The visitor's statement adds common knowledge — everyone now knows that everyone knows that at least one has blue eyes.

// Inductive logic:
// Base: N=1 → leaves night 1
// Inductive step: if N=k all leave on night k,
//   then for N=k+1:
//     each person sees k blue-eyed others and waits k nights
//     when nobody leaves on night k, they deduce they have blue eyes
//     all N=k+1 leave on night k+1

// The visitor created "common knowledge":
// Before: everyone knew, but not everyone knew that everyone knew.
// After: the public announcement makes it universally known.

Common knowledge: The key is the difference between "everyone knows X" and "everyone knows that everyone knows X." The public announcement escalates individual knowledge to common knowledge, enabling the inductive chain.

This puzzle is a classic example of epistemic logic and game theory — it illustrates how public information with shared observation triggers coordinated action that private information cannot.

You have 2 eggs and a 100-floor building. There is a critical floor F such that eggs survive drops from floors below F but break at F and above. Find F with the minimum number of drops in the worst case.

The naive approach — binary search — uses only 1 egg for halving, which fails because a break leaves you with no egg to continue. You need a strategy that balances the linear scan (second egg) with the jump size (first egg).

Optimal strategy: drop first egg from floor x, then x+(x-1), then x+(x-1)+(x-2), etc. (decreasing intervals). This way, each breakage costs 1 fewer linear step with the second egg, keeping worst case constant.

Solve: x + (x-1) + ... + 1 >= 100 → x(x+1)/2 >= 100 → x = 14. Start at floor 14, then 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. Worst case is exactly 14 drops.

function eggDrop(n, k) {
  // n = eggs, k = floors
  // dp[i][j] = max floors testable with i eggs and j drops
  const dp = Array.from({length: n + 1}, () => new Array(k + 1).fill(0));
  let m = 0;
  while (dp[n][m] < k) {
    m++;
    for (let i = 1; i <= n; i++) {
      dp[i][m] = dp[i-1][m-1] + dp[i][m-1] + 1;
    }
  }
  return m; // minimum drops needed
}
console.log(eggDrop(2, 100)); // 14

Decreasing intervals: The insight is that as you use more drops on the first egg, you can afford fewer linear scans — so intervals decrease by 1 each time, giving a triangular number formula x(x+1)/2 >= n.

For the general k-egg, n-floor case, dynamic programming gives O(k·n log n) or O(k·n²) solutions. The two-egg, 100-floor variant is the classic interview form illustrating the tradeoff between binary search and linear fallback.

Testing each bottle individually would require 1000 prisoners (one per bottle). Binary encoding dramatically reduces this number.

Label each bottle from 1 to 1000 in binary (10 bits). Assign one prisoner per bit position (1 through 10). Each prisoner drinks from all bottles that have a '1' in their assigned bit position.

After 30 days, observe which prisoners die. The pattern of deaths forms a binary number that directly identifies the poisoned bottle.

Since 2^10 = 1024 > 1000, only 10 prisoners are needed.

// Example: if prisoners 1, 3, 4 die (bits 1, 3, 4 are set)
// Binary: 0b0011010 = bottle number 26 is poisoned
// Bottle 0 is identified if no prisoners die

Binary encoding trick: Each prisoner's death/survival maps to a bit in the binary representation of the poisoned bottle's number — 10 binary bits covers all 1000 bottles.

This is a classic information theory puzzle: log₂(1000) ≈ 9.97, so at least 10 bits (prisoners) are theoretically necessary, and the binary approach achieves this minimum.

Four people must cross a narrow bridge at night with one torch. Only 2 can cross at a time, and the torch must be carried back for each return trip. Each person has a different speed.

Classic instance: speeds of 1, 2, 5, 10 minutes. Naively pairing fastest with slowest: (1+10) + 1 + (2+5) + 2 = 21 minutes. Optimal: send the two slowest together.

Optimal strategy: 1+2 cross (2 min), 1 returns (1 min), 5+10 cross (10 min), 2 returns (2 min), 1+2 cross (2 min). Total: 17 minutes.

The key insight is that the two slowest people should always cross together to amortize their high cost over a single crossing.

// Optimal strategy:
// Step 1: Person 1 and 2 cross → 2 min
// Step 2: Person 1 returns → 1 min
// Step 3: Person 5 and 10 cross → 10 min
// Step 4: Person 2 returns → 2 min
// Step 5: Person 1 and 2 cross → 2 min
// Total: 17 minutes

Pair the two slowest: The dominant cost is the slowest person — pairing the two slowest together means you only pay for the slowest once, not twice.

The general algorithm for n people: repeatedly apply either the "pair two slowest" or "escort one slowest" strategy based on which costs less for the current remaining group.

You are on a game show with three doors. Behind one is a car; behind the others are goats. You pick a door. The host opens a different door revealing a goat. Should you switch your choice?

Counterintuitively, you should always switch. When you first pick, you have a 1/3 chance of being right. After the host reveals a goat, that probability does not increase to 1/2 — rather, the remaining door has a 2/3 probability of having the car.

The host's action is not random — they always open a goat door — which transfers the probability from your original choice to the other door.

Switching wins 2/3 of the time; staying wins only 1/3 of the time.

// Simulation (switch always wins ~66.7% of the time):
// Initial pick: P(car) = 1/3
// Host removes a goat → other remaining door has P(car) = 2/3
// Switching wins when initial pick was WRONG (prob = 2/3)

Bayesian intuition: The host's additional information (revealing a goat) doesn't help your original door — it concentrates the 2/3 probability onto the single unchosen door.

Run a simulation: simulate 10,000 rounds with "always switch" vs "always stay." Always switch will win approximately 6,667 times vs 3,333 — definitively demonstrating the 2/3 probability.

Neither jug holds 4 liters directly. The solution uses iterative filling and pouring to reach the target through combinations of 3 and 5.

One approach: Fill the 5L jug. Pour into the 3L jug (3L full, 2L left in 5L). Empty the 3L jug. Pour the remaining 2L into the 3L jug. Fill the 5L jug again. Pour 1L from the 5L jug into the 3L jug (to fill it). Now the 5L jug has exactly 4 liters.

An alternative: Fill the 3L jug. Pour it into the 5L jug. Fill the 3L jug again. Pour 2L into the 5L jug to fill it. 1L remains in the 3L jug. Empty the 5L jug. Pour the 1L into it. Fill the 3L jug. Pour into the 5L jug. 4 liters are now in the 5L jug.

// Steps: Fill 5L → pour into 3L → empty 3L → pour 2L into 3L
// → fill 5L → pour 1L into 3L (to fill it) → 5L has 4L

Water jug problems are graph search: Each state is (3L amount, 5L amount). BFS from (0,0) to any state with 4 finds the shortest sequence of operations.

In general, you can measure any amount that is a multiple of GCD(3, 5) = 1, meaning any integer from 0 to 8 is achievable with these two jugs.

Three switches outside a room control three light bulbs inside. You can flip switches as many times as you want before entering the room — but you can only enter the room once. How do you identify which switch controls which bulb?

Use heat as a second property of bulbs: turn on switch 1 for 10 minutes, turn it off, then turn on switch 2, and enter the room. The lit bulb is controlled by switch 2. The warm-but-unlit bulb was controlled by switch 1. The cold-and-unlit bulb is controlled by switch 3.

This works because incandescent bulbs retain heat after being turned off — exploiting a physical property beyond just on/off state.

// Strategy:
// - Turn switch 1 ON for 10 minutes, then OFF
// - Turn switch 2 ON, then enter the room
// - LIT bulb → switch 2
// - WARM but unlit bulb → switch 1
// - COLD and unlit bulb → switch 3

Use heat as a second channel: With only on/off states (2 states, 3 unknowns), the puzzle requires exploiting an extra dimension — heat from prior activation differentiates bulb 1 from bulb 3.

With 4 bulbs and one entry, extend: leave switch 1 on 20 min, switch 2 on 10 min, switch 3 on 5 min, switch 4 off. Relative warmth distinguishes all four.

How many people do you need in a room for there to be a 50%+ chance that two share a birthday? The answer is surprisingly small — just 23 people.

Instead of calculating the probability of a match directly, calculate the probability that all n birthdays are different. P(no match) = (365/365) ×(364/365) × (363/365) × ... × ((366-n)/365).

P(no match with 23 people) ≈ 49.3%, so P(at least one match) ≈ 50.7% — just over 50%.

With 70 people, the probability of a shared birthday exceeds 99.9%.

// P(at least one shared birthday with n people)
// = 1 - P(all different)
// = 1 - (365 * 364 * ... * (365-n+1)) / 365^n

function birthdayProbability(n) {
  let p = 1;
  for (let i = 0; i < n; i++) p *= (365 - i) / 365;
  return 1 - p;
}
// birthdayProbability(23) ≈ 0.507

Complement probability: Calculating "all different" and subtracting from 1 is much simpler than counting all the ways two people might share a birthday.

The paradox arises from human intuition underestimating combinatorial growth — 23 people create C(23, 2) = 253 possible pairs, each with a 1/365 chance of matching.

N people stand in a circle, counting every kth person who is eliminated. Find the last remaining person's position. With k=2, this has an elegant O(n) formula.

For k=2: after eliminating every second person, the position of the survivor after eliminating from n people is J(n) = (J(n-1) + 2) % n, with J(1) = 0 (0-indexed).

The recursive formula comes from the observation that after the second person is eliminated, the problem reduces to n-1 people starting from the third person.

For general k, the recurrence is J(n,k) = (J(n-1,k) + k) % n.

function josephus(n) { // k=2, 0-indexed
  let pos = 0;
  for (let i = 2; i <= n; i++) pos = (pos + 2) % i;
  return pos; // 1-indexed: return pos + 1
}
// josephus(7) = 6 (0-indexed), person 7 survives

Recurrence reduction: Each elimination reduces the circle size by 1, and the survivor's position shifts by k positions relative to the new circle — the recurrence captures this shift.

The O(n) iterative solution computes the survivor's position bottom-up from the base case J(1,k)=0, avoiding recursive overhead.

5 pirates rank 1 (most senior) to 5 (least senior). Pirate 1 proposes how to divide 100 gold coins. All pirates vote; if 50%+ approve, the proposal passes. Otherwise Pirate 1 is thrown overboard and Pirate 2 proposes next. What should Pirate 1 propose?

Work backwards using game theory. Pirate 5 alone: keeps 100. Pirate 4 and 5: Pirate 4 proposes (100, 0) and votes yes (50% threshold met). Pirate 3,4,5: Pirate 3 proposes (98, 0, 2) — Pirate 5 prefers 2 over 0 from the 2-pirate scenario.

Continuing backwards, Pirate 1 proposes: (98, 0, 1, 0, 1). Pirates 1, 3, and 5 vote yes (3 of 5 = 60%). Pirate 1 keeps 98 coins.

// Backward induction:
// n=1: (100)
// n=2: (100, 0)  — P1 gets 100
// n=3: (98, 0, 2) — P1 bribes P3 with 2
// n=4: (99, 0, 1, 0) — P1 bribes P3 with 1
// n=5: (98, 0, 1, 0, 1) — P1 bribes P3 and P5

Backward induction: Solve from the simplest case (1 pirate) backwards — at each step, bribe the minimum number of pirates needed for approval by offering them 1 more than they would get if the current proposer is eliminated.

This puzzle demonstrates that rational, self-interested agents can reach surprising equilibria — Pirate 1, the most powerful, keeps 98% of the gold through pure logic.

Given e eggs and n floors, find the minimum number of trials in the worst case to determine the critical floor (highest safe floor). Dropping an egg above the critical floor breaks it.

With 2 eggs and 100 floors: try floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 (decreasing increments). If the first egg breaks at floor k, scan linearly below from the previous checkpoint. Worst case: 14 trials.

The diminishing interval strategy ensures the sum of decrements equals 100: k + (k-1) + ... + 1 = k(k+1)/2 ≥ 100, so k = 14.

For e eggs and n floors, the DP solution finds the minimum trials in O(e × n × log n) using binary search optimization.

// 2 eggs, n floors: min trials k satisfies k(k+1)/2 >= n
// k = ceil((-1 + sqrt(1 + 8n)) / 2)
// For n=100: k = 14

// Drop pattern: floor 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99
// If egg breaks at 27: check 15-26 linearly (12 more trials max)

Diminishing intervals: Reducing the search interval by 1 each time the first egg survives balances worst-case trials for linear scan after first egg breaks vs continued higher-floor checks.

With 3 eggs, the minimum is only 5 trials for 100 floors — each additional egg dramatically reduces the required trials by enabling more efficient binary-style search.

Three ants are placed at the corners of an equilateral triangle. Each ant picks a random direction (clockwise or counterclockwise) and walks. What is the probability they all avoid collisions?

Each ant independently chooses clockwise (CW) or counterclockwise (CCW) with equal probability 1/2. A collision occurs when at least two ants travel toward each other.

No collision occurs only when all ants move in the same direction: all CW or all CCW. Probability = (1/2)³ + (1/2)³ = 2/8 = 1/4.

P(at least one collision) = 1 - 1/4 = 3/4.

// Each ant: P(CW) = 1/2, P(CCW) = 1/2
// Safe combinations: (CW,CW,CW) or (CCW,CCW,CCW)
// P(no collision) = P(all CW) + P(all CCW) = (1/2)^3 + (1/2)^3 = 1/4
// P(collision) = 1 - 1/4 = 3/4

Complement principle: Count the easy cases (all same direction) rather than all collision scenarios. The complement gives the collision probability directly.

For n ants on a regular n-gon, by the same logic: P(no collision) = 2/(2^n) = 1/(2^(n-1)), since only all-CW or all-CCW avoids collisions among all 2^n combinations.

With exactly 2 eggs and 100 floors, find the minimum worst-case number of trials to determine the highest safe floor from which an egg can be dropped without breaking.

If you break the first egg on floor k, you must then scan floors 1 through k-1 linearly with the second egg. To minimize the worst case, start at floor k, and if it survives, go to floor k + (k-1), then k + (k-1) + (k-2), and so on.

You need the smallest k such that k + (k-1) + ... + 1 = k(k+1)/2 ≥ 100. Solving: k ≥ 13.65, so k = 14. Maximum trials = 14.

// k(k+1)/2 >= 100
// k=13: 91 (not enough)
// k=14: 105 >= 100 ✓
// Drop at: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99
// If first egg breaks at floor f, check f-k+1 to f-1 linearly

Optimal intervals: Using decreasing intervals (k, k-1, k-2, ...) balances the worst case between "early break" (more linear scan) and "late break" (more jumps) scenarios.

This is a specific case of the general egg drop DP: with more eggs, binary search-like strategies become feasible, drastically reducing the needed trials.

A standard 8×8 chessboard has two opposite corner squares removed. Can you tile the remaining 62 squares using 31 dominoes, each covering exactly two adjacent squares?

The answer is no. A chessboard has alternating black and white squares. Opposite corners are the same color (say, both white). Removing them leaves 30 white and 32 black squares (or vice versa).

Each domino covers exactly one black and one white square. 31 dominoes cover 31 white and 31 black squares. Since the board has an unequal count, tiling is impossible.

// Standard chessboard: 32 white + 32 black squares
// Remove 2 corners (same color): 30 white + 32 black remaining
// Each domino covers 1 white + 1 black
// 31 dominoes → 31 white + 31 black needed
// 31 ≠ 30 → IMPOSSIBLE to tile

Coloring invariant: Assigning colors to squares and tracking counts creates an invariant that proves impossibility — a common mathematical proof technique for combinatorial puzzles.

Extension: if you remove one white and one black square (any two of opposite colors), tiling IS always possible — this can be proven by constructing an explicit path algorithm through the board.