Some Logic Puzzles

COIN PROBLEM: (hard!)
There is a game where a coin gets tossed. If it comes up heads, you gain a
dollar. If it comes up tails, you lose half your money. You start with $0 (and
you can have fractional amounts of money, not limited to cents or anything,
money is just a real number).

After N tosses how many different possible values of money can you have?

Example:
toss heads: 1.0
toss tails: 0.5
toss tails: 0.25
toss heads: 1.25
toss heads: 2.25

When N=5, one possible value is 2.25

It may be trivial to write a program to simulate the coin tosses and discover
the function. But why is it what it is?

DICE PROBLEM:
Sue and Bob take turns rolling a 6-sided die. Once either person rolls a 6 the
game is over. Sue rolls first, if she doesn't roll a 6, Bob rolls the die, if
he doesn't roll a 6, Sue rolls again. They continue taking turns until one of
them rolls a 6.

Bob rolls a 6 before Sue.
What is the probability Bob rolled the 6 on his second turn?

EGG PROBLEM: (asked during a software engineering job interview)
you have two eggs
dino eggs, very resiliant
they will absorb a certain amount of force with no negative consequences
but at some point they crack
if they don't crack, they are fine.

so you're on a 100 story building, you got 20 trials (you're allowed at most 20
individual egg drops) and 2 eggs, is it possible to devise a testing algo that
guarantees to tell you at exactly what floor the eggs will break?

drop an egg and it doesnt break -> 19 trials, 2 eggs left
drop an egg and it does break -> 19 trials, 1 eggs left



More logic puzzle/problems can be found at:
http://psthomas.com/LogicPuzzles.html
http://wiki.xkcd.com/irc/Puzzles

stuart.powers@gmail.com