reverse a string - word by word aha:!!

a typical programming interview question is "reverse a string, in place". if you understand pointers, the solution is simple. even if you don't, it can be accomplished using array indices. i usually ask candidates this question first, so they get the algorithm in their head. then i play dirty by asking them to reverse the string word by word, in place. for example if our string is "the house is blue", the return value would be "blue is house the". the words are reversed, but the letters are still in order (within the word).

solution: reverse a string - word by word

100 doors in a row aha:!

problem: you have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.

question: what state are the doors in after the last pass? which are open which are closed?

red marbles, blue marbles aha:!

problem: you have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. (when picking, you'll first randomly pick a jar, and then randomly pick a marble out of that jar) you can arrange the marbles however you like, but each marble must be in a jar.

solution: red marbles, blue marbles

bumblebee aha:!!!!

problem: two trains enter a tunnel 200 miles long (yeah, its a big tunnel) travelling at 100 mph at the same time from opposite directions. as soon as they enter the tunnel a supersonic bee flying at 1000 mph starts from one train and heads toward the other one. as soon as it reaches the other one it turns around and heads back toward the first, going back and forth between the trains until the trains collide in a fiery explosion in the middle of the tunnel (the bee survives). how far did the bee travel?

solution: bumblebee

int atoi( char* pStr ) aha:!

problem: write the definition for this function without using any built-in functions. if pStr is null, return 0. if pStr contains non-numeric characters, either return 0 (ok) or return the number derived so far (better) (e.g. if its "123A", then return 123). assume all numbers are positive. plus or minus signs can be considered non-numeric characters. in order to solve this program, the programmer must understand the difference between the integer 0 and the character '0', and how converting '0' to an int, will not result in 0. in other words, they have to understand what ascii is all about.

daughter's ages aha:!!

two MIT math grads bump into each other at Fairway on the upper west side. they haven't seen each other in over 20 years.

the first grad says to the second: "how have you been?"
second: "great! i got married and i have three daughters now"
first: "really? how old are they?"
second: "well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there.."
first: "right, ok.. oh wait.. hmm, i still don't know"
second: "oh sorry, the oldest one just started to play the piano"
first: "wonderful! my oldest is the same age!"

problem: how old are the daughters?

palindromes aha:!!

problem: this year on October 2, 2001, the date in MMDDYYYY format will be a palindrome (same forwards as backwards).
10/02/2001
when was the last date that this occurred on? (see if you can do it in your head!)

solution: palindromes

sum it up aha:!

problem: you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number? what if i give you the constraint that you can't use a dynamic amount of memory (i.e. the amount of memory you use can't be related to n)?
what if there are two repeating numbers (and the same memory constraint?)

pirates aha:!

five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).

fogcreek programmers aha:!

100 fogcreek programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can't see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says "what color is your hat?" the fogcreek programmer can only answer "red" or "blue." the programmer is killed if he gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front get to hear the answers of the programmers behind them, but not whether they live or die. they can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can't communicate in any way other than those already specified. what strategy should they choose to maximize the number of programmers who are guaranteed to be saved?

bad king aha:!

a bad king has a cellar of 1000 bottles of delightful and very expensive wine. a neighbouring queen plots to kill the bad king and sends a servant to poison the wine. (un)fortunately the bad king's guards catch the servant after he has only poisoned one bottle. alas, the guards don't know which bottle but know that the poison is so strong that even if diluted 1,000,000 times it would still kill the king. furthermore, it takes one month to have an effect. the bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. being a clever bad king he knows he needs to murder no more than 10 prisoners - believing he can fob off such a low death rate - and will still be able to drink the rest of the wine at his anniversary party in 5 weeks time.

explain how....

thanks to Duncan Smeed for tipping me off to this question

jelly beans aha:!

