There are many counter-intuitive results in mathematics, some of which are listed here. However, most of these theorems involve infinite objects and one can argue that the reason these results seem counter-intuitive is our intuition not working properly for infinite objects.
I am looking for examples of counter-intuitive theorems which involve only finite objects. Let me be clear about what I mean by "involving finite objects". The objects involved in the proposed examples should not contain an infinite amount of information. For example, a singleton consisting of a real number is a finite object, however, a real number simply encodes a sequence of natural numbers and hence contains an infinite amount of information. Thus the proposed examples should not mention any real numbers.
I would prefer to have statements which do not mention infinite sets at all. An example of such a counter-intuitive theorem would be the existence of non-transitive dice. On the other hand, allowing examples of the form $\forall n\ P(n)$ or $\exists n\ P(n)$ where $n$ ranges over some countable set and $P$ does not mention infinite sets would provide more flexibility to get nice answers.
What are some examples of such counter-intuitive theorems?
Best Answer
100 prisoners problem.
Citing Sedgewick and Flajolet, the problem reads as follows:
The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 drawers. The director randomly puts one prisoner's number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every prisoner finds his number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy—but may not communicate once the first prisoner enters to look in the drawers. What is the prisoners' best strategy?
Surprisingly, there exists a strategy with surviving probability more than 30%. It is connected to the fact---also non-intuitive---that a big random permutation is quite likely to contain "small" cycles only.