211
$\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$
  • 70
    $\begingroup$ There are only five platonic solids. $\endgroup$ – D Wiggles Dec 2 '16 at 19:29
  • 10
    $\begingroup$ @IBWiglin: I would call that an intriguing result rather than counter-intuitive. $\endgroup$ – Burak Dec 2 '16 at 19:31
  • 30
    $\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 '16 at 19:40
  • 19
    $\begingroup$ ...and the birthday paradox. $\endgroup$ – Rahul Dec 2 '16 at 22:38
  • 6
    $\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 '16 at 20:21

36 Answers 36

120
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ This is definitely counterintuitive! I would expect the best probability to be 2^-100 since it seems each prisoner would have a 50% chance of finding his number... $\endgroup$ – Mehrdad Dec 4 '16 at 4:24
  • 23
    $\begingroup$ @Mehrdad In fact, each prisoner has a 50% chance. Just that those events are not necessarily independent. $\endgroup$ – Peter Franek Dec 4 '16 at 10:37
  • 9
    $\begingroup$ @SimpleArt: Indeed they were. Unfortunately the first prisoner failed to find the correct number, so the prisoners are no longer. $\endgroup$ – Marc van Leeuwen Dec 5 '16 at 8:07
  • 10
    $\begingroup$ A variant of this was posted on puzzling stack exchange where a person before the beginning gets to swap two of the numbers in the drawers. If you allow for that the prisoners always survive. $\endgroup$ – DRF Dec 6 '16 at 11:18
  • 1
    $\begingroup$ @SimpleArt Or just one very smart and very convincing one :) $\endgroup$ – Henrik Dec 8 '16 at 17:34
107
$\begingroup$

The hydra game. Quote from the link:

A hydra is a finite tree, with a root at the bottom. The object of the game is to cut down the hydra to its root. At each step, you can cut off one of the heads, after which the hydra grows new heads according to the following rules:

If you cut off a head growing out of the root, the hydra does not grow any new heads.

Suppose you cut off a head like this:

http://math.andrej.com/wp-content/uploads/2008/02/hydra1.gif

Delete the head and its neck. Descend down by 1 from the node at which the neck was attached. Look at the subtree growing from the connection through which you just descended. Pick a natural number, say 3, and grow that many copies of that subtree, like this:

http://math.andrej.com/wp-content/uploads/2008/02/hydra2.gif

The counter-intuitive fact: you can always kill the hydra using any algorithm. The counter-intuitive meta-fact: You can't prove the theorem in PA.

$\endgroup$
  • 8
    $\begingroup$ My favourite! The best part is that it is unprovable using Peano arithmetic. $\endgroup$ – The Vee Dec 3 '16 at 22:54
  • 11
    $\begingroup$ Anyone try here for yourself to see how ridiculously fast it grows, yet you know if you're diligent enough, you can't lose. $\endgroup$ – The Vee Dec 3 '16 at 23:03
  • 7
    $\begingroup$ The first fact wasn't counter-intuitive to me. If you remove a head, then either you remove a level (by removing the last head on the topmost level), or you decrease the maximum size of branches on that level, or you decrease the number of branches of that size on that level, and hydras are well-ordered by those properties. (Proof sketch only) $\endgroup$ – immibis Dec 6 '16 at 2:29
  • 3
    $\begingroup$ @immibis: The problem is that you're tacitly assuming there's no limit ordinal, which is unprovable in PA. You could have 0, 1, 2, ..., omega, omega + 1, omega + 2, ... and that wouldn't violate any of the PA axioms. $\endgroup$ – Kevin Dec 6 '16 at 22:08
  • 7
    $\begingroup$ This is a variant of Goodstein's Theorem, where the trees are replaced by integers (in iterated exponential notation). Such results are "counter-intuitive" only if one is not familiar with ordinals (here $\,\varepsilon_0 = \omega^{\large \omega^{\omega^{\Large\cdot^{\cdot^\cdot}}}}\!\!\! =\, \sup \{ \omega,\, \omega^{\omega}\!,\, \omega^{\large \omega^{\omega}}\!,\, \omega^{\large \omega^{\omega^\omega}}\!,\, \dots\, \} ).\,$ The prior-linked post contains links to many accessible expositions on this and related topics. $\endgroup$ – Bill Dubuque Dec 7 '16 at 0:20
93
$\begingroup$

Suppose $X$ is any finite set, which will represent a set of voters, and let $Y$ be another finite set, representing decisions or options that the voters can rank. For example, voting on presidential candidates, favorite ice cream, etc. For simplicity, assume that $X=\{1,\ldots, N\}$.

Call a ranking to be a linear ordering on $Y$, and a social welfare function is a map $$F: L(Y)^N \to L(Y)$$ where $L(Y)$ is the set of all linear orderings on $Y$. $F$ essentially shows how to take the rankings of each voter and turn that into a single ranking. The elements of $L(Y)^N$ are an $N$-tuple of rankings, a ranking of $Y$ from each voter. We shall represent such a tuple by $(\leq_n)_{n=1}^N$ and its image by $F((\leq_n)_{n=1}^N)=\leq$.


Since this is to be a voting system, we probably want this to adhere to some rules which enforce the idea that $F$ accurately reflects the rankings of each voter:

  • Unanimity: If every voter ranks $a\in Y$ better than $b\in Y$, then in the output of $F$, society ranks $a$ higher than $b$. Formally, if $a\leq_n b$ for every $n$, then $a\leq b$.

  • Independence of Irrelevant Alternatives: How voters rank $a$ and $b$ should not effect how society ranks $a$ and $c\neq b$. Formally, if $(\leq_n)_{n=1}^N$ and $(\leq_n')_{n=1}^N$ are two tuples of rankings such that the ordering of $a$ and $c$ are the same for each $n$ (i.e. $a\leq_n c$ if and only if $a\leq_n' c$) then the ordering of $a$ and $c$ are the same in society's rankings (i.e. $a \leq c$ if and only if $a\leq' c$).

    Since this is a bit more involved, consider the example of a group ranking the three ice cream flavors of vanilla, chocolate, and strawberry. The group makes their choices, and $F$ says that the highest ranked flavor is chocolate. Then the group learns that strawberry is out, so they rank strawberry as last. It would be counter-intuitive, then, to suspect that all of a sudden vanilla becomes ranked highest (but there are such functions making this true).

    The intuition is the hope that the group's consensus on how it feels about two options should only depend on how each individual feels about those two options.

    Cases where this still fails are usually indicative of cases where the voting scheme can be gamed in some way, i.e. by voting against your favorite option to avoid your least favorite option or by varying how you rank the remaining options to guarantee their loss.

    A good ranked voting system should be such that you benefit most by actually saying what you really think, than attempting to game the system. The failure of Independence of Irrelevant Alternatives allows for this gaming.


This bring's us to our result:

Arrow's Impossibility Theorem: For $Y$ finite and $|Y|> 2$, the only function $F: L(Y)^N \to L(Y)$ satisfying the above two properties is a dictatorship, i.e. there is a fixed $m$ (which depends only on $F$) such that $1\leq m\leq N$ and $F((\leq_n)_{n=1}^N) = \leq_m$.

One method of proof is by considering filters and using the fact that the only ultrafilters on a finite set are the principal ultrafilters.

It is important to note that Arrow's Impossibility Theorem only applies to ranking systems. There are alternatives ways of voting which are not ranking systems and show more promise.

Moreover, whether the hypothesis of the Independence of Irrelevant Alternatives actually captures what we want in all cases is suspect.

$\endgroup$
  • 8
    $\begingroup$ Why do you consider this result to be counterintuitive? It is surprising, yes, but I don't see what intuition would suggest existence of such a system. $\endgroup$ – Wojowu Dec 2 '16 at 21:16
  • 14
    $\begingroup$ @Wojowu I would say it is counter-intuitive in that our intuition - perhaps more due to social upbringing rather than a mathematical intuition - makes it seem like many voting systems that are used in the world should be well-behaved (until you actually start creating example scenarios). Another aspect is because the conditions seem like common-sense. That we find it so obvious that these are properties we want usually makes it seem like they should naturally occur in some non-trivial examples. $\endgroup$ – Hayden Dec 2 '16 at 21:24
  • 6
    $\begingroup$ @Wojowu because it seems like a bunch of people can get together and vote on something without someone always inviting Hitler. $\endgroup$ – djechlin Dec 3 '16 at 6:18
  • 9
    $\begingroup$ @user347489 Perhaps I misphrased it. $m$ is a fixed value dependent on $F$. Once $F$ is chosen, there is a single voter which always gets their way. I would describe that as a dictatorship. $\endgroup$ – Hayden Dec 4 '16 at 14:52
  • 6
    $\begingroup$ Note that Arrow's theorem deals with a deterministic $F$. If you relax that requirement and allow $F$ to map to a random variable, a trivial observation is that "random dictatorship" (choosing a random individual and taking their preference orer to be the group preference order) is what comes out, and it's an interesting thought experiment whether such a system would produce reasonable/acceptable results. $\endgroup$ – R.. Dec 5 '16 at 3:39
75
$\begingroup$

Closed-form formulas exist for solutions of polynomials up to degree 4, but not more than that.

Only 4 colors are required to color a map of any size, with adjacent areas being distinct colors.

Division rings over the reals have a maximum of 4 dimensions, and cannot have more.

Having more than three regular convex polytypes is a property of dimensions only up to 4.

$\endgroup$
  • 17
    $\begingroup$ I think the fact that some roots of some degree 5+ polynomials cannot be expressed with algebraic operations is even more interesting. $\endgroup$ – Serge Seredenko Dec 3 '16 at 5:53
  • 5
    $\begingroup$ This might be interesting as well: en.wikipedia.org/wiki/Exotic_R4 $\endgroup$ – polfosol Dec 3 '16 at 8:28
  • 7
    $\begingroup$ For polynomials you, might need to add "solutions by radicals." There might be closed form solutions for degree 5 in terms of transcendental functions, say. Also, I would not consider division algebras over the reals "finite objects." $\endgroup$ – Kimball Dec 3 '16 at 16:48
  • 2
    $\begingroup$ @IwillnotexistIdonotexist : Not all algebraic numbers can be expressed using algebraic operations (addition, subtraction, multiplication, division, and positive integral roots) applied to rational numbers (or integers, since division makes the distinction not a difference). Only algebraic roots whose minimal polynomial has a solvable Galois group can be (i.e., only those that live in a tower of simple algebraic field extensions of $\Bbb{Q}$) "Most" fifth and higher degree polynomials do not have solvable Galois groups, so cannot be expressed with algebraic operations on rationals. $\endgroup$ – Eric Towers Dec 4 '16 at 2:20
  • 2
    $\begingroup$ @Burak: you can replace "real numbers" with "real closed field," and e.g. the real algebraic numbers (of which there are countable many) are a real closed field. So this example doesn't really have anything to do with the real numbers per se, and in particular is not connected to how it takes an infinite amount of information to specify an arbitrary real number (which was the OP's objection to using the real numbers as examples). $\endgroup$ – Daniel McLaury Dec 5 '16 at 14:47
69
$\begingroup$

Simpson's Paradox.

Gender discrimination example. A university has only two graduate departments — Math and English. Men and women apply to both departments, with varying admit rates, as summarized in the table below.

Each department is more likely to admit women than men. But when aggregated, the university as a whole is more likely to admit men than women (and thus open to charges of gender discrimination)!

enter image description here

Drug testing example. We recycle the exact same numbers from before to a context in which the paradox seems even more paradoxical.

There are 300 male patients and 300 female patients suffering from some illness. 200 of the males and 100 of the females receive the new experimental drug. The recovery rates are as given in the table below.

The conclusion from this trial is that if we know the patient is male or female, we should not administer the drug. But absurdly, if we do not know whether the patient is male or female, we should!

enter image description here


For more, see Pearl (2014), who "safely proclaim[s] Simpson’s paradox 'resolved.'”

P.S. Simpson's Paradox illustrates both the fallacy of composition ("what is true of the parts must also be true of the whole") and the fallacy of division ("what is true of the whole must also be true of the parts").

$\endgroup$
  • 26
    $\begingroup$ After staring at this for ten minutes, I think I understand the electoral college. $\endgroup$ – Mauser Dec 7 '16 at 20:26
  • 7
    $\begingroup$ Isn't that how the US election system works? $\endgroup$ – Tobias Kienzler Dec 8 '16 at 13:45
  • 6
    $\begingroup$ Of course they are open to charges of gender discrimination: women are twice as likely to get admitted to the English department. That seems like a pretty strong bias. $\endgroup$ – tomasz Dec 8 '16 at 13:58
  • 4
    $\begingroup$ @mbomb007 Thanks for the link. I understand how it works. I was making a little bit of a joke, but with some truth behind it, and not intending to belittle the institution. This fallacy of composition warns against aggregating dissimilar data, as information, perhaps critical information, will be destroyed upon the aggregation. This same concern was perhaps involved in the development of that process as well. $\endgroup$ – Mauser Dec 8 '16 at 22:18
  • 7
    $\begingroup$ @tomasz: Didn't you know that gender discrimination can only ever be against women? =) $\endgroup$ – Kenny LJ Dec 10 '16 at 1:46
59
$\begingroup$

I feel like the Monty Hall problem is counter-intuitive the first time you see it.

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door (say No. 1). Then the host, who knows what's behind all the doors, opens another door (say No. 3) that is guaranteed to have a goat. He then says to you, "Do you want to now pick door No. 2?" Is it to your advantage to switch your choice?

The answer is yes, you should ALWAYS switch your choice. The reasoning is as follows: at the beginning you have a $1$ in $3$ chance of selecting the correct door. After the host shows you another door, there are only $2$ doors to select from there. You initially chose the first door which had a probability of $1/3$ of being the correct door. Now, because all the probabilities within a set of choices must always add to $1$, we can conclude that the 2nd door is correct with a probability of $2/3$. So indeed, switching your guess is to your advantage.

$\endgroup$
  • 4
    $\begingroup$ The really fun part with the Monty Hall problem is what happens when you slightly alter the rules, but the situation sounds practically identical. You modify it like this - what happens if Monty chooses one of the other two doors at random to reveal (and if it's the car, you're out of luck)... and he reveals a goat? $\endgroup$ – Glen O Dec 3 '16 at 7:15
  • 16
    $\begingroup$ There are some instances in which you'd better stay with the first choice xkcd.com/1282 $\endgroup$ – Del Dec 3 '16 at 10:22
  • 13
    $\begingroup$ Under this formulation of the question, you do not know if it is better to switch. You also need to know the information that the host will never open the door with the car. Just because he knows what's behind a door does not necessarily imply he will not open a door with a car. $\endgroup$ – David Stone Dec 4 '16 at 18:38
  • 13
    $\begingroup$ @NoseKnowsAll that doesn't clear it up. You still need to specify the hosts motivations. Consider an evil monty who only gives you the option to switch if you selected the car on your first pick (and immediately declares you a loser if you picked either goat). $\endgroup$ – Steve Cox Dec 5 '16 at 19:30
  • 4
    $\begingroup$ I'm divided on how to react to this answer, since on the one hand I don't like to see this defective formulation of the problem propagated, but on the other hand the Monty Hall problem (correctly understood) is a really good example of a counterintuitive result. $\endgroup$ – David K Dec 7 '16 at 22:06
48
$\begingroup$

Monsky's theorem is easy enough to state for anyone to understand, yet arguably counter-intuitive.