you have three jars that are all mislabeled. one contains peanut butter jelly beans, another grape jelly jelly beans, and the third has a mix of both (not necessarily a 50/50 mix, could be a 1/99 mix or a 399/22 mix). how many jelly beans would you have to pull out, and out of which jars, to find out how to fix the labels on the jars?

| | | | | |
|jar 1| |jar 2| |jar 3|
| | |  | | |
======= ======= =======
 p.b. grape p.b./grape

thanks to joel wollman

bridge aha:!!

problem: this one is a classic that many of you have probably already heard, but all the more reason why it should definitely be included here. four people are on this side of the bridge. the bridge will be destroyed by a bomb in 17 minutes. everyone has to get across before that. problem is that it's dark and so you can't cross the bridge without a flashlight, and they only have one flashlight. plus the bridge is only big enough for two people to cross at once. the four people walk at different speeds: one fella is so fast it only takes him 1 minute to cross the bridge, another 2 minutes, a third 5 minutes, the last it takes 10 minutes to cross the bridge. when two people cross the bridge together (sharing the flashlight), they both walk at the slower person's pace. can they all get across before the bridge blows up?

person A: 1 minute
person B: 2 minutes
person C: 5 minutes
person D:10 minutes

card trick without the trick aha:!!

this is a card trick without the trick. there is no sleight of hand, no tricks up my sleeve, no magic whatsoever. it's all done with logic, yet it will amaze most people.

joel and i are working together as a team to do the trick. babak will be the culprit.

i ask babak to pick 5 cards out of a deck. he can pick any five cards, he can shuffle the deck 7 times, it really doesn't matter. he honestly picks out 5 cards that i cannot see. he hands the five cards to me (joel can't see any of this). i look at the cards and i pick 1 card out and give it back to babak. i then arrange the other four cards in a special way, and give those 4 cards all face down, and in a neat pile, to joel. joel looks at the 4 cards i gave him, and says out loud which card babak is holding (suit and number).

i did not convey any information to joel other than the way i ordered the 4 cards, (all face down, aligned in line with one another) so how did i encode babak's card using that method?

hint 1: card trick without the trick
hint 2: card trick without the trick

hint 1: with five cards there will always be at least two cards of the same suit. since i get to pick the card to give back to babak, i can use that to my advantage to communicate the suit to joel.

hint 2: if i communicate the suit to joel with one of the cards, then i'm only left with the other 3 cards to show the number. since only the ordering of the cards can be used, i am allowed up to six combinations. well, that won't do to signify up to 13 cards, will it? certainly not, but if i pick the right card to show the suit, i can use that card to reduce the range of cards down to 6. how?

pirates revisited aha:!

a slightly different version of the original pirates problem (read that one first to get all the rules). 6 pirates, only one gold coin. as before, the pirates are super-smart, and they value, in this order: (i) their lives, (ii) getting money, (iii) seeing other pirates die. so if given the choice between two outcomes, in which they get the same amount of money, they'd choose the outcome where they get to see more of the other pirates die. how can pirate 6 save his skin?

fuse on fire aha:!!

a mad bomber is out on the job, making bombs. he has two fuses (pieces of string) of varying thickness which each burn for 30 seconds. unfortunately he wants this bomb to go off in 45 seconds. he can't cut the one fuse in half because the fuses are different thicknesses and he can't be sure how long it will burn. how can he arrange the fuses to make his bomb go off at the right time?

dave's on fire aha:

dave winer is stuck on a deserted island, with lots of trees, which is very thin and ten miles long (east to west). large cliffs surround the entire island and if he jumped off, he wouldn't survive the fall. a fire starts burning at the west side of the island. unfortunately this island always has a west to east blowing wind blowing at 2mph and this moves the fire slowly toward dave at 1mph. (so he only has ten hours left). save dave (or maybe, let him burn :-) ! what to do?

chessboard aha:!!!

problem: using 31 dominoes, where one domino covers exactly two squares, can you cover all the empty squares on this chessboard (which has 62 spaces). if so, how? if not, why?

