What are some counter-intuitive results in mathematics that involve only finite objects?

Solution 1:

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.

Solution 2:

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:

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:

Solution 3:

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.

Solution 4:

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.

And more number-4 things by Saharon Shelah (presented in Twitter post by Artem Chernikov).

Solution 5:

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

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!

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