Okay, here are some puzzles which I've heard gossiped about (answers are at the bottom of the page):

1. You can cut a 3 X 3 X 3 wooden cube into 9 - 1 X 1 X 1 cubes using 6 cuts of a knife, where a "cut" is defined as a slice through the cube that stays in the same plane. The puzzle is - come up with a way you achieve the same division using less than 6 cuts ? If you think it's not possible, try to prove why (not).
2. Five thieves - call them 1, 2, 3, 4, 5, have stolen $ 5 million from a bank. They devise a unique scheme of dividing up the money. First thief # 5 announces a division of the money among the 5; then all the five vote on the proposed division. If there are a majority of votes for the division, then everyone would take his share and go home. But if there is not a majority of votes for the proposed division, thief #5 would be killed by the rest 4, and the process would start all over again with thief #4 proposing a division among the 4 thieves left. No one abstains from voting and a tied vote is a vote against the proposed division (eg., if there are 4 thieves voting for thief #4's proposal, and 2 vote for, and 2 against, thief #4 dies). Given that all the thieves are rational and ultimately intelligent, and their priorities are strictly in the foll. order: 1. to get home alive, 2. to get as much money as possible, and 3. to kill as many other thieves as possible, how should thief # 5 propose to divide up the money ?
3. This is a famous one - a man starts from his hut (less than 10 ft square in size), goes one mile north, one mile east, then one mile south - this brings him back to his house (the same one he started from). He sees a bear running around in his backyard and drives it out. The questions - what is the color of the bear's skin, and why ?
4. If you thought #3 was a piece of cake, try this - how many other possible positions could the man's house be in (assume that houses can be built on the seas) ?
5. Can you obtain 24 using the numbers 1,3,4,6 once each and only the operations +,-,/,* ? (no tricks, like changing the base, etc. !)
6. Now try to obtain 24 from four 0's. This time you can use any valid mathematical operation.
7. A retiring dictator was asked who would succeed him. Being the sadist that he was, he answered "The father of my successor is my father's son". However, the dictator was known to have no sons or brothers. Who was the dictator's successor ?
8. You are given a pointer to the head of a singly linked list (i.e., no pointers to the predecessor element) that might (or might not) have a loop somewhere (i.e., an element pointing back to an element). The length of the list is finite, but unknown. Devise an algorithm that detects if there is a loop. The constraints are 1)  that your algorithm must use only constant amount of memory space (in other words, as you traverse the list, you can't just remember the entire set of elements you've seen along the way - you have to be more efficient), and 2) your algorithm must not destroy the list (i.e., the elements must be kept intact).

Answers:

1. You can't achieve a division into 9 - 1 X 1 X 1 cubes using less than 6 knife cuts. The proof is a simple one - the innermost 1 X 1 X 1 cube has 6 sides, and each of these sides needs a separate knife "cut" !
2. Thief # 5 gives 2 cents to each of 3 and {1 or 2}, keeping the rest for himself. If you have a different answer than this - if you've worked your way from the bottom (what if there were 2 thieves, what if there were 3 thieves and so on....), check if you haven't made a small mistake along the way. If you still believe your answer is right, email me at gupta@cs.cornell.edu.
3. The man lives at the south pole, so the bear is a (white) polar bear.
4. The house could be on any point one mile south of the north latitude that has a circumference of 1 mile (or equivalently, 1/2 mile, 1/3 rd mile ....). If you thought of this answer in response to puzzle #3, I bow to you.
5. 6/(1-3/4) = 24
6. ((0! + 0!)! + (0! + 0!)!)! = 24
7. Duh, his daughter ! If you're male, and you got this one, kudos !
8. Maintain a variable called 'count', and two pointers to elements that are separated by 'count' other elements. Initialize 'count' to 1, and keep incrementing it. If there is a loop of size=k, 'count' will eventually become a multiple of k after you enter the loop (as you're traversing the list). The loop is detected when the two pointers that you maintain are the same. If there is no loop, you will reach the end of the list.