Monsky's theorem states that it is not possible to dissect a square into an odd number of triangles of equal area. In other words, a square does not have an odd equidissection.

The problem was posed by Fred Richman in the American Mathematical Monthly in 1965, and was proved by Paul Monsky in 1970.

$\endgroup$
  • 24
    $\begingroup$ It seems pretty intuitive to me. That means that my intuition is either really great or specatacularly terrible. $\endgroup$ – user159517 Dec 3 '16 at 1:22
  • 5
    $\begingroup$ @user159517 Hat's off to that, it's not at all intuitive to me. Same goes for the equivalent result about polyominoes, or centrally symmetric polygons. $\endgroup$ – dxiv Dec 3 '16 at 1:50
  • 11
    $\begingroup$ @user159517: I felt the same on first glance, and then realised I’d fallen into the “spectacularly bad” camp: I’d been picturing it with just lattice-aligned right-angled triangles. $\endgroup$ – Peter LeFanu Lumsdaine Dec 3 '16 at 19:20
  • 2
    $\begingroup$ +1, although this raises the question whether "mathematics that involve only finite objects" excludes things dealing with continuity/topology... I believe Monsky's theorem deals with 2-adic numbers and their topology. $\endgroup$ – Matthew11 Dec 4 '16 at 4:45
  • 2
    $\begingroup$ @xI_hate_math420x The proof, maybe, but not the statement of the theorem. $\endgroup$ – Akiva Weinberger Dec 5 '16 at 15:59
43
$\begingroup$

Stacking Books on a Table Edge

Given a rigid (non-deformable), flat, horizontal surface (e.g., a table), a rigid rectangular parallelepiped (e.g., a block, like a book or a brick) can be placed on the edge of the table so that $49.\overline9\%$ of its weight overhangs the edge:

       one book

Assume that you have a very large supply of identical books.  By moving the first book back toward the center of the table (i.e., away from the edge), you can put a second book on top of the first book so that $74.\overline9\%$ of its weight overhangs the edge:

       two books

By adding more and more books, you can get the top one completely beyond the edge of the table — in fact, as far beyond as you want:

six books

This is discussed (and illustrated much better) at Wolfram MathWorld.
Spoiler alert: it boils down to the fact that $$\sum_k\frac1k$$ grows without bound.

$\endgroup$
  • 4
    $\begingroup$ It's too bad there are no rigid surfaces in the world, and they all bend somewhat, which is why we can't really try this at home. $\endgroup$ – einpoklum Dec 4 '16 at 23:35
  • 11
    $\begingroup$ What I find counterintuitive is that you can do a lot better. The method given here gets an overhang on the order of $\log n$, but you can achieve on the order of $n^{1/3}$. This is mentioned at the MathWorld page, but see also maa.org/sites/default/files/pdf/upload_library/22/Robbins/… $\endgroup$ – Gerry Myerson Dec 5 '16 at 8:44
  • 41
    $\begingroup$ I feel like that last image is highly misleading. While it's possible to get 1 block completely past the edge of the table, the arrangement of the other blocks below it would not look like that. $\endgroup$ – Shufflepants Dec 5 '16 at 16:41
  • 14
    $\begingroup$ Why "$49.\overline{9}\%$" and "$74.\overline{9}\%$" instead of just 50% and 75%? $\endgroup$ – anomaly Dec 7 '16 at 16:43
  • 14
    $\begingroup$ But $49.\overline9 = 50$, so you have created exactly the same unstable situation you wanted to avoid. You might instead write, "$0.5 - \delta_1,$ where $\delta_1$ is a small positive number." $\endgroup$ – David K Dec 7 '16 at 22:09
39
$\begingroup$

What surprised me most was the following Arab story.

An inheritance of $35$ camels had to be distributed among $3$ brothers as follows: half for the elder, the third for the second and the ninth for the younger. The problem was that the brothers would then have to receive more than $17$ and less than $18$, more than $11$ and less than $12$, more than $3$ and less than $4$ respectively.

"The man who calculated" solved the problem by asking a friend to lend him a camel with which he obtained $36$ camels to distribute following the instructions of the deceased father. Then the brothers received $18$, $12$ and $4$ camels respectively, i.e. more than they had planned so they were very satisfied.

But then the “man who calculated" distributed $34$ camels so that in addition to returning the camel loaned by his friend had for himself a camel as a reward for his calculations.

It was several years after I read this story that I could explain mathematically what happened.

$\endgroup$
  • 2
    $\begingroup$ I read 'the man who counted' a long time ago, and this segment has remained with me the whole time. $\endgroup$ – Liam Dec 2 '16 at 22:30
  • 25
    $\begingroup$ $1/2 + 1/3 + 1/9 = 17/18$. I have no idea why the brothers would not accept extras if there had been no camel lent, but if they did, they wouldn't have needed to borrow anything. $\endgroup$ – John Dvorak Dec 3 '16 at 8:18
  • 5
    $\begingroup$ @JanDvorak Well then they would fight over who got the extra, of course. $\endgroup$ – Kimball Dec 3 '16 at 16:44
  • 4
    $\begingroup$ @JanDvorak: psychologically it works because borrowing the camel makes it clear to the brothers that they are receiving the "extra" in exact proportion to their "rightful share". If you just told them "take 18/12/4" then you still have to demonstrate that you haven't unfairly given more extra to one than to the other, just to make round numbers. The number 36 likely will feature somewhere in this demonstration. You don't really need the physical camel to do that, of course, but it does make it easier, and the brothers aren't good with fractions. $\endgroup$ – Steve Jessop Dec 4 '16 at 15:49
  • 19
    $\begingroup$ How is this an example of a counter-intuitive theorem? The fact that $1/2 + 1/3 + 1/9 \neq 1$ doesn't seem so strange to me. $\endgroup$ – JiK Dec 5 '16 at 13:36
36
$\begingroup$

There's this game about paying taxes that I saw in Yale's open course on game theory. link

We have tax payers and a tax-collecting agency. The tax payers can choose whether to cheat paying $0$ or not cheat paying $a$. The agency can choose whether to check whether someone has paid tax. If someone cheats and the agency finds out, he'll have to pay $a$ to the agency and a fine $f$ that doesn't go to the agency. To check each tax payer, the agency has to spend $c$. $c$ is less than $a$. The payoff matrix is as follows:

                          Tax Payer
                      Cheat      Not Cheat
                 +-------------+-----------+
         Check   | (a-c, -a-f) | (a-c, -a) |
Agency           +-------------+-----------+
       Not Check |   (0, 0)    |  (a, -a)  |
                 +-------------+-----------+

One's intuition may suggest that as $f$ increases, tax payers will cheat less often. But solving for the Nash equilibrium tells us that in an equilibrium, as $f$ increases, the probability a tax payer cheats doesn't change, but the agency will check less often. Maybe the tax payer will cheat less often and the agency will check at the same probability when $f$ has just changed, but given enough time, rational tax payers and agency will play the Nash equilibrium.

The Nash equilibrium is that the tax payer cheats at a probability of $\frac c a$, and the agency checks at a probability of $\frac a {f+a}$. The tax payer's expected payoff is $-a$. The agency's expected payoff is $a-c$.

