#### How to have two 1 hour uneven burning fuses burn for 45 mins?

- light only ONE end
- burn both ends = 30 mins
- when it finishes, light the other end

#### Three light bulbs are all off in one room, three light switches in another...

...If you can't see the bulbs from the switch room, how can you tell which connects to which if you can only enter the bulb room once?

Flip the first switch for one bulb for many minutes, then turn it off.

Flip the second switch on. Enter the bulb room, the bulb on connects to the second switch, the warmer of the two bulbs off is the first switch.

#### At night 4 people arrive at one side of a bridge...

**...that can only support 2 people at a time and they have only one flashlight.**

If each were alone here's how fast they could cross: the first in 15 minutes, the second in 10 minutes, the third in 2 minutes and the fourth in 1 minute.

If the flashlight only has 17 minutes how do they cross?

- The 1 minute and 2 minute cross together (takes 2 minutes).
- The 1 minute returns (total is now 3 minutes).
- The 10 and 5 minutes cross together (total is now 13 minutes).
- The 2 minute returns (the total is now 15 minutes).
- Finally the 1 minute and 2 minute cross again (17 minutes and complete).

#### 3 bags contain all oranges, all apples, or a mix of oranges and apples...

**...BUT the label on each definitely is incorrect. How do you find out which bag has what and how many bags to you need to open?**

*Choose the one labeled "mixed" and if it contains apples, therefore the remaining bag which is labelled oranges must not contain all oranges and so must be the mixed one.*

#### There are 3 red hats and 2 blue hats in a bag....

Andrew, Bob, and Carol each reach into the box and place one of the hats on their own head. They cannot see what color hat they have chosen. Then they sit down all facing in the same direction: Andrew <-- Bob <--Carol

- Such that Carol can see what color Bob and Andrew are wearing.
- Bob can see what color Andrew is wearing.
- Andrew can't see anyone's hats.

**The first person to say what color hat they are wearing wins.**
The winner of the game gets a billion dollars... But if they guess wrong, they die... so nobody wants to try "just guessing"...

SO... after they grab their hats and sit down, a long time passes...

Eventually somebody says "I have the answer" and successfully states what color hat they have.