easy river crossing aha:!

three cannibals and three anthropologists have to cross a river. the boat they have is only big enough for two people. if at any point in time there are more cannibals on one side of the river than anthropologists, the cannibals will eat them. what plan can the anthropologists use for crossing the river so they don't get eaten?

remember! the boat can't cross the river by itself, someone has to be in it to row it across.

a much harder river crossing problem will appear later this week.

A - anthropologist
C - cannibal
++ - boat
 
 river
AAA |============|
 |++ |
CCC |============|
 
need to make it
 river
 |============| AAA
 | ++|
 |============| CCC

note that if you violate the "anthropologists > cannibals" rule at any point in time, it is illegal.. for example if a boat with a cannibal and an anthropologist travels to a shore with one cannibal on it, then # cannibals > # anthropologists, even if you say the anthropologist immediately takes the boat back.

shapes aha:!!

part I: draw a square. divide it into four identical squares. remove the bottom left hand square. now divide the resulting shape into four identical shapes.

part II: draw an equilateral triangle (all sides same length). divide it into four identical shapes. remove the bottom left hand shape. now divide the resulting shape into four identical shapes.

this is the sort of problem that i would expect on a MENSA test. i'm not too sure whether getting this right constitutes intelligence in a way that would benefit computer scientists, but maybe it does. if you figure it out, then you can say it does. if you can't figure it out, then you can just say it's all hogwash and it's a stupid question.

thanks to mark chesser

webloggers aha:!

five webloggers - joshua Allen, meg Hourihan, jason Kottke, robert Scoble, and joel Spolsky - were competing for karma points on the major search engines: google, yahoo, altavista, lycos, and msn. karma was distributed on a five point scale. the most popular weblog received 5 points, and the least popular received 1 point. for each search engine, no two webloggers received the same number of points. overall scores were determined by adding up the individual scores from each search engine.

Allen got the highest number of karma points - 24. Kottke was consistent in his scores: he got the same karma points from 4 different search engines. Spolsky got 5 points from lycos, and 3 from msn.

no two webloggers got the same total score, and the final rankings were as follows: Allen, Hourihan, Kottke, Scoble, and Spolsky. how many karma points did Hourihan get from lycos?

hard river crossing aha:!

a disfunctional family has to cross the river. on one side of the river are a mom and 2 daughters, dad and 2 sons, the maid and the dog. there is a boat only big enough to hold 2 people (counting the dog as 1 person). only the adults are capable of operating the boat. everyone has to get to the other side, without anything bad happening.

difficulties: if the dog is left with anyone and the maid isn't there to control him, he'll bite. the dad can't be left with any of the daughters when the mom isn't there. likewise, the mom can't be trusted alone with either of the sons when the dad isn't there.

remember! only an adult can operate the boat, AND the boat can't drive itself.

classic weighing aha:!

this is a classic problem which i have heard many times before. this is the "harder" of the two problems, since in this one, you do not know if the invalid item weighs more or less than the others.

solving it is only half the battle. writing up a solution that anyone including your grandma could understand, is very hard.

problem: the evil king from before sends his own assassin to take care of the evil queen who tried to poison him. of course, her trusty guards catch the assassin before any harm is done. the queen notices that the assassin is quite handsome and doesn't really want to punish him by death. she decides to test his wisdom.

the queen gives the assassin 12 pills which are all completely identical in shape, smell, texture, size, except 1 pill has a different weight. the queen gives the man a balance and tells him that all the pills are deadly poison except for the pill of a different weight. the assassin can make three weighings and then must swallow the pill of his choice. if he lives, he will be sent back to the bad king's kingdom. if he dies, well, thats what you get for being an assassin.

only one pill is not poison and it is the pill which has a different weight. the assassin does not know if it weighs more or less than the other pills. how can he save his skin?

monty hall problem aha:!

another well known problem in probability is the monty hall problem.

