How about Four-colour map theorem?:
http://en.wikipedia.org/wiki/Map_coloring
And its big brother, graph colouring:
http://en.wikipedia.org/wiki/Graph_coloring
Not strictly speaking puzzles, but they certainly have some game elements to them.
Not being a math person, I tend to think of programming languages as…languages. They are nothing more than another way to speak, except you are speaking to a machine.
This is why I don’t tend to get into many math puzzles, I prefer linguistics puzzles like cypher cracking and such.
Here’s some we had to do.
There are 35(?) soldiers at the MASH unit and Colonel Potter has 1 weekend pass. The soldiers will stand in a circle around him and count off. Every fifth one will be eliminated from the circle. The last man standing gets the pass to Seoul for the weekend. In what initial position does Max Clinger need to stand to get the pass?
One prof gave us the counterfeit coins problems for homework (12 coins, one is counterfeit and weighs slightly more or slightly less than the rest. Given a balance scale, determine the counterfeit in 3 weighings). I already knew the riddle, so I “solved” it easily. Then I wrote an inductive proof showing how many weighings would be needed for X number of coins. The teacher was so pleased that I had combined two parts of the class. I had never seen him happier.
In real software development world these days, I my opinion, Tower of Babel is more relevant example than Tower of hanoi!!
http://en.wikipedia.org/wiki/Tower_of_Babel
Jeff, I’m afraid what you say about the travelling salesman problem and P-versus-NP is garbled.
The travelling salesman problem is known to be NP-complete (and also NP-hard, which is implied by NP-complete). What would get you the Clay prize is proving either that P=NP (in which case the travelling salesman problem would be in P, because it’s in NP) or that P != NP (in which case the travelling salesman problem would not be in P, because it’s NP-hard). So it’s where TSP falls relative to class P, not relative to class NP, that you need to establish to win $1M.
(TSP is in class P iff you can always solve any instance of it in time that’s at most some_fixed_polynomial(n) where n is the number of places the salesman has to visit. A decision problem – one where the question is always “does there exist some configuration such that …?” – is in class NP iff the problem of checking a particular configuration is in class P. An optimization problem like TSP is said to be in class P, or class NP, or whatever, iff the problem “is the solution to the optimization problem at least …?” is always in P, or NP, or whatever. Given an efficient solution to that problem, you can then solve the optimization problem efficiently by binary search.)
Puzzles are a great way to find out how deep someone’s understanding of problem solving process really is.
However, today’s IT marketplace is flooded with automatons who are not hired to think or solve problems but to pound “templated code.” And then we hear how many people can’t write code. This is because they cannot think (for themselves) either.
Don’t forget the Little Schemer books on lisp. Lots of good examples on how to apply lisp and think through problems. “Schemer” refers to Scheme, a Lisp implementation (freely available) - for those who are not familiar with Lisp “marketplace.”
There is also a book called “How to move mountain Fiji?” which has a lot of puzzles from Microsoft interviews.
Place 99 blue marbles in the bucket of whites marbles and leave one blue marble by itself. There is now have 100% chance to pick the lone blue if they go to that bucket and 49.5% to pick a blue if they choose the mixed bucket.
Ran across the one recently.
ding ding ding!
And here I thought I was going to have to post the answer myself after the first couple got it wrong =]
The first computer problem I solved on my own - 25 years ago with lots of thinking at age 10 - was the towers from hanoi. I remember doing some experiments with coins and then coming up with a interative solution, not a recursive one. This made me somehow proud.
After programming for 25 years and solving lots of problems, I’m still proud of solving that problem as my first one on my own (there was no internet back then 
Peace
-stephan
CCP tested me not too long ago and prolly their most mind bending question was:
Given a list of of resister, return a value true or false wether a resistance can be met with any combination of resistors in series or parrallel circuit.
re: `Josh on September 14, 2007 01:08 AM … how important is engineering mathematics in software development these days?
I would say that graph theory and queuing theory are exceptionally valuable, even if the student does not remember the formulae afterwards. (They can always find them online) Many stupid system and network sizings are based on ignorance of even the concepts of these two subjects. And yes, sizing the target system, or developing software to fit in a target system are parts of the software development job.
In analyzing message error rates in communications systems where bit error probabilities are low (e.g. 1E-4) or very low (e.g. 1E-6), I have found it useful to use a few terms in a Taylor series. Even with double precision accuracy the message error rate as calculated by a spreadsheet for a 1400 byte message at a bit error rate of 1e-6 is likely to be way off. =1-(1-0.000001)^(1400*8)
One of my favorites, “Every programmer knows why sewer lids are round, but why are septic tank lids square?”
Another favorite:
- Pick a number between 1 and 9
- Subtract 5
- Multiply by 3
- Square the number
- Add the digits of that number together, for example, if you number is 83, you would add 8 and 3 and get 11.
- If the resulting number is less than 5, add five, otherwise subtract 4
- Multiply by 2
- Subtract 6
- Assign a letter to your number. A=1, B=2, C=3, D=4, E=5, etc
- Pick a country that begins with your letter
- Pick an animal that begins with the second letter from your country
- think of the color of that animal
Why are you thinking about a gray elephant in Denmark?
he decided that the way to get people to pay attention to your algorithm was to turn it into a story problem:
And that’s really the heart of this post, isn’t it? Tell a story if you want people to understand the problem.
The puzzles may have little to do with programming aptitude, and little relevance to any real-world situations. However (um, make that in italics ) these puzzles and the answers can show a lot about the candidate’s skills. It’s a way of getting the candidate a bit off-balance to see how he (or she) handles an unexpected situation.
There could be anything from ignorance, “Hanoi has towers?” to overconfidence, “Oh, that’s a trapdoor-knapsack problem. It’s unsolvable.” Whatever the initial answer, a few followup questions can give a clue to the interviewee’s problem-solving skills and ability to work with a team (in this case, the interviewer).
Which is why technical skills are often NOT the things you look for in a new employee. You assume the job skills are as stated on the resume, because you really can’t assess that outside a couple of months probationary period. What your need to determine in a short interview is the people skills: Can this person take instruction? Give instruction? Is he arrogant or cooperative?
Yeah, I know some coders could be fine locked in a windowless closet, with a pizza shoved through the slot at mealtimes, but most of us have to talk to other people. If you can’t be patient with an end-user and persuasive with a superior, The company may be better off with someone else.
This post makes me nostalgic and takes me back to those good old college days.
Though this problem does not come under any puzzle, recursion used to fascinate me a lot.
especially using Ackermans funtion to crash your computer !!.
I vaguely remembers there was a section on “Knights and Knaves” in this book. The knights always tell the truth while the knaves always lie.
Hey guys this is cool stuff
In NYU, I had a classmate keep asking me questions about how to accomplish things in constant time and constant memory, such as finding out whether a linked list contains a loop or not by using an algorithm with constant memory. I told him something along the lines of “test for a loop of length k by remembering the current link, then a loop of length k+1 from the current link, etc. until you get to the end of the list or find a loop”
Then he asked me how to implement a buffer that can have read, write and clear all in constant time. But you can use as much memory as you need. I said timestamp … but there was a better, more abstract way. I forgot what it was.
Where can I find more such puzzles?
AND HEY CHECK THIS MATHEMATICAL PUZZLE OUT. WHAT DO YOU THINK OF IT??
ENJOY,
GREG
and what kind of stupid problem is the two generals problem (as stated) … obviously if there is a chance all messengers get captured then this problem can never be solved in all cases. A 10 year old can see that.
hm
It’s actually an introduction to combinatory logic, not LC. The two are considered functionally equivalent but aren’t exactly the same.