Counterintuitive results for undergraduates I am looking for examples of results which go against people's intuition for a general audience talk. Results which if asked from non-experts "what does your intuition tell you?", almost all would get it wrong. Results' statement should be easily explainable to undergraduates in cs/math. I am mainly looking for results in computer science.

What are the most counterintuitive/unexpected results (of general interest) in your area?
For a general audience you have to stick to things that they can see. As soon as you start theorizing they'll start up their mobile phones.

Here are some ideas which could be worked out to complete examples:


There is a surface which has only one side.
A curve may fill an entire square.
There are constant width curves other than a circle.
It is possible to color the plane with three colors in such a way that every border point is a tri-border.


If you can rely on a bit of mathematical knowledge, you can do more:


There are as many odd numbers as there are natural numbers.
There is a continuous and nowhere differentiable function.
There is a function $f : \mathbb{R} \to \mathbb{R}$ which is discontinuous at all rational numbers and differentiable at all irrational numbers.
The Banach-Tarski "paradox".


For programmers you can try:


The impossible functionals: there is a program which takes a predicate p : stream → bool, where stream is the datatype of infinite binary sequences, and returns true if and only if p α is true for all streams α (that's uncountably many), and false otherwise.
It is possible to play poker by telephone in a trusted way which prevents cheating.
A group of people can calculate their average salary without anybody finding out any other person's salary.
There is a program which constructs a binary tree $T$ with the following properties:


the tree $T$ is infinite
there is no program that traces an infinite path in $T$