Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math.
In order to show them the beauty of TCS, I'd like to gather some nice results/open questions coming from TCS which can easily be explained.
A good candidate for this purpose (IMHO) will be showing that the halting problem is not decidable. Another will be showing a lower bound on the running time of comparison based sorting (although that's a bit pushing it from what I expect them to understand).
I can also use the ideas from Explain P = NP problem to 10 year old, assuming some of them are unfamiliar with it.
So, questions has to be:
- Explainable with (at most) high school math.
- (preferably) not trivial enough to be shown in professional programming courses (for C++/Java/Web/etc.).