What are some counter-intuitive results in mathematics that involve only finite objects? 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?

A proper coloring of a graph is an assignment of colors to its vertices in such a way that no two adjacent vertices share the same color.
The chromatic number of a graph is the minimum number of colors for which there is a proper coloring.
Any tree has chromatic number $2$ - imagine starting at a leaf and just alternating red-blue-red-blue.
The girth of a graph is the number of vertices in its smallest cycle. 
A tree has infinite girth, as it contains no cycles.
The tree example may cause you to think that large girth means small chromatic number. It seems plausible enough: A graph with large girth "looks like" a tree near any particular vertex, since it will be a long time before the edges leaving that vertex wrap back around to form a cycle. We therefore should be able to alternate red-blue-red-blue locally near a vertex, then just introduce a couple new colors to fix up the places where we get stuck.
Nothing of the sort! Erdős proved in 1959 using probabilistic techniques that there are graphs with arbitrarily high girth and chromatic number. In other words, that "treelike" appearance of high girth graphs has no ultimate control over chromatic number.