you are presented with three doors (door 1, door 2, door 3). one door has a million dollars behind it. the other two have goats behind them. you do not know ahead of time what is behind any of the doors.

monty asks you to choose a door. you pick one of the doors and announce it. monty then counters by showing you one of the doors with a goat behind it and asks you if you would like to keep the door you chose, or switch to the other unknown door.

should you switch? if so, why? what is the probability if you don't switch? what is the probability if you do.

lots of people have heard this problem.. so just knowing what to do isn't sufficient. its the explanation that counts!

gold chain aha:!!!

a man has a gold chain with 7 links. he needs the service of a laborer for 7 days at a fee of one gold link per day. however, each day of work needs to be paid for separately. in other words, the worker must be paid each day after working and if the laborer is ever overpaid he will quit with the extra money. also he will never allow himself to be owed a link.

what is the fewest # of cuts to the chain to facilitate this arrangement and how does that guarantee payment?

surgeons aha:!!

a one armed surgeon with a hand wound needs to operate on three patients. the surgeon only has two gloves. how can he operate on the three patients in turn without risking exchange of fluids? (remember he only has one arm so he only needs to wear one glove at a time.)

clock aha:!

part I: what is the angle between the minute hand and the hour hand at 3:15 on an analog clock? no, its not 0.

part II: how often does the minute hand pass the hour hand on an analog clock?

mountain man aha:!

at 6 a.m. a man starts hiking a path up a mountain. he walks at a variable pace, resting occasionally, but never actually reversing his direction. at 6 p.m. he reaches the top. he camps out overnight. the next morning he wakes up at 6 a.m. and starts his descent down the mountain. again he walks down the path at a variable pace, resting occassionally, but always going downhill. at 6 p.m. he reaches the bottom. what is the probability that at some time during the second day, he is in the exact same spot he was in on the first day?

treasure island aha:!

you find an old treasure map in your grandma's attic. the map shows a cannon, a coconut tree, and a palm tree. the map states that to find the treasure you must:
a. start at the cannon, walk toward the palm tree while counting your paces. when you reach the palm tree, turn 90 degrees to your left and walk the same number of paces. mark that spot on the ground with a stake.
b. start at the cannon again, walk toward the coconut tree while counting your steps. when you reach the coconut tree, turn 90 degrees to your right and walk the same number of paces. mark that spot on the ground with a stake.
c. find the midpoint between the two stakes and dig for the treasure.

you set off in secrecy to the deserted island. upon reaching the shore you site the coconut tree and the palm tree, but someone has removed the cannon. without digging randomly all over the island, is it still possible to find the treasure?

screwy pirates aha:!

a. first i would just like to say i am so glad jenna got voted off survivor. yuck, i couldn't stand her ever since she accused that guy of eating beef jerky when he was chewing on grass.
b. recruit meyer on boot camp rocks. did you see how he made himself cry to get sympathy? and it worked! he is the funniest part of the show. i hope he wins.
c. i apologize for this site being soooooo slow. but that's why you get what you pay for. (i didn't pay anything so i shouldn't really expect anything in return.)
d. those screwy pirates are at it again. this time there are 13 pirates and they need to protect their treasure chest. they decide that they should only be able to open the chest if the majority (at least 7) agree that it should be opened. they ask a locksmith to come and put a specific number of locks on the safe. every lock must be opened to open the chest. there can be multiple keys for each lock, but each key only opens one lock (i.e. no skeleton keys). the locksmith can give more than one key to each pirate. how many locks should the locksmith use and what strategy should he use to distribute the keys, such that only when a majority of the pirates agree can the chest be opened?

ants on a triangle aha:!

there are three ants on a triangle, one at each corner. at a given moment in time, they all set off for a different corner at random. what is the probability that they don't collide?

one mile south aha:!!

how many places are there on the earth that one could walk one mile south, then one mile east, then one mile north and end up in the same spot? to be precise, let's assume the earth is a solid smooth sphere, so oceans and mountains and other such things do not exist. you can start at any point on the sphere and walk in any direction you like.

think you've figured it out? i'll tell you now, there is more than one. in fact, there are more than two. also be advised that walking north from the north pole (or south from the south pole) is illogical and therefore does not enter into the problem. all normal assumptions about directions will be used.

there are no tricks involved with this question. it just forces you to really think about the problem to come up with all the solutions.

cube aha:!

this is difficult to describe in words, so read this carefully, lest there be any confusion. you have a normal six sided cube. i give you six different colors that you can paint each side of the cube with (one color to each side). how many different cubes can you make?

different means that the cubes can not be rotated so that they look the same. this is important! if you give me two cubes and i can rotate them so that they appear identical in color, they are the same cube.

more hat puzzles aha:!

i buried four fishermen up to their necks in the sand on the beach at low tide for keeping their fishing spot a secret from me. i put a hat on each of their heads and told them that one of them must shout out the correct color of their own hat or they will all be drowned by the incoming tide. i give them 10 minutes to do this. fisherman A and B can only see the sand dune i erected. fisherman C can see that fisherman B has a white hat on. fisherman D can see that C has a black hat, and B has a white hat. the fisherman have been told that there are four hats, two white and two black, so they know that they must have either a white or a black hat on. who shouts out the color of their hat and how do they know?

coin on a table aha:!!!

you die and the devil says he'll let you go to heaven if you beat him in a game. the devil sits you down at a round table. he gives himself and you a huge pile of quarters. he says "ok, we'll take turns putting quarters down, no overlapping allowed, and the quarters must rest on the table surface. the first guy who can't put a quarter down loses." the devil says he wants to go first.

being the smart programmer you are, you realize that if the devil goes first, he may automatically win. so you convince him to let you go first, which makes your day because you know you can't lose. what is your winning strategy?

thanks to ole eichhorn

noodles aha:!

there is a pot of N noodles. (so there are 2N ends). a person randomly grabs two ends and merges them. the person keeps doing it, until there are no more noodles, (and only loops), left in the pot. what's the average number of loops in the pot?

heaven aha:!

a person dies, and arrives at the gate to heaven. there are three doors. one of them leads to heaven. another one leads to a 1-day stay at hell, and then back to the gate, and the other leads to a 2-day stay at hell, and then back to the gate. every time the person is back at the gate, the three doors are reshuffled. how long will it take the person to reach heaven?

this is a probability question - i.e. it is solvable and has nothing to do with religion, being sneaky, or how au dente the pasta might be ;-)

flipping coins aha:!

someone walks into your room and dumps a huge bag of quarters all over the floor. they spread them out so no quarters are on top of any other quarters. a robot then comes into the room and is programmed such that if it sees a head, it flips it to tails. if it sees a tail, it throws it in the air. the robot moves around randomly forever. will there be a convergence in distribution of heads vs. tails?

solution: flipping coins

Hmmm. I made a little math trick out of it. If the 'bot finds a head, it flips. If the bot finds a tail, there's a fifty percent chance this will become a head, as well.

(P_h = #heads/#coins, P_t = #tails/#coins)

So, delta h = -P_h + .5 P_t

= -(1 - P_t) + .5 P_t

= 1.5 P_t -1

Which is zero when P_t is 2/3. It's important to remember that a flip to a tail results in no change to the number of tails -- this threw me off for a second.

pennies aha:!!

i challenge you to a game. we each get one penny and we flip them at the same time. (so on turn 1, we each flip our respective pennies - turn 2, we flip them again, and so on until someone wins). i am looking to get heads then tails. you are looking to get heads then heads. so if you flip heads on any flip and then heads on the next flip, you win. if i flip heads on any flip and then tails on the next flip, i win. (its not a speed race, we both flip at the same time, except i'm only concerned with what appears on my coin, and you are only concerned with whats on your coin). are the odds fair? (obviously not, otherwise this wouldn't be a question). who has the advantage and why?

thanks rob

linked list aha:!!

how does one find a loop in a singly linked list in O(n) time using constant memory? you cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.)

last ball aha:!

you have 20 blue balls and 14 red balls in a bag. you put your hand in and remove 2 at a time. if they're of the same color, you add a blue ball to the bag. if they're of different colors, you add a red ball to the bag. (assume you have a big supply of blue & red balls for this purpose. note: when you take the two balls out, you don't put them back in, so the number of balls in the bag keeps decreasing). what will be the color of the last ball left in the bag?

once you tackle that, what if there are 20 blue balls and 13 red balls to start with?

thanks to vijay varanasi

coin rolls aha:!

every night, i dump all the change in my pocket into a big bucket.

when I buy things, i never hand over coins. always bills. so i accumulate a lot of coins. even if the purchase price is $1.01, and i have lots of coins in my pocket, i pay $2 and take the 99c in change. all the more coins to dump in my change bucket!

after about 10 years of this, i decide to roll all the coins into rolls. remember that a quarter roll is $10, a dime roll is $5, nickels $2, pennies 50 cents. so I go to the Banking Supply Store and buy empty paper rolls.

the Banking supply store, conveniently, sells assortment packs of coin rolls. each assortment pack contains W quarter rolls, X dime rolls, Y nickel rolls, and Z penny rolls.

the question: what is the optimum ratio of W to X to Y to Z to maximize the probability that I will use up the assortment packs at the same rate, e.g. without lots of leftover nickel tubes and stuff.

p.s. this problem should ideally be solved using Excel (but if you really like doing these things by hand, be my guest).

submitted by joel

paul brinkley makes these assumptions which are all good assumptions to make:
Assumption 1: The price of purchases made, modulo $1, is an even distribution from 0 cents to 99 cents.
Assumption 2: The cashier will always give you the least number of coins mathematically possible, and will always have enough of each type of coin to do this. So you'll never get 99 pennies as change for a $1.01 purchase, for example.
Assumption 3: Half dollars don't exist.

calendar cubes aha:!!!!

a man has two cubes on his desk. every day he arranges both cubes so that the front faces show the current day of the month. what numbers are on the faces of the cubes to allow this?

note the aha factor

boys and girls aha:!

in a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?

painfully easy aha:!

i flip a penny and a dime and hide the result from you. "one of the coins came up heads", i announce. what is the chance that the other coin also came up heads?

chinese emperor aha:!

A chinese emperor had to choose a new adviser amongst 3 sages, all of them equally wise. He placed a problem to them: "To choose one of you, you'll play a simple and fair game: In this sack there are 3 white balls and 2 black balls. Each of you will be blindfolded and will pick one ball and place it on your head. After that, the blindfolds will be removed and each one in turn will try to guess the colour of the ball upon his head, by observation of the other picked balls. However, beware. You may pass your turn in guessing, but if you state a colour and fail, you're disqualified. This way I'll learn which one is the most intelligent amongst you" The sages talked briefly to each other and promptly refused: "Dear lord, it's of no use, since the game is not fair. The last one of us to guess in the first round will know the answer." and the sages promptly demonstrated this to the emperor, who was so amazed by their wits that he appointed all 3 has his advisers. Could you demonstrated it ? NOTE: If the emperor had any wits at all he would have named them all advisers in the first place... maybe spending reduction ? :)

nuggets aha:!

you can go to a fast food restaurant to buy chicken nuggets in 6-pack, 9-pack or 20-packs. is there such a number N, such that for all numbers bigger than or equal to N, you can buy that number of chicken nuggets?

orbs aha:!

you have two identical crystal orbs. you need to figure out how high an orb can fall from a 100 story building before it breaks. you know nothing about the toughness of the orbs: they may be very fragile and break when dropped from the first floor, or they may be so tough that dropping them from the 100th floor doesn't even harm them.

