This recent article discusses the Post correspondence ^[1] principle.

1. http://en.wikipedia.org/wiki/N-body_problem , http://en.wikipedia.org/wiki/N-body_simulation
2. http://en.wikipedia.org/wiki/Dining_philosophers_problem
3. http://en.wikipedia.org/wiki/Cigarette_smokers_problem
4. http://en.wikipedia.org/wiki/Producers-consumers_problem
5. http://en.wikipedia.org/wiki/Readers-writers_problem
6. http://en.wikipedia.org/wiki/Sleeping_barber_problem
7. And finally a huge list on http://en.wikipedia.org/wiki/Computational_complexity_theory

I always liked the traveling salesman problem. I heard about this as a kid and more recently worked with a dispatch system that tried to solve this. The concepts are easy, but the solution is virtually infinite (given enough points). http://en.wikipedia.org/wiki/Travelling_salesman_problem.

What about the bin packing problem ^[1]? This problem is NP-hard, but it is is relatively easy to work out why this is the case. Think about a lorry or truck with boxes that must be put in to make the best use of the available space. Is it possible to find an optimal solution to this problem without resorting to brute force?

Here's a Stack Overflow question relating to it too: http://stackoverflow.com/questions/1170478/how-to-create-an-optimized-packaging-function-in-python

One interesting now-solved problem is the "four color theorem". It remained unproved from 1852 to 1976, and the remarkable fact was that it was THE FIRST theorem solved with computer help.

The statement is (veeery simple) "four colours is enough to paint a map in the plane such that no two bordering nations share the same color".

The article in Wikipedia is here http://en.wikipedia.org/wiki/Four_color_theorem

For sure it's not the answer you are looking for, but I think it is historically relevant.

You are equipped with two ropes and some matches.

Your goal is by burning the rope(s), to identify when exactly 45 minutes has passed. All you know about the ropes is:

• The ropes are of different length and you don't know how long they are.
• Each rope burns in precisely 1 hour.
• Each rope has a non-uniform density, meaning it is thicker at some points than others. Consequently, burning half a rope cannot be guaranteed to take 30 minutes.

It is more logical than anything else, I "heard" it was one of Microsoft recruitment question.

Sorting networks is a good one, IMHO. The concept of a sorting network is simple: You connect inputs which you want to compare and swap if one is bigger than the other, and what you want is to connect these inputs in such a way that the inputs are getting sorted with the least number of compares:

This turns out to be difficult, with some deep theory involved. For example, we don't know optimal networks with more than only 8 inputs! On the other hand, having these sort networks is a great thing because you can specialize a sorting algorithm for known array sizes into a optimal ladder of compares and swaps or build fast hardware sorter.

http://en.wikipedia.org/wiki/Sorting_network

A now solved, easy to understand but tough to solve problem is the PRIMES is in P ^[1] problem.

The problem: Is there a polynomial time algorithm to detect if a number is prime?

This was recently answered in the affirmative by the following paper: http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf

I think the most interesting problem is writing a program to pass the Turing test ^[1], because

• it requires a computer (as opposed to possibly being solved with just paper and pencil, like many proposed exercises that are really math problems),
• it's simple to state but has to be posed in prose (as opposed to being formulated in math terms),
• a solution would have tremendous consequences and applications,
• it includes many philosophical and not just practical hurdles,
• it's easy to pose but difficult to solve,
• many "toy" sub-solutions are available to experiment with,
• laypeople understand the problem (although maybe not why it's hard to solve) and can even test the solution,
• it's a problem that at first seems solvable but that quickly explodes in complexity as a solution is attempted,
• it's easy to restrict the domain (eg, only blocks on a table) to create a more-manageable subproblem,
• it's one of the oldest computer problems,
• it requires understanding of our own human nature and abilities,
• it's created tremendous debate for decades,
• there's $20,000 ^[2] riding on the problem.

Don't know if it is more mathematics or CS, but...

You have N boxes. In these boxes, you place the integers from 1 up, one at a time. You cannot put an integer in a box, if two integers in that box sum to it.

Now, find a closed formula for the first number that cannot be put in a box (or, if you prefer, the highest number that can be put into a box, before no other number can be added).

3SUM Hard problems ^[1].

Easy to understand:

Given three integer arrays A,B,C is there a better than quadratic (i.e sub-quadratic) algorithm which tells you if there are some a,b,c (a in A, etc) such that a+b=c?

A lot of problems in computational geometry have been shown to be 3SUM Hard, so it is not just interesting, but an important open problem. Check out the survey paper: http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf

I found this following question/riddle fascinating: seemingly impossible, but surprisingly simple when applying simple logic.

Two prisoners are called up by the king to play a game. Each of them will have a coin stuck on their forehead, so that each person can see the other's coin, but not their own. They are now each given one chance to guess what side the coin on their own head is.

If both of them get it right, they will be set free along with 1000 golds each.

If one of them gets it right, they will be both freed, but no gold will be given.

If no one gets it right, both will be executed.

What strategy should they use?

(answer is provided below the line)

The answer: person A says the side of coin on person B, and person B say the opposite side of coin on person A. They will always get one right, hence they are guaranteed to be freed.

The undecidability ^[1] of the halting problem ^[2]. That is, it's IMPOSSIBLE to construct an algorithm to tell if any given algorithm will eventually stop or will just run forever.

Understanding this is a very humbling enlightenment. Most people initially thought that this must be possible at first.

If you could shuffle a deck perfectly (so the resulting deck is exactly half of the original deck interleaved into the other half 1-by-1), how many shuffles would it take to get the deck back to its original state?

I find the integer factoring problem ^[1] quite interesting. Very simple to state and very difficult to solve.