$\endgroup$
  • 2
    $\begingroup$ So the moral of the story is that you shouldn't let the IRS keep 100% of taxes levied, they should have to hand some of it over to the treasury? ;-) $\endgroup$ – Steve Jessop Dec 4 '16 at 16:09
  • $\begingroup$ Even though f shouldn't affect the agency in any way whatsoever... $\endgroup$ – immibis Dec 6 '16 at 2:35
  • $\begingroup$ @immibis - and c shouldn't affect the taxpayer (or tax cheat) whatsoever, either. Interesting, though, that the expected payoff for both the taxpayer and the agency is independent of the fine itself. $\endgroup$ – Glen O Dec 6 '16 at 5:54
  • 4
    $\begingroup$ Since I posted the last comment I had an epiphany of how this can be the case (intuitively; I still haven't bothered to do the maths). If the fine increases then less people want to cheat, so now the agency is wasting their money doing so many checks for so few cheaters, so they do less checks (which increases the number of cheaters again). $\endgroup$ – immibis Dec 6 '16 at 7:53
  • 1
    $\begingroup$ This doesn't seem counter-intuitive. If the fine increases, then the agency will not need to check as much in order to enforce a level of compliance which they are happy with. $\endgroup$ – jwg Dec 8 '16 at 12:01
32
$\begingroup$

The fallacy of the hot hand fallacy

Suppose you'd like to detect whether a coin ever goes on hot streaks or cold streaks, so that after $k$ heads in a row, the probability of the following flip coming up heads is different from the overall probability $p$ of a heads. To test this, you'll flip the coin $n$ times, and after any streak of $k$ heads, you'll record the outcome of the following flip. Let $X$ be the percentage of your recorded flips that came up heads. For concreteness, let's set the values at $p=\frac{1}{2}$, $n=100$, and $k=3$.

Here is the surprise: for these values, $E[X]\approx0.46$ (not $\frac{1}{2}$!!!!). And, in general for any $0<p<1$, $n\geq 3$, and $0<k<n$, $E[X]<p$, and the bias can be quite large for certain values of $n$ and $k$.

This is counterintuitive enough that when Gilovich, Vallone and Tversky wrote their seminal paper Hot Hand In Basketball in 1985 measuring whether basketball players went on "hot streaks", they used the exact method above to attempt to detect hot streaks, and since the percentage after three hits in a row was not different from the overall percentage, they concluded that there was no evidence of a hot hand. But this was a mistake! If there was no hot hand, they should have observed a significantly lower percentage on shots after three hits in a row. In fact, their data do show evidence for a hot hand in many of the cases, according to a new paper last month. This mistake went unchecked for 30 years, with untold numbers pop psychology books and articles citing the result as evidence for a "hot-hand fallacy".

Demonstration

Here's a demonstration in R.

f7 <- function(x){ 
  # running total of run length
  # stolen from http://tolstoy.newcastle.edu.au/R/e4/devel/08/04/1206.html
  tmp <- cumsum(x)
  tmp - cummax((!x)*tmp)
  }      

streak <- function(v, k = 3, n = length(v)) {
  # returns a vector of length n = length(v) this is TRUE when the last k
  # entires are True
  c(FALSE, f7(v)[1:(n-1)] >= k)
}

random_shots <- function(n, p = 0.5) {
# takes n random shots with probability p of success
  runif(n) < p
}

trial <- function(n, k = 3, p = 0.5) {
  s <- random_shots(n, p) 
  mean(s[streak(s, k)])
}

# do simulation 100000 times
results <- sapply(1:100000, function(x) trial(100, 3))
summary(results)
#    Min. 1st Qu.  Median    Mean 3rd Qu.    Max.    NA's 
#  0.0000  0.3636  0.5000  0.4615  0.5714  0.8571       3 

What's going on?

One way to see it is to consider the absolute simplest case, where we flip the coin three times, and tally up the flips after a single head in a row.

Outcome   Heads   Flips   Proportion
HHH       2       2       1
HHT       1       2       1/2
HTH       0       1       0
HTT       0       1       0
THH       1       1       1
THT       0       1       0
TTH       0       0       NA
TTT       0       0       NA

The last two outcomes, of course, can't be included in our tally because the proportion of heads is undefined. Now, if we repeat this experiment many times, we'll find that of the sequences that we record, $\frac{2}{6}$ of the time we will have a proportion of $1$, while $\frac{1}{6}$ of the time we'll have $\frac{1}{2}$, for an expected proportion of $$\frac{2}{6}\times{1} + \frac{1}{6}\times\frac{1}{2} = \frac{5}{12} < \frac{1}{2}$$

So, by inspection we can plainly see that in this case the expected proportion is less than 0.5, although at first glance this might still seem unsatisfactory. Yeah, it's less than 0.5 but... why?

I think there are a few ways to hand-wave about this. One has to do with the fact that we have two outcomes with proportion = $1$, but one of those ways has two heads, and the other only has one. So sequences with more heads are weighted the same as sequences with fewer heads, and in this way heads are somehow being underrepresented, leading to the bias.

$\endgroup$
  • 7
    $\begingroup$ So gambler's fallacy is (kind of) true? How come $E[X] \approx 0.46$? $\endgroup$ – Jasper Dec 5 '16 at 12:20
  • 5
    $\begingroup$ To my understanding that's because the samples are allowed to "overlap", and to correct for it, HHHH should only count as two HH pairs, not three. (After seeing an H, or k consecutive H's), you should record the next flip and reset your counter of consecutive H's. $\endgroup$ – immibis Dec 6 '16 at 2:57
  • 4
    $\begingroup$ I've figured out part of what's going on. Suppose (as written in this answer) that you flip a fair coin 100 times, and after any streak of 3 heads (with overlaps permitted), you record the outcome of the following flip. Let $A$ be the number of flips that you record, and let $H$ be the number of those which are heads. As expected, $E[H]/E[A] = 1/2$. Part of the reason that $E[H/A] \neq 1/2$ is that $A$ and $H$ are not independent variables. The flips in a heads-heavy trial run "matter less" than the flips in a tails-heavy trial run. $\endgroup$ – Tanner Swett Dec 6 '16 at 4:01
  • $\begingroup$ It's worth noting that as you increase the number of trial runs, $E[x]$ gets closer to $1/2$. While at 100 runs $E[x]\approx 0.46$, at 10,000 runs $E[x]\approx 0.499$. This is based only on experimental runs from the given R program, I didn't actually do the math $\endgroup$ – rtpax Dec 10 '16 at 22:42
  • $\begingroup$ This is related to this post, which explains the intuition in a different way: math.stackexchange.com/questions/2317508/… $\endgroup$ – Joshua B. Miller Nov 13 '17 at 6:51
28
$\begingroup$

Here is a consequence of the Arc sine law for last visits. Let's assume playing with a fair coin.

Theorem (false) In a long coin-tossing game each player will be on the winning side for about half the time, and the lead will pass not infrequently from one player to the other.

The following text is from the classic An Introduction to Probability Theory and Its Applications, volume 1, by William Feller.

  • According to widespread beliefs a so-called law of averages should ensure the Theorem above. But, in fact this theorem is wrong and contrary to the usual belief the following holds:

    With probability $\frac{1}{2}$ no equalization occurred in the second half of the game regardless of the length of the game. Furthermore, the probabilities near the end point are greatest.

In fact this leads to the Arc sine law for last visits (see e.g. Vol 1, ch.3, section 4, Theorem 1).

Remarkable statements cited from Chapter III: Fluctuations in Coin Tossing and Random Walks:

  • For example, in various applications it is assumed, that observations on an individual coin-tossing game during a long time interval will yield the same statistical characteristics as the observation of the results of a huge number of independent games at one given instant. This is not so.

and later on:

  • Anyhow, it stands to reason that if even the simple coin-tossing game leads to paradoxical results that contradict our intuition, the latter cannot serve as a reliable guide in more complicated situations.

An example:

Suppose that a great many coin-tossing games are conducted simultaneously at the rate of one per second, day and night, for a whole year. On the average, in one out of ten games the last equalization will occur before $9$ days have passed, and the lead will not change during the following $356$ days. In one out of twenty cases the last equalization takes place within $2\frac{1}{4}$ days, and in one out of a hundred cases it occurs within the first $2$ hours and $10$ minutes.