- Since Carol can see Andrew and Bob, if they both were wearing blue hats she would immediately know that she was wearing red, so unlikely that a long time would pass before she answered (and take the money)...
- Therefore Andrew and Bob have one red hat and one blue hat. (And Carol knows there's a 33% chance she's got a blue hat and a 66% chance she's got a red hat).
- Since Bob knows that Carol delayed in answering "a long time passes" AND he can see the color of hat that Andrew is wearing, then
- Either Andrew is wearing a blue hat, and therefore Bob must be wearing a red hat.
- Or Andrew is wearing a red hat, and therefore Bob must be wearing a blue hat.

Bob successfully answers...

*(unless Carol is more interested in sadistic plots and even though she knows both Bob and Andrew have blue hats she just waits to watch Bob get it wrong...)*

```
NOTE: this variation from the NY Times is slightly incorrect as it is essentially asking why Andrew wins...
The clue in order for "Andrew" to know (the delay) is the same as what Bob uses, but Bob will be able to deduce it much faster.
(Again, Carol could be deliberately waiting to watch Andrew fail too...)
```

http://tierneylab.blogs.nytimes.com/2009/03/16/the-puzzle-of-the-3-hats

#### One ball of 8 weighs more than the other 7, how can you identify it with two measurings of a balance scale?

Weigh 3 vs 3, if they match then weigh one of the "good" ones against
one of the remaining ones, if they're unequal you have the heavier one,
if they're equal then the last is the heavy one.

If the 3 vs 3 do not match then take two of the heavy side and weigh
them against each other: if they're unequal you have the heavier one, if
they're equal then the last of the heavy side is the heavy one.

#### One ball of 12 weighs more OR less than the other 11, how can you identify it and whether it's heavier or lighter with three measurings of a balance scale?

*Weigh 4 vs 4, label them ABCD and EFGH. If they balance then weigh "good" ABC against WXY. If the second weighing balances then weigh Z against A to see if Z is light or heavy. If the second weighing has WXY heavier or lighter (make a note of which as we have solved whether the imbalance is heavy or light), then weigh W with X. If they balance then Y is the imbalance from step 2 (heavier or lighter). If they do not balance then whichever matches the imbalance from step 2 is the off ball.*

IF at the first weighing ABCD was lighter than EFGH, in the second weighing rotate such that ABCZ is weighed against D with "good" XYZ. If ...

Note that this problem can also be solved by carefully measuring the results as the left and right groups of 4 are rotated.

12 becomes 4 v 4 v (4) - if the balance the last 4 are easy

if not balanced: 1,2,5 vs 3,6,12

#### 5 pots of 10g coins BUT one contains 9g coins, which pot is off by measuring the weight once?

1 from pot 1, 2 from pot 2, 3 from pot 3, 4 from pot 4, and 5 from pot 5

Expected weight should be 150g: if it’s 149 then pot 1 , if it’s 148 then pot 2, etc.

#### How can you use a weighted coin (i.e. head more than tails) and still create a fair system of flips?

*Aggregate the outcomes: treat two flips as a single result such that heads then tails = Heads, and tails followed by heads = Tails.*

#### 10 are heads of N coins, how to create 2 groups that have the same number of heads up?

*Take any 10 from N and flip them (inverted will mirror the number of heads in the N - 10 group)*

#### 3 colors of socks: how many to take out until you have a pair?

*4 (1 of each and the last 1 must match 1 of the first 3)*

#### 100 closed lockers, open all of the lockers on the first pass...

** ...close every 2nd locker on the second pass, on the third pass and for every 3rd locker open it if it's closed, close it if it's open.**
**After the hundreth pass, how many lockers are open?**

i.e. after the hundreth the locker 12 was opened on pass 1, closed pass 2, opened pass 3, closed pass 4, opened pass 6, closed pass 12.

locker 13 (prime) was opened on pass 1 and closed on pass 13.

locker 16: opened on 1, closed on 2, opened on 4, closed on 8, opened on 16!

There are 9 perfect squares under one hundred: 1, 4, 9, 16, 25, 36, 49, 64, 81

#### Incomplete Puzzles

Minutes Degrees from 12:00 = mins * 6

Hours Degrees From 12:00 = hours * 30 + mins * .5

Find 1 duplicate in 100 numbers of 1 to 100 = add them up and subtract sum of 1 to 100

ALTERNATIVES: hashmap O(1), sort and then scan looking for a double entry (nLog(n) if mergesort? + n ), n\^2 if using brute force

Sorted List rotated: find min = naive if curr < prev is O(n)

Binary Search compare first and mid, if ordered then reset is in partition > mid (RIGHT)

find any elem: if > first and Ordered then LEFT

BAD: binary search against the "fixed" list using the min location as an offset with mod list size ?

nxn matrix of numbers in ascending order in both dimensions how would you go about finding if the number y is in the matrix.

5623 players in a tournament, how many matches must be played?

5622 (everybody loses at least once except the winner)

#### Unsolved Puzzles

N different flavored Cakes (each with a different Volume) for K people, each person should get an equal volume of Cake (but only a single flavor)

V’s 1, 2, 3, 4 for 5 people

add all volumes together / people = “theoretical best” (i.e. 10/5 = 2)

start with 2 cakes, 4 + 1, so V=1 for K, next 4 + 2 = doesn’t work, 4+3 doesn’t work

3 cakes: 4+3+2 = 9 BUT not divisible by 5

1 * 1, 2 * 1, 2 * 1 = waste 5 ( 10-5)

discard

#### Random Facts

- World Population (estimated 2012) = 7 Billion
- US Population (estimated 2012) = 316 Million
- Earth circumference (equator) = 24,901.55 miles (40,075.16 kilometers)