what is the largest number of orb-drops you would ever have to do in order to find the right floor? (i.e. what's the most efficient way you could drop the orbs to find your answer?)

you are allowed to break both orbs, provided that in doing so you uniquely identify the correct floor.

salary aha:!

three coworkers would like to know their average salary. how can they do it, without disclosing their own salaries?

world series aha:!

you have $10,000 dollars to place a double-or-nothing bet on the Yankees in the World Series (max 7 games, series is over once a team wins 4 games).

unfortunately, you can only bet on each individual game, not the series as a whole. how much should you bet on each game, so that, if the yanks win the whole series, you expect to get 20k, and if they lose, you expect 0?

basically, you know that there may be between 4 and 7 games, and you need to decide on a strategy so that whenever the series is over, your final outcome is the same as an overall double-or-nothing bet on the series.

100 factorial aha:!

how many trailing zeroes are there in 100! (100 factorial)?

oil mogul aha:!

you are an oil mogul considering the purchase of drilling rights to an as yet unexplored tract of land.

the well's expected value to its current owners is uniformly distributed over [$1..$100]. (i.e., a 1% chance it's worth each value b/w $1..$100, inclusive).

bcause you have greater economies of scale than the current owners, the well will actually be worth 50% more to you than to them (but they don't know this).

the catch: although you must bid on the well before drilling starts (and hence, before the actual yield of the well is known), the current owner can wait until *after* the well's actual value is ascertained before accepting your bid or not.

what should you bid?

vienna aha:!!

it's the middle ages, you're travelling across europe and you want to find the way to vienna. you come to a crossroads, now there are two ways to go. at the crossroads stand a knight and a knave. the knight answers every question truthfully. the knave answers every question falsely. you don't know which guy is which. how can you figure out which road leads to Vienna by only asking one question?

duel aha:!!

you find yourself in a duel with two other gunmen. you shoot with 33% accuracy, and the other two shoot with 100% and 50% accuracy, respectively. the rules of the duel are one shot per-person per-round. the shooting order is from worst shooter to best shooter, so you go first, the 50% guy goes second, and the 100% guy goes third.

where or who should you shoot at in round 1?

hen aha:!!!

if a hen and a half lay an egg and a half in a day and a half, how many hens does it take to lay six eggs in six days?

mensa aha:!

if "24 H in a D" means "24 hours in a day", what does "26 L of the A" mean? what about the other 32 puzzles here on my mensa forward reproduction page?

box o' numbers aha:!

arrange the numbers 1 to 8 in the grid below such that adjacent numbers are not in adjacent boxes (horizontally, vertically, or diagonally).

 ___
 | 1 |
 =============
 | 6 | 4 | 3 |
 =============
 | 2 | 7 | 5 |
 =============
 | 8 |
 =====

the arrangement above, for example, is wrong because 3 & 4, 4 & 5, 6 & 7, and 7 & 8 are adjacent.

even harder coin problem aha:!

some of you may have easily solved the pill weighing problem posed here. if so you are going to love this problem.

it is similar but much more difficult.

from my buddy tom:

> ok, here's a tough one (i thought). there are no "aha!" tricks - it
> requires straightforward deductive-reasoning.
>
> you have 12 coins. one of them is counterfeit. all the good coins weigh
> the same, while the counterfeit one weights either more or less than a
> good coin.
>
> your task is to find the counterfeit coin using a balance-scale in 3
> weighs. moreover, you want to say whether the coin weighs more or less
> than is should and, and this is the real kicker, your weighs must be
> non-adaptive.
>
> that is, your choice of what to put on the balance for your
> second weigh cannot depend on the outcome of the first weigh and your
> decision about what to weigh for round 3 cannot depend on what happened on
> either your first or second weigh.
>
> for example, you can't say something like "take coin #1 and coin #2 and
> weigh them. if they balance, then take coins 3,4,5 and weight them
> against 6,7,8...if 1 and 2 don't balance, then weigh #1 vs #12..." you
> have to say something like:
>
> round #1: do this
> round #2: do this
> round #3: do this
>
> if the results are left tilt, balanced, and left tilt, respectively, then
> coin #11 is heavier than it should be.
>
> this problem is solveable...it took me about 1-2 hours of working on it to
> get it. i think even finding the counterfeit using an adaptive solution
> is tough. then non-adaptive constraint makes it quite hard and having to
> find whether it's heavier and lighter is cruel and unusual riddling ;-)
>
> have fun...

technical riddles aha:!!

You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once?

x implies y aha:!!

Part I

(you can't use paper, you have to figure it out in your head)

i have a black triangle, a white triangle, a black circle and a white circle.  if i gave you a shape (triangle or circle) and a color (black or white), the "frobby" items would be those that had either the shape or the color, but not both.  that is, in order to be frobby, the item must be of the specified color OR the specified shape, but not both the specified shape AND the specified color.  i'm thinking of a shape and a color in my head and i tell you that the white triangle is frobby.  can you tell me the "frobbiness" of the other items?

Part II

there are four cards which have a letter on one side and a number on the other side.  i lay them out and the cards appear as 2 5 F E.  the rule is that a card with an odd number on one side must have a vowel on the other.  what is the minimum number of cards you should turn over to prove the rule is true (and which cards would they be)?

XOR using NAND gates aha:!

I can't remember if I saw this on the discussion board or somewhere else...

Create an XOR gate using only NAND gates.  (BTW, mostly all circuit problems assume you have two inputs plus 0 and 1 also as inputs).

smart cookie aha:?

did you ever wonder how they make those pillsbury cookie dough rolls with the intricate faces inside them?  scroll about halfway down the page here and notice the intricate design they have somehow injected into their cookie rolls?  if you examine the roll closely there is no seam between the normal dough and the colored shape, but somehow they get that inside the roll.  i emailed them asking them how they do it and they told me it was "doughboy magic".

wanna play? aha:!

i offer to play a card game with you using a normal deck of 52 cards.  the rules of the game are that we will turn over two cards at a time.  if the cards are both black, they go into my pile.  if they are both red, they go into your pile.  if there is one red and one black, they go into the discard pile.  we repeat the two card flipping until we've gone through all 52 cards.  whoever has more cards in their pile at the end wins.  i win if there is a tie.  if you win, i pay you a dollar.  how much would you pay to play this game?

crazy guy on the airplane aha:!

"a line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.)

unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. if it is occupied, they will then find a free seat to sit in, at random.

what is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?"

chameleons aha:!

"at one point, a remote island's population of chameleons was divided as follows:

• 13 red chameleons
• 15 green chameleons
• 17 blue chameleons

each time two different colored chameleons would meet, they would change their color to the third one. (i.e.. If green meets red, they both change their color to blue.) is it ever possible for all chameleons to become the same color? why or why not?"

railroad bridge aha:!!

i got some new brain teasers and more classic programming puzzles for everyone!

a man needs to go through a train tunnel.  he starts through the tunnel and when he gets 1/4 the way through the tunnel, he hears the train whistle behind him. you don't know how far away the train is, or how fast it is going, (or how fast he is going).  all you know is that

1. if the man turns around and runs back the way he came, he will just barely make it out of the tunnel alive before the train hits him.

2. if the man keeps running through the tunnel, he will also just barely make it out of the tunnel alive before the train hits him.

assume the man runs the same speed whether he goes back to the start or continues on through the tunnel.  also assume that he accelerates to his top speed instantaneously.  assume the train misses him by an infintisimal amount and all those other reasonable assumptions that go along with puzzles like this so that some wanker doesn't say the problem isn't well defined.

how fast is the train going compared to the man?