$\endgroup$
  • 1
    $\begingroup$ just started reading this as finally had some time on hands. looking forward to that chapter! $\endgroup$ – Mehness Dec 3 '16 at 23:34
  • 1
    $\begingroup$ I would think about this like a random walk. The walk could cross the y-axis often, but it's just as likely it's wandered off to one half or the other $\endgroup$ – Dylan Frese Dec 7 '16 at 1:08
  • 2
    $\begingroup$ Out of context, depending on which statistics you look at, the statement about "the results of a huge number of independent games at one given instant" seems either trivial (the lead can change during a series of games, but not during a number of simultaneous games) or untrue (if there are $N$ games in either case and $X$ is the total number of heads, how does sequence vs. simultaneous affect the moments of $X$?). I presume there was some discussion prior to that statement that explains it better. $\endgroup$ – David K Dec 7 '16 at 22:22
  • 1
    $\begingroup$ @DavidK: If I understand correctly, what it's saying is this: if you gather scores of a single long-running game after every N flips, you'll get a very different distribution than if you gather scores of many independent games of N flips. In the long-running game, you might expect that scores will tend to stay near 0 (so that scores < -N or > N, while possible, are extremely unlikely, so don't affect the overall shape of the distribution), but in fact scores far from 0 are quite likely. $\endgroup$ – ruakh Dec 10 '16 at 23:53
  • 1
    $\begingroup$ Perhaps the purpose of the statement about "various applications" was meant to be provocative, to motivate someone to read the chapter. (It worked for me, anyway!) It may be that its exact meaning was never intended to be explained. Certainly the rest of the chapter contains many very well-explained, precise statements that are also surprising or indicative of fallacies, including a questionable inference by Galton in 1876 (page 70). On page 88, "even trained statisticians expect" the lead in the sequential game to change far more often than it actually is likely to. $\endgroup$ – David K Dec 11 '16 at 17:03
21
$\begingroup$

Wedderburn's little theorem: In its simplest form, it states that any finite division ring is commutative. I find it borderline magical; as if somehow the axioms do not imply the result, but rather it is forced due to some weird combinatorial coincidence. Of course, this feeling of mine says more about my flawed intuition than about the theorem - but that's true for any example of a "counterintuitive mathematical result".

Another example, even more elementary, is the fact that a matrix's rank is well defined, i.e., that for any matrix (even if it's non-square), the dimension of its column-space is equal to the dimension of its row-space. Over time I came to terms with this result, but when I first encountered it, I've been reading the proof again and again, understanding every step - but still couldn't believe the theorem is true. It was a long time ago, but I clearly remember I've felt like I'm practicing voodoo.

$\endgroup$
  • 2
    $\begingroup$ Arguably, the reason for the counterintuitive matrix rank is that matrices are just a not-really-optimal representation of linear mappings. It's fairly intuitive that the image of a linear mapping has the same dimension as the image of its adjoint mapping. $\endgroup$ – leftaroundabout Dec 3 '16 at 21:17
  • $\begingroup$ “Young man, in mathematics you don't understand things. You just get used to them.” -- John von Neumann $\endgroup$ – Mike Jones Dec 6 '16 at 23:33
  • $\begingroup$ @leftaroundabout: matrices are the only representation I know of linear mappings, what else did you have in mind? $\endgroup$ – Mozibur Ullah Dec 11 '16 at 6:51
  • $\begingroup$ @MoziburUllah there are plenty of representations. One representation that makes it particularly clear that the rank doesn't depend on the space dimension is the singular value decomposition (which can be defined without ever talking about matrices, only abstract linear mappings). $\endgroup$ – leftaroundabout Dec 11 '16 at 10:09
  • 1
    $\begingroup$ @MoziburUllah there is no such difference, I just said abstract to emphasize that there's no need to write out the linear mapping in any particular notation (like a matrix). It's sufficient to describe it as a generic function $\varphi : V\to W$ between two vector spaces which has the linearity property $\varphi(\mu\cdot u + v) = \mu\cdot\varphi(u) + \varphi(v)$. Sure enough, any such function (if the spaces are finite-dimensional) can be written in matrix notation, but my point is that this isn't always such a good idea since it obscures interesting properties (like well-defined rank). $\endgroup$ – leftaroundabout Dec 11 '16 at 10:57
20
$\begingroup$

I've always thought Bernoulli's paradox was counter-intuitive, and the name suggests that I'm not the only one who thinks this. (Nicolas) Bernoulli offers the following gambling game; You flip an honest coin. If it comes up heads, you win two dollars and get to flip again. If it comes up heads a 2nd time, you win four more dollars and you get to flip again. In general if it comes up heads for n consecutive times, on the nth flip you win 2^n more dollars and get to flip again. The first time the coin comes up tails the game is over, but you get to keep your winnings. Bernoulli asked essentially what the mathematical expectation of this game is. To keep things finite, let's just ask if should you mortgage your house and pay Mr. Bernoulli $250,000 to play this game? Although I would strongly advise against doing so, the mathematics "shows" that you should be willing to put up all the money you have or can borrow to play the game.

$\endgroup$
  • 13
    $\begingroup$ The counterintuivity here comes from not so much from the game itself, as from tacitly conflating “should you do it?” with “is the expected value, in dollars, positive?” This conflation turns our strong (and very justifiable) gut instinct that we shouldn’t play the game into the erroneous intuition that its expected value is negative. $\endgroup$ – Peter LeFanu Lumsdaine Dec 3 '16 at 15:14
  • 8
    $\begingroup$ Also known as the St Petersburg paradox. Since it is presented as a real-life challenge, to evaluate it requires the assessment of at least two entailed real-life hazards: (1) Counterparty risk---the offerer cannot or will not pay up as promised. (2) The decreasing marginal utility of wealth---a million-dollar gain might transform your life now, but you would hardly notice it if you already had a billion. $\endgroup$ – John Bentin Dec 3 '16 at 15:17
  • 6
    $\begingroup$ @John Bentin I have comforted myself by taking Bernoulli's game as a mathematical proof of that the law of marginal utility applies even to wealth. Also buried away is the tacit assumption of economists that utility is always positive: you have to wonder if, after receiving eleven Lords a leaping, the recipient doesn't begin to thank God there aren't 5000 days of Christmas. Counterparty risk is a red herring: if ,as a gedankin experiment, you ignore it, the paradox remains. $\endgroup$ – Airymouse Dec 3 '16 at 16:11
  • 7
    $\begingroup$ The classical St Petersburg paradox does not pose a limit to the number of flips which makes it a paradox dealing with infinity (which OP wants to exclude). Indeed, the surprising result is that the expected value is $\infty$ so any amount you bet is acceptable to you if you play the game enough times. You should limit the game to at most $N$ flips, which will make the expected value $N$. Any bet below $N$ (per game) is acceptable, which again can be counterintuitive if $N$ is a large number. The trick part is realising that the median and expected value are very different in this game. $\endgroup$ – Thanassis Dec 4 '16 at 2:38
  • 10
    $\begingroup$ This problem becomes much more intuitive when you assume any finite bound on the amount of money the house is able to pay out. If you cap the amount you could possibly win at even a trillion dollars, the expected value drops down from infinite to about $10. $\endgroup$ – Shufflepants Dec 5 '16 at 16:46
16
$\begingroup$

That you only need 23 people in a room for there to be a 50% chance that two of them will share a birthday.

$\endgroup$
  • 4
    $\begingroup$ To me this is like the “counter-intuitive” fact about how often you have to double the thickness of a newspaper to reach the moon. It comes down to it being too easy to acquire incorrect intuitions and be surprised they are wrong – we have to learn caution. Now Dorothy Parker’s intuition was that it would not be at all surprising if all the girls at a Yale prom were laid end to end – that’s more like it. $\endgroup$ – PJTraill Dec 6 '16 at 0:21
  • $\begingroup$ Write a story about 23 people and explore the relationship between every pair of them. The birthday paradox will then no longer be a paradox. $\endgroup$ – Théophile Dec 7 '16 at 20:23
15
$\begingroup$

Langton's ant is a set of rules that are applied to change "pixels" in a grid. After a finite number of steps of applying those rules, the rather chaotic behaviour changes into a periodic one. That can be seen in the picture below.

langtons ant

$\endgroup$
  • $\begingroup$ Not only that, but there are some turmites that are only slightly more complex to describe than Langton's ant (e.g. 9 turmites with 3 colours where Langton's ant has 2) where it is not known whether they will ever settle down into periodic behaviour. github.com/GollyGang/ruletablerepository/wiki/… and scroll down to "Unresolved Turmites". $\endgroup$ – Rosie F Jul 9 '18 at 20:05
14
$\begingroup$

The amazing speed of exponential growth. This can be explained to children, but it will always defy your intuition, take e.g. the famous wheat and chessboard problem. As Addy Pross explains here, this may play a fundamental role in the emergence of life.

$\endgroup$
  • 2
    $\begingroup$ Whenever it does come within your understanding, I recommend looking into the Ackermann function, Knuth's up-arrow notation, Graham's number, and other related things from googology, recommendably in that order. Then your mind will truly blow up at how fast things can grow. $\endgroup$ – Simply Beautiful Art Mar 20 '17 at 23:46
  • $\begingroup$ @SimplyBeautifulArt there is something of this Googology in the long path $27$ takes to reach $1$ by iteration of the Collatz function. $\endgroup$ – user334732 Nov 1 '17 at 13:22
  • $\begingroup$ @RobertFrost possibly interesting. Personally I find things like TREE(3) and the Goodstein sequence more interesting :P $\endgroup$ – Simply Beautiful Art Nov 1 '17 at 13:59
14
$\begingroup$

First, a more elementary example: Given two polygons $A$ and $B$ of equal area, I can always cut one into a finite number of polygonal pieces, and rearrange those to form the other; that is, any two polygons of equal area are scissors congruent.

Hilbert's third problem was about extending this result to three dimensions. He conjectured, rightly, that it fails in three dimensions, and this was proved shortly afterwards by his student, Dehn.

Still, even though it was proved rather quickly, and Hilbert's (and others') intuition was right on the mark, I still find it incredibly counterintuitive.


Another geometric example is the refutation of the triangulation conjecture; however, I'm not sure if arbitrary manifolds count as finite objects.

$\endgroup$
  • $\begingroup$ This doesn't quite satisfy “only involves finite objects” though, does it? $\endgroup$ – leftaroundabout Dec 7 '16 at 21:10
  • $\begingroup$ @leftaroundabout I think the first one does - everything in question can be appropriately represented by a finite set of natural numbers (OK fine, technically we need to consider polytopes with vertices in some fixed countable set - say, all coordinates rational - but the fact still holds). Note that the OP is okay with quantifiers ranging over $\mathbb{N}$, just not direct invocation of infinite sets. The second example is much less finitary, but I thought it was worth mentioning just in case (it can be finitized, but less naturally). $\endgroup$ – Noah Schweber Dec 7 '16 at 21:16
14
$\begingroup$

As a non-mathematician it seems pretty obvious to me that there are whole number solutions (where $n>2$) for

$$a^{n}+b^{n}=c^{n}.$$

I'd be shocked if there weren't. There must be some, surely.

$\endgroup$
  • $\begingroup$ I'm not sure if you're being sarcastic, but in 1995 this was famously proven not to have solutions. $\endgroup$ – Akiva Weinberger Dec 5 '16 at 18:55
  • 2
    $\begingroup$ @AkivaWeinberger yeah, but it is counter-intuitive that it has no solutions. $\endgroup$ – theonlygusti Dec 5 '16 at 19:05
  • 1
    $\begingroup$ @theonlygusti I was referring to the "I'd be shocked if they weren't" bit; it implies that OP does not know. $\endgroup$ – Akiva Weinberger Dec 5 '16 at 19:06
  • 19
    $\begingroup$ @AkivaWeinberger: That he gives this as an answer suggests quite strongly that he is aware of the result and intends to suggest he considers it counter-intuitive. His phrasing suggests British, perhaps with the matching sense of humour – his profile confirms it. $\endgroup$ – PJTraill Dec 5 '16 at 23:58
  • 4
    $\begingroup$ What's counter-intuitive about this having no solutions? IMO it's not intuitive that this has an integral solution for any $n\neq 1$; in fact I recall being mildly surprised when I first read that Pythagorean triples exist – of course, just trying a couple of numbers quickly gives an affirmative example, but a priori it seems just as plausible that there's a simple argument à la irrationality of $\sqrt 2$ (small enough to fit in this margin...) that it can't work. What's counter-intuitive is that it required so insanely advanced maths to settle this simple question. $\endgroup$ – leftaroundabout Dec 7 '16 at 21:21
9
$\begingroup$

For those who don't find the "harmonic overhang" of Scott's answer counterintuitive, here is a variant that Loren Larson, a retired mathematician and current creator of wooden puzzles, discovered and demonstrated some years ago: It's possible to construct a stable tower of blocks with the property that removing the top block causes the tower below it to collapse.

It's worth spending some time trying to imagine how this is possible, but once you give up, here is the secret:

Start with a standard harmonic overhang (as I recall, Loren's had a couple dozen wooden blocks of dimensions something like $8$ inches by $2$ inches by $1/2$ inch) and carefully nudge it, block by block, to form a spiral. If the tower is tall enough and the spiral is big enough -- Loren worked out the mathematical details -- the top block becomes necessary to counterbalance the portion of the spiral lower down that juts out on the opposite side. Removing it creates an imbalance that causes the lower portion to topple.

$\endgroup$
  • 8
    $\begingroup$ Why not just put three blocks one on the other, with middle one shifted to the side? Removing the top block will cause middle one to fall. $\endgroup$ – Abstraction Dec 7 '16 at 12:12
  • $\begingroup$ Yeah, or surely build up Scott's tower, and then build it on top of itself again going in the other direction. $\endgroup$ – theonlygusti Dec 7 '16 at 12:47
  • 2
    $\begingroup$ A tower that collapses when you remove the top block is easy to imagine; the fact that a particular tower does so might be less obvious. The difficulty here is trying to imagine what the tower actually looks like; I wasn't able to get a clear enough picture of it to say whether it is counterintuitive that the top block is required. $\endgroup$ – David K Dec 7 '16 at 22:36
9
$\begingroup$

I don't know whether it qualifies -

If we cut a Mobius strip, instead of getting two strips, we get only one strip (longer, with two 2 twists). When I first saw this, it was quite counter-intuitive to me.

$\endgroup$
  • 9
    $\begingroup$ That's wrong. You don't receive a new Möbius strip, but a strip that has two twists. That's odd. But what baffled me: When you cut this strip, you get two strips that are interwound. Further results of cutting are listed at the Wikipedia page, and it's really getting crazy at some point... $\endgroup$ – Marco13 Dec 8 '16 at 19:18
  • 2
    $\begingroup$ I didn't said that one'd get a new Mobius strip but I said that one'd get a long Mobius strip, without mentioning about the twists though. $\endgroup$ – Kushal Bhuyan Dec 9 '16 at 2:01
  • 5
    $\begingroup$ @KushalBhuyan But the resulting strip is not a Möbius strip. I don't understand what you are saying. $\endgroup$ – Improve Dec 10 '16 at 15:28
  • $\begingroup$ Its a great example even if the details are missing - because it is something one can straight-forwardly and practically do - unlike most of the other examples. $\endgroup$ – Mozibur Ullah Dec 11 '16 at 6:44
  • $\begingroup$ @ypercubeᵀᴹ Thanks $\endgroup$ – Kushal Bhuyan Dec 12 '16 at 10:11
8
$\begingroup$

I think it is counterintuitive, at first glance, that list coloring graphs can be strictly harder than ordinary coloring.

To expand on what that means: a graph is a set of vertices, some pairs of which are adjacent. (Think of the vertices as dots, with adjacent vertices having a line drawn between them.) A proper $k$-coloring of a graph assigns each vertex a number from $1$ to $k$ such that no two adjacent vertices receive the same color. The chromatic number of a graph $G$, written $\chi(G)$, is the smallest $k$ such that $G$ has a proper $k$-coloring.

A $k$-list-assignment on a graph is a function $L$ that assigns each vertex some "palette" of $k$ different numbers. If $L$ is a $k$-list-assignment, then a proper $L$-coloring of $G$ assigns each vertex a color from its list such that, again, no two adjacent vertices receive the same color. The list chromatic number of $G$, written $\chi_l(G)$, is the smallest $k$ such that $G$ has a proper $L$-coloring for every $k$-list-assignment $L$.

Now, intuition (at least, my intuition) suggests that finding an $L$-coloring should be hardest when all the vertices have the same list $L$ -- in other words, when we're really just looking for a proper $k$-coloring. If different vertices have different lists, aren't there just fewer opportunities for collisions to happen? This suggests that maybe $\chi_l(G) = \chi(G)$ for every $G$, since the hardest list assignments "should" just be the ones that give every vertex the same list.

However, this isn't true! Consider the complete bipartite graph $K_{3,3}$, whose vertices consist of six vertices $v_1, v_2, v_3, w_1, w_2, w_3$ where any pair of vertices $v_iw_j$ is adjacent. This graph clearly has a proper $2$-coloring: color all the vertices $v_i$ with color $1$ and all the vertices $w_j$ with color $2$. But now consider the following list assignment $L$:

$L(v_1) = L(w_1) = \{1,2\}$

$L(v_2) = L(w_2) = \{1,3\}$

$L(v_3) = L(w_3) = \{2,3\}$.

Among the colors $\{1,2,3\}$ appearing in these lists, we would need to use at least two of them on the vertices $v_i$, since no color appears in all three lists, and we would need to use at least two of them on the vertices $w_j$, for the same reason. This means that some color gets used on both a $v_i$ and a $w_j$, which contradicts the assumption that the coloring is proper. So there is no proper $L$-coloring, which means $\chi_l(K_{3,3}) > 2 = \chi(K_{3,3})$. In other words, it's harder to color from these lists than it is to color when every vertex has the same list!

$\endgroup$
  • $\begingroup$ Why do you claim it's counterintuitive that colouring should be harder when you have fewer free choices of colour in list colouring? One can consider the "open" colouring to have assigned every vertex a list of $|V|$ colours, and the problem is simply to make that list as short as possible given $E$ and the definitions that apply. Consider by analogy: it is easy to assemble a Yowie toy on the table, but very difficult to fit the pieces back in the capsule, and often impossible to fit the complete toy at all. $\endgroup$ – Nij Dec 3 '16 at 6:34
  • 4
    $\begingroup$ @Nij: He doesn't have fewer choices: In both cases, he can choose one of two colours at each node. And the total number of colours in the second case is larger (because there are three colours in the union of all lists). $\endgroup$ – celtschk Dec 3 '16 at 11:58
  • $\begingroup$ @Nij - as celtschk said, the comparison isn't between finding the L -coloring for my specified L and finding any proper coloring at all, but rather, the comparison is between finding the L-coloring for the given L and finding a proper 2-coloring, which is the same as having the list {1,2} at every vertex. It seems intuitive to guess that the latter coloring problem should be harder, even though it turns out not to be. $\endgroup$ – Gregory J. Puleo Dec 3 '16 at 14:47
  • 1
    $\begingroup$ Good example. As you no doubt know, the smallest example for $\chi_l(G)\gt\chi(G)$ is the graph $G$ you get by removing two nonadjacent edges from $K_{3,3}$ or in other words $G=P_3\square P_2.$ $\endgroup$ – bof Dec 3 '16 at 19:48
8
$\begingroup$

(1). In the Stone Age, Og and Mog each need to make large numbers of arrow-heads and ax-heads. Their products are of equal quality. Og takes 3 units of time to make an arrow-head and 5 units of time to make an ax-head. Mog takes 4 units of time to make an arrow-head and 7 units of time to make an ax-head. Both of them consider their time to be valuable.

Since Og is faster at both, it seems that Mog could not give Og an incentive to trade.

But Mog offers to give 17 arrow-heads for 10 ax-heads, which, for Mog, is trading 68 units of time in return for 70. And for Og, this is trading 50 units of time in return for 51. So they both benefit by the trade.

(2). This might not count as finite: In triangle ABC draw the trisectors of the interior angles. Let the trisector lines of angles B ,C that are closer to the side opposite A, meet at A'. Define B',C' similarly. Then (Morley's Theorem) A'B'C' is an equilateral triangle. Intuitively it may seem that A'B'C' might have any given shape. There is a nice proof in Introduction To Geometry by Coxeter.

(3). The only solution in positive integers to $X^3=Y^2+2$ is $X=3, Y=5.$ (Pierre de Fermat). Not obvious to me that there aren't any others.

$\endgroup$
  • 5
    $\begingroup$ To help make the first one more intuitive: If you imagine that the timings were the same except that Mog took 1,000,000 units of time to make an ax-head, it's quickly pretty clear that he'd trade a lot of arrow-heads for them, and that that trade would be good for Og. $\endgroup$ – Ben Aaronson Dec 6 '16 at 9:03
  • 4
    $\begingroup$ (1) is yet another example from economics — the theory of comparative advantage. As said by Paul Samuelson, "That it [the theory of comparative advantage] is logically true need not be argued before a mathematician; that is is not trivial is attested by the thousands of important and intelligent men who have never been able to grasp the doctrine for themselves or to believe it after it was explained to them." $\endgroup$ – Kenny LJ Dec 7 '16 at 6:48
  • $\begingroup$ The first one doesn't seem counter-intuitive at all to me. It's a red herring that Og is faster at both; what's relevant is that they produce at different rates (i.e., time for axe vs. time for arrow). $\endgroup$ – Théophile Dec 7 '16 at 21:09
  • 1
    $\begingroup$ @Théophile. Try it out on people you know. Yesterday I showed it to a friend, a master at computer programming. He said he wouldn't have thought it possible. What is obscure to some is obvious to others, and what is counter-intuitive to some may be intuitively clear to others. And what was intuitive to S. Ramanujan, who knows? $\endgroup$ – DanielWainfleet Dec 7 '16 at 23:25
  • 1
    $\begingroup$ @Théophile: Try this. Say T-shirts and cars are the only two goods in the world. For an American worker, it takes 3 man-hours to produce a T-shirt and 5,000 man-hours to produce a car. For a Chinese worker, it takes 9 man-hours to produce a T-shirt and 20,000 man-hours to produce a car. The typical American who doesn't understand the theory of comparative advantage then wonders, "Americans are literally better than the Chinese at everything! So why are we shipping T-shirt jobs to China?" The answer is that surprisingly, both the US and China can gain by "shipping jobs to China". $\endgroup$ – Kenny LJ Dec 8 '16 at 0:52
7
$\begingroup$

Recall the Busy Beaver function, $BB(n)$ is the maximal number of steps that a Turing machine with at most $n$ states will halt on the blank tape, assuming it halts at all.

$\sf ZFC$ cannot decide the value of $BB(1919)$.1

Namely, if there is a contradiction to $\sf ZFC$, then a Turing machine with less than $2000$ states should be able to find it. Yes, $1919$ is a large number, but it's not unimaginably large. But what it means is that $BB(1919)$ is pretty much entirely unimaginable, because we cannot even give it a concrete estimation.

(See this and that on Scott Aaronson's blog.)


1. Under the usual caveat that we need to assume that $\sf ZFC$ is consistent of course.

$\endgroup$
  • $\begingroup$ Um, ZFC cannot decide the value of BB(1919) if ZFC is consistent. =) $\endgroup$ – user21820 Dec 24 '16 at 14:58
  • $\begingroup$ When is it not? C'mon, you only have to look at Turing machines with less than 2000 states! :-) $\endgroup$ – Asaf Karagila Dec 24 '16 at 15:00
  • $\begingroup$ I think it is but I can't prove it. =) Anyway I suggest you edit to make it consistent with your second part of your answer, which implicitly suggests the possibility that ZFC may not be consistent. $\endgroup$ – user21820 Dec 24 '16 at 15:03
  • $\begingroup$ We can look at them all, but we can't run them for arbitrarily long time, not to say infinite time. Well, it's the age-old question of whether the halting problem has a definite answer or not. =P $\endgroup$ – user21820 Dec 24 '16 at 15:05
  • $\begingroup$ That definite answer is, of course, 4. A number which is always visible, and always out of reach. $\endgroup$ – Asaf Karagila Dec 24 '16 at 15:07
5
$\begingroup$

Determinacy of classes of finite games:

The existence of winning strategies for finite games without draws and with perfect information is counter-intuitive at first glance. It is, ultimately, very sound though.

I have been in the situation of explaining this to children and adults with the example of simple games, and most of the time people went from disbelief to recognition that it is in fact obvious.

There are three major reasons for this counter-intuitiveness:

-We are used to playing those types of games since we're children, and in our experience, our strategies often ended up defeated.

-Winning strategies for even simple games are often unknown: most of the time they can't be computed because the numbers of possible outcomes are two high. So most of the time, the existence of a winning strategy for a game doesn't affect the way you play the game.

-The definition of the fact $W$ of being in a winning position is somewhat complex: if you can make a winning move, then $W$, and (if whatever move your opponent makes, then $W$), then $W$. This type of recursive definition can be hard to grab, and when trying to unveil it, complexity, in the sense of an alternance of quantifiers, really appears since you get: $\forall$ opponent move $\exists$ move such that $\forall$ opponent move $\exists$ move such that ... such $\exists$ a winning move for you.

$\endgroup$
5
$\begingroup$

82000. It absolutely boggles the mind because this is very close to the axioms, so to speak. You need to prove only a few things based on the Peano axioms to get to

The smallest number bigger than 1 whose base 2, 3, and 4 representations consist of zeros and ones is 4. If we ask the same question for bases up to 3, the answer is 3, and for bases up to 2, the answer is 2. But 82000 is the smallest integer bigger than 1 whose expressions in bases 2, 3, 4, and 5 all consist entirely of zeros and ones.

And it is very likely there is no other for 2-5 and none at all for 2-6.

Edit: if you downvote, please leave a comment so I can learn. Thanks!

$\endgroup$
  • $\begingroup$ Didn't downvote, but this doesn't seem like an interesting result (or one that's particularly counterintuitive). It doesn't explain anything; it doesn't seem to mean anything; and it doesn't seem to have any consequences. Questions about what numbers look like in different bases are generally not very interesting ones. $\endgroup$ – anomaly Dec 7 '16 at 16:40
  • 2
    $\begingroup$ Also the condition is trivial for base 2, so "bases up to 3" is really just "base 3", and "bases up to 4" is really just "bases 3 and 4". $\endgroup$ – Ben Millwood Dec 7 '16 at 17:32
  • 2
    $\begingroup$ Of course the first few are trivial -- but the base-N notation here is not exactly necessary, you could just talk about sum of powers, it's a small convenience. Ie. 82000 is the smallest of numbers that can be written as a sum of powers of 3 and 4 and 5. That's what I find so odd, that somehow this odd number comes from the structure of the mathematical universe. The oddity here is like Ramanujan's taxi cab number. $\endgroup$ – chx Dec 7 '16 at 17:37
5
$\begingroup$

Sporadic simple groups in the Classification of finite simple groups

https://en.wikipedia.org/wiki/Classification_of_finite_simple_groups

I find the existence of the sporadic simple groups https://en.wikipedia.org/wiki/Sporadic_group like the Monster group https://en.wikipedia.org/wiki/Monster_group is pretty astounding considering how simple the definition of groups is.

$\endgroup$
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$
  • 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 '16 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 '16 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 '16 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 '16 at 16:15
  • 1
    $\begingroup$ For the first one, do you mean "false" or "not provable"? $\endgroup$ – Theodore Norvell Dec 10 '16 at 15:09
4
$\begingroup$

Here are several involving the construction of regular polygons. For at least three out of the four cases we would not call it counterintuitive, but the results we know today would have thrown the Greeks for a loop.

1) The regular heptagon has no Euclidean construction. The Greeks would have preferred to be able to construct regular polygons generally by Euclid's methods, which would make their properties accessible to elementary proof. Only in modern times did we definitely learn the bad news.

2) The regular enneagon (nonagon) has no Euclidean construction, either. This is a special case of the old angle trisection problem: trisect the central angle of an equilateral triangle and you can make a regular enneagon. Now we know it works in reverse: we prove that a general angle trisection with Euclidean methods cannot exist by showing that the regular enneagon is not Euclidean-constructible.

3) The regular hendecagon does have a neusis construction. Unlike the other cases, this is purely a "modern" counterintuitive. It was long thought that neusis construction was similar to conic-section construction: you can solve cubic and quartic equations with it. But we know now that some (we don t know about all) irreducible quintic equations are also solvable. Benjamin and Snyder showed that the minimal equation for $\cos((2\pi)/11)$ is one such neusis-solvable equation. See Constructing the 11-gon by splitting an angle in five.

4) After the regular pentagon, the next regular prime-sided polygon constructible by Euclid's methods is the 17-gon. It 's "obvious" now, but ancient and medieval mathematicians would never have suspected it without the theories developed by Gauss.

$\endgroup$
  • 2
    $\begingroup$ I don't think #4 is at all obvious. It's well known to be true, just like the fact that the speed of light is finite, but that's not the same as obvious. $\endgroup$ – Théophile Dec 7 '16 at 21:26
  • 1
    $\begingroup$ @Théophile: That's why Oscar put it in quotes. $\endgroup$ – user21820 Dec 25 '16 at 8:03
3
$\begingroup$

Hmm, not sure if this counts as counterintuitive, but what about the handshaking lemma, that the number of people at a party who shake hands an odd number of times is even?

$\endgroup$
  • 1
    $\begingroup$ -1. It's not counterintuitive to expect the divisors of an even number to be either even or paired with an even complement divisor. $\endgroup$ – Nij Dec 3 '16 at 0:49
  • 4
    $\begingroup$ Look I agree (even if understatement forbade me from proclaiming didactically), hence my caveat, I guess it's just a 'cute' result, the amusement owing more to linguistics than mathematics. $\endgroup$ – Mehness Dec 3 '16 at 1:30
  • 4
    $\begingroup$ @Nij : I'm inclined to disregard any claim of "being intuitive" from anyone who has absorbed any significant quantity of math or science. "Intuitive" only to a handful of percent of the population is not intuitive. $\endgroup$ – Eric Towers Dec 4 '16 at 2:15
  • 1
    $\begingroup$ The fact that even numbers must have an even divisor is taught to eight-year-olds. The fact that factor pairs must contain all of the prime factors of the product is taught to ten-/eleven-year olds. It's intuitive to anybody who has had more math education than learning how to count and add. Defining "counterintuitive" to mean "not immediately expected by a seven-year-old" is frankly a terrible and pointless way to do it. $\endgroup$ – Nij Dec 4 '16 at 5:31
  • 4
    $\begingroup$ A set that is not open is not necessarily closed. A relation that is not symmetric is not necessarily anti-symmetric. A statement that is not intuitive is not necessarily counter-intuitive. :) $\endgroup$ – Théophile Dec 7 '16 at 21:18

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

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.