237
$\begingroup$

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?

$\endgroup$
25
  • 79
    $\begingroup$ There are only five platonic solids. $\endgroup$
    – D Wiggles
    Dec 2, 2016 at 19:29
  • 11
    $\begingroup$ @IBWiglin: I would call that an intriguing result rather than counter-intuitive. $\endgroup$
    – Burak
    Dec 2, 2016 at 19:31
  • 35
    $\begingroup$ There are many at-first-counter-intuitive results in probability theory. Like so called Boy-Girl Paradox or Monty Hall Problem. $\endgroup$
    – Levent
    Dec 2, 2016 at 19:40
  • 24
    $\begingroup$ ...and the birthday paradox. $\endgroup$
    – user856
    Dec 2, 2016 at 22:38
  • 7
    $\begingroup$ @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. $\endgroup$
    – prosfilaes
    Dec 3, 2016 at 20:21

36 Answers 36

Reset to default
1
2
4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ ah the probabilistic techniques of graph theory really mess with my mind. $\endgroup$
    – Jakob
    Dec 9, 2016 at 14:53
  • 3
    $\begingroup$ Using Erdos is cheating. $\endgroup$
    – djechlin
    Dec 11, 2016 at 2:06
4
$\begingroup$

Not sure whether this is the kind of thing you were expecting, but here goes:

Some statements about constructive mathematics can seem very counter-intuitive (at first, this is probably because one is misinterpreting what they mean), e.g.:

  • the induction principle holds, but on the other hand: that every non-empty (or inhabited) set of naturals has a smallest element is in general false
  • given a set $A$, consider the statements: (i) "there is a finite set $B$ and an injection $A\to B$", (ii) "there is a finite set $B$ and a surjection $B\to A$". None of the statements imply each other or that $A$ is finite
$\endgroup$
8
  • 4
    $\begingroup$ Can you explain the first one? It looks like a simple negation of the well-ordering principle. I don't see any other way to interpret it. $\endgroup$
    – murgatroid99
    Dec 5, 2016 at 23:31
  • $\begingroup$ @murgatroid99 I don't know what you mean by "explain". In my second paragraph I meant: Even if you initially think it is surely true, you may have a faulty explanation. In the case of the well-ordering principle of integers something like: "Of course, you just increment an integer starting at $1$ until you land in the set" which doesn't work because it may be very hard to check that you are in this set. $\endgroup$
    – Stefan Perko
    Dec 6, 2016 at 8:27
  • 1
    $\begingroup$ I'm just trying to understand why that statement is false. Can you provide a counterexample, or a method of finding a counterexample, or some other proof that it's false. Even an explanation of why that statement is not actually equivalent to "the well ordering principle if false" would be helpful. $\endgroup$
    – murgatroid99
    Dec 6, 2016 at 8:53
  • 1
    $\begingroup$ I understand now. When I first read your post, I completely missed the part where you were operating under an unusual set of logical axioms, and that was the source of my confusion. $\endgroup$
    – murgatroid99
    Dec 6, 2016 at 16:15
  • 1
    $\begingroup$ For the first one, do you mean "false" or "not provable"? $\endgroup$
    – Theodore Norvell
    Dec 10, 2016 at 15:09
4
$\begingroup$

$()()$ 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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Why does place value grow logarithmically? Doesn't this depend on the distributional assumption which you make? $\endgroup$
    – Epiousios
    Nov 1, 2017 at 8:00
  • $\begingroup$ @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. $\endgroup$
    – it's a hire car baby
    Nov 1, 2017 at 11:38
  • $\begingroup$ @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. $\endgroup$
    – it's a hire car baby
    Nov 1, 2017 at 11:44
0
$\begingroup$

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

$\endgroup$
-4
$\begingroup$

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.

$\endgroup$
1
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .