# 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?

• There are only five platonic solids. – D Wiggles Dec 2 '16 at 19:29
• @IBWiglin: I would call that an intriguing result rather than counter-intuitive. – Burak Dec 2 '16 at 19:31
• There are many at-first-counter-intuitive results in probability theory. Like so called Boy-Girl Paradox or Monty Hall Problem. – Levent Dec 2 '16 at 19:40
• ...and the birthday paradox. – Rahul Dec 2 '16 at 22:38
• @IBWiglin Because each corner has to be three elements, so hexagons and polygons with more sides are too big. More than five triangles, three squares or three pentagons are also too big. I find it counter-intuitive that that's the only criteria, that every corner that can be made makes a solid, but I'm pretty sure with physical pieces it would pretty obvious that there are five and only five platonic solids. – prosfilaes Dec 3 '16 at 20:21

Pick a couple of positive integers $a,b$ and make a tower of exponents with $a$, and find the value $\bmod b$. For example:

$21^{21^{21^{21}}} \bmod 31$

Now you don't need a very tall tower before extending it makes absolutely no difference to the result. I can replace the top $21$ there with any other positive integer, or (for effect) pile on more layers of exponents, and the answer doesn't change.

• Do you know/have bounds on how tall the tower needs to be, given $a$ and $b$? – Theoretical Economist Dec 20 '16 at 12:54
• $\log_2 b$ would be a quick upper bound, since the cycle must at minimum halve with each step up. – Joffan Dec 20 '16 at 13:17
• @Joffan is there a Hensel lift in there? – user334732 Nov 1 '17 at 11:46
• @RobertFrost not that I am aware - it's simply a consequence of the relatively rapid descent of the iterated Carmichael function. – Joffan Nov 2 '17 at 2:56
• @Joffan thanks for such an interesting function. I'm pretty sure the two are related although I'm a very long way from connecting the dots. – user334732 Nov 2 '17 at 9:03

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.

• ah the probabilistic techniques of graph theory really mess with my mind. – Jakob Dec 9 '16 at 14:53
• Using Erdos is cheating. – djechlin Dec 11 '16 at 2:06

One of the best (and most useful) is Benford's law which states that the leading digit of a randomly chosen number is not equally distributed among the radix. For example, in based 10, the value 9 will appear less often than any other digit in the highest place value position - in a "naturally occurring" population of numbers.

Say you wanted to analyse the accounts of a company to identify falsified data. If you found that some set of numbers (e.g. a set of invoices) contained the digits $0-9$ in roughly equal proportions in the highest place value, this would be a red flag that the data might have been falsely generated.

This is because place value grows logarithmically while a number's value is a linear function of the choice of any given digit, making low-valued digits such as $1$ more likely to lead.

• Why does place value grow logarithmically? Doesn't this depend on the distributional assumption which you make? – Epiousios Nov 1 '17 at 8:00
• @Epiousios yes it does. Any assumption that the leading digit is equally distributed among the radix, inherently implies that the distribution of your figures is not independent of the base in which you write them. – user334732 Nov 1 '17 at 11:38
• @Epiousios another way of looking at it is that the leading digit of any figure $x$ of length $n$ when written in base $b$ is conditional upon the magnitude of that figure $x$ being in the range $b^n-1\geq x\geq b^{n-1}$. So it's conditional upon a logarithmic assumption. – user334732 Nov 1 '17 at 11:44

Micha Perles's discovery of non-rational polytopes - combinatorial types of convex polytopes that cannot be realized with rational vertex coordinates.

Non-rational configurations, polytopes, and surfaces by Gunter Ziegler

$$()()$$ is not a palindrome but $$())($$ is.

Intuition tells us that if we can put a mirror in the centre and it reflects, then it's a palindrome. But because the mirror exchanges left brackets for right ones, our intuition deceives us in this particular instance.

Maybe not right on the money, but worth mentioning: (subtly) faulty dissections. For example, as shown here, it is seemingly possible to dissect an 8 x 8 square into a 5 x 13 rectangle.

## protected by Community♦Dec 3 '16 at 13:52

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).