# Ingenuity in mathematics

[This is just the kind of vague community-wiki question that I would almost certainly turn my nose up at if it were asked by someone else, so I apologise in advance, but these sorts of questions do come up on MO with some regularity now so I thought I'd try my luck]

I have just been asked by the Royal Society of Arts to come along to a lunchtime seminar on "ingenuity". As you can probably guess from the location, this is not a mathematical event. In the email to me with the invitation, it says they're inviting me "...as I suppose that some mathematical proofs exhibit ingenuity in their methods." :-)

The email actually defines ingenuity for me: it says it's "ideas that solve a problem in an unusually neat, clever, or surprising way.". My instinct now would usually be to collect a bunch of cute low-level mathematical results with snappy neat clever and/or surprising proofs, e.g. by scouring my memory for such things, over the next few weeks, and then to casually drop some of them into the conversation.

My instinct now, however, is to ask here first, and go back to the old method if this one fails.

## Question: What are some mathematical results with surprising and/or unusually neat proofs?

Now let's see whether this question (a) bombs, (b) gets closed, (c) gets filled with rubbish, (d) gets filled with mostly rubbish but a couple of gems, which I can use to amuse, amaze and impress my lunchtime arty companions and get all the credit myself.

This is Community Wiki of course, and I won't be offended if the general consensus is that these adjectives apply to the vast majority of results and the question gets closed. I'm not so sure they do though---sometimes the proof is "grind it out". Although I don't think I'll be telling the Royal Society of Arts people this, I always felt that Mazur's descent to prove his finiteness results for modular curves was pretty surprising (in that he had enough data to pull the descent off). But I'm sure there are some really neat low-level answers to this.

-
I'm in a mellow mood and shan't vote to close, but I think that as penance for asking the question you should do a report on the seminar for us. Slightly more seriously, I think it'll be quite an amazing result that a) has a surprising proof, b) is explainable to non-mathematicians, and c) the fact that the proof is surprising is explainable to non-mathematicians. –  Loop Space Sep 28 '10 at 16:56
+1 for 'I suppose that some mathematical proofs exhibit ingenuity'. Two cultures, anyone? –  HJRW Sep 28 '10 at 17:31
–  Martin Brandenburg Sep 28 '10 at 17:36
Kevin: doesn't do it for me. Why would I be interested in the sum of the first 1000 numbers? Sounds like the sort of thing my kids would do before they knew any better. –  Loop Space Sep 28 '10 at 19:33
I think, by the way, that "I need some examples for a talk" is a completely legitimate excuse for a big-list community wiki question. –  gowers Sep 28 '10 at 20:03

"At any party, there are at least two people with the same number of friends there".

This typically won't be obvious to someone who isn't a mathematician. However, it's quite easy for many people to see this by picturing everyone at the party wearing a t-shirt displaying how many of their friends are present. The number of possible t-shirts is one less than the number of attendees, so there must be a double somewhere.

-
You need a little more to complete the proof, since, for $n$ people at the party, there are, a priori, $n$ possible t-shirts, bearing the numbers 0 through $n-1$. The extra step you need is that 0 and $n-1$ can't both occur (though either one can). –  Andreas Blass Sep 29 '10 at 13:03
[Pedantic note: 0 and n - 1 can both occur if there is only 1 person at the party. But perhaps it is implicit in "party" that there are at least two people.] –  Sridhar Ramesh Jun 16 '12 at 4:19

The impossibility of tiling a chessboard with two opposite corners removed using dominos is quite good for this purpose I think, especially if you start by giving a boring case-analysis proof for a 4-by-4 board.

The bridges of Königsberg is also pretty good. Marcus du Sautoy spoke about it last night in his series A Brief History of Mathematics on Radio 4 (though he overdid it when he claimed that the solution had "revolutionized the internet").

-
+1 for the chess board. It's my canonical example for such occasions. –  Alex B. Sep 29 '10 at 0:25
The chessboard problem can be nicely continued by proving that the chessboard can be tiled with dominos if two differently coloured squares are removed. Check out the solution of puzzle B at gurmeetsingh.wordpress.com/2008/09/12/… –  Tamas Hausel Sep 29 '10 at 16:24

There are irrational numbers $x$ and $y$ such that $x^y$ is rational. For consider $\sqrt{2}^\sqrt{2}$. This number is either rational or irrational. If it's rational then we're done. Otherwise, it's irrational, and $(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = 2$, so we're still done.

-
This is my favorite example of a non-constructive proof. –  Derrick Stolee Nov 30 '10 at 7:40
@Dinesh: but then you first have to prove that $e$ and $ln 2$ are irrational, which is slightly harder than the proof of irrationality of $\sqrt{2}$ –  Jan Jitse Venselaar Nov 30 '10 at 15:58
Well, let's choose $x=\sqrt{2}$, $y=2\log_2 3$. It is easy to prove that both $x$, $y$ are irrational. –  Fedor Petrov Nov 30 '10 at 22:35
While I like this result, I'm not sure if this is the sort of thing that will really "wow" a room full of artists, for whom (I imagine) notions of rationality and irrationality aren't familiar enough for this to be anything more than a remote curiosity. –  Nick Salter Dec 1 '10 at 20:47
i taught a class for gifted 8-10 year olds this summer and one of them showed me this proof! –  roy smith Aug 23 '11 at 2:53

One of my favorites is von Neumann's randomness extractor:

Suppose you have a biased coin that comes up heads with probability $p$ and tails with $q=1-p$. How do you construct an unbiased coin from the biased one?

The answer is simple but really nice. Simply toss the bad coin twice, and discard $HH$ and $TT$. The other two events occur with equal probabilities, $pq$ and $qp$.

-

Linear algebra proof of Binet's formula for Fibonacci numbers.

Fibonacci numbers satisfy

$\begin{pmatrix} 1 & 1 \\\\ 1 & 0 \end{pmatrix}^{n} = \begin{pmatrix} F_{n+1} & F_{n} \\\\ F_{n} & F_{n-1} \end{pmatrix}$

Diagonalize the matrix on left.

-
That's a really cool one,Fubini. John Kennedy showed to me originally and it shows the power of linear algebra manifesting in a really unexpected place. –  Andrew L Sep 29 '10 at 0:33
In fact, I'd go with the identity $F_{n+1}F_{n-1}-F_n^2=(-1)^n$ instead of the Binet formula. –  Victor Protsak Sep 29 '10 at 5:55
This is indeed a cool fact. However, I am certain any non-math person would be lost at the term matrix, let alone diagonalize, especially when said non-math people merely suppose some mathematical proofs exhibit ingenuity :) –  Peter Luthy Sep 29 '10 at 8:26
@AndrewL: It's never surprising when the power of linear algebra manifests itself. –  Sheikraisinrollbank Nov 30 '10 at 15:29

Here is a proof of Pythagoras's theorem that I like:

• You want to prove that the sum of the squares on each of the non-hypotenuse sides equals the square on the hypotenuse.

• You generalize, and instead prove that for any shape, if you scale it by $a$, and then by $b$, the sum of the resulting areas is the area of the shape scaled by $c$. (We began with the case of the unit square.)

• By thinking about how areas scale, it suffices to check for one particular shape.

• We check it by taking the shape to be the original triangle (to be pedantic: scaled so that its hypotenuse has length one). This case is clear: just drop a perpendicular from the vertex opposite the hypotenuse to the hypotenuse, and see note that the triangle with hypotenuse length $c$ is the sum of two similar triangle of hypotenuse lengths $a$ and $b$.

Obviously you are not going to drop this into casual conversation: it requires a focused effort at explanation. But I think it illustrates something true, and fairly general, about how mathematicians argue.

For example, the squares that we are adding get transmuted from areas of specific shapes, to scaling factors for areas of quite general shapes. This lets us go from checking something tricky (or trying to make tricky geometric constructions with the squares on the three sides, to see how they are related) to checking something that is immediately obvious. So we also see two kinds of ingenuity: the ingenious reinterpretation of the meaning of the squares (ingenious on a conceptual level, which is certainly a very common form of mathematical ingenuity), and the ingenuity of drawing a single line on the original triangle to break it into two triangles similar to itself (which is ingenious on a more visceral level --- a single stroke of ingenuity).

One other advantage: the other participants quite likely have heard of Pythagoras's theorem, and may even remember it, but are unlikely to know a proof. (Or do painters have some training in Euclidean geometry?) Knowing the result, they may be better positioned to appreciate the ingenuity of the proof.

Also: this argument appeared somewhere else recently on MO, I think, but I forget where. (Added: here, in a reponse of Dick Palais to Timothy Gowers's question about making something easier by generalization.)

-
It went well and I was glad I used the more powerful similarity approach for two reasons. 1) they learned a more generally useful idea. 2) I finished in the alloted time! –  roy smith Aug 6 '11 at 5:32

Does the problem of The Monkey and the Coconuts count?

-
I think Franz was suggesting the negative solution as his submission. Isn't that the whole point of this exercise? Find ways that replace brute-forcing your way to a solution with a non-obvious insight (that $-4$ is a solution, and solutions are periodic mod $5^4$) that depends on some knowledge of slightly non-trivial mathematics? –  Cam McLeman Sep 29 '10 at 14:18

You run a knockout tournament. Some good players get seeded to later rounds, and some players get byes if there are an odd number of players left. How many matches are necessary? (OK, it's well known and completely trivial, but you did imply that you would be talking to artists....)

-

There is the old classic of a fly flying between two trains.

-
I thought it was Gordon Baker's dog ... –  gowers Sep 28 '10 at 19:23
There is a great story about von Neumann being presented with this problem, which he answered instantaneously. "Aha! So you knew how to do it in a clever way. Most people are trying to sum the series, you know". - "What do you mean? That's what I did!". –  Victor Protsak Sep 29 '10 at 5:59

On the walk home I remembered the following. You play a game with a friend. The friend deals from a pack of cards, turning each card face up one by one. After each card, you have the opportinity to say "STOP" (and after the 51st card has been turned over you have to say "STOP"). The next card is then turned over, and you win if it's red. Can you devise a strategy which enables you to win on average with probability over 50 percent?

-
To complete the triviality of the situation, after your audience proposes a bunch of complex strategies, propose an alternative game whereby after "STOP" it's the last card in the deck that gets turned over. Everyone sees that this game is strategy-indifferent, and then you deliver the coup de grace... I've used this several times in math circles. Gets them every time. –  Alon Amit Nov 30 '10 at 5:19

Alex R's answer reminds me of another sort of clever "strategy" problem. The way I've heard it phrased is as follows (with apologies to the vegetarians in the audience):

You are given 1000 cups filled with water, exactly one of which (unknown to you) is laced with a lethal poison that is guaranteed to kill within 24 hours if ingested. You are given ten rats with which to determine the poisoned cup. What is the minimum amount of time needed to be certain?

One naive approach would be to break up the cups into groups of 100 to be fed to each rat (i.e. rat 1 gets cups 1 through 100, rat 2 gets 101 through 200 etc). After 24 hours one rat will be dead and you have narrowed the poisoned cup to one in 100. Repeat two more times: you have your poisoned cup identified within 72 hours.

There is in fact a much better solution, which identifies the cup in the minimal 24 hours. Since $1000~<~2^{10} = 1024$, assign each cup a number expressed in binary. Then give the water in that cup to those rats for which there is a '1' in the binary representation (so, for example, cup 17 = 10001 is fed to rats 1 and 5). After 24 hours, you can simply read off the number of the poisoned cup by the numbers of the dead rats.

You can impress your audience with the remarkable (some might say brutal) efficiency of this procedure: to identify one in a million cups you would need only 20 rats (ignoring, of course, any deaths caused by overhydration...)

-
Anyone who likes this problem might also enjoy thinking about the generalization where two or more cups are poisoned, which seems much harder to me: math.stackexchange.com/questions/639/… –  Qiaochu Yuan Nov 30 '10 at 21:54

I like evaluating the integral $$\int_{-\infty}^{\infty} e^{-x^2} dx.$$

-

Sylvester-Gallai Theorem:

n points in the 2D plane, not all collinear. There is a line which passes through exactly two points.

Proof: Dualize. Points<->Lines. In dual, we need to show no more than 3 lines intersect. Consider intersection points and lines as planar graph. Planar graphs have nodes with degree no more than 5. Done.

-

How about the classic 20 prisoner problem. A warden tells 20 prisoners that they can live if they survive the following game: tomorrow the warden will line up the prisoners single file (at random), facing forward and place either a red or blue hat on each prisoner. Each prisoner can only see the color of hats infront of him. The warden starts from the back of the line and asks each prisoner in turn what color hat they think they are wearing. If a prisoner answers correctly they live, otherwise they die. No communication is allowed between prisoners once the game starts and they can only shout "red" or "blue" when it's their turn. The prisoners have the evening to discuss a strategy.What is the best strategy for the prisoners? How many prisoners can be guaranteed to live.

-
Apart from being not for the general audience, I think that it's also wrong. It relies on a kind of constructive version of the axiom of choice, which of course doesn't exist, otherwise it wouldn't have to be an axiom. The AC is an existence statement and not a procedure for making a choice. In particular the sentence from the wikipedia page "Using the axiom of choice, they select and memorize a representative sequence from each equivalence class" doesn't make any sense to me. –  Alex B. Sep 29 '10 at 4:55
"Using the axiom of choice, they select and memorize a representative sequence from each equivalence class" doesn't make any sense to me.. Alex, will you be happier with "Using the axiom of choice, we can show that there exists a strategy (a mapping that takes in the position number and the tail seen from this position and outputs the hat color) that makes only finitely many errors for every input sequence"? I mean, "prisoners", "hats", and "memorize" are just colorful words here and the implied translation into the formal language is rather obvious, so what do you object? –  fedja Dec 3 '10 at 22:53

The game of chomp: http://en.wikipedia.org/wiki/Chomp where player 1 has a winning strategy, but no one really knows how to find it.

It's a neat example of a nonconstructive proof of existence (and has a short proof).

-
I know how to find it. Wanna play chomp? –  Sheikraisinrollbank Dec 3 '10 at 12:04

Certainly Cantor diagonalization? You have Russell's paradox, which is perfectly understandable to the lay person, going to the uncountability of reals, going to Godel's incompleteness. I think each incarnation passes Andrew Stacey's tests...

-
NERD ALERT NERD ALERT I have tried explaining Cantor's Diagonal Argument to my girlfriend. Eew. On a very long bus journey in Bolivia. Well, we had got bored of looking out of the window...Anyway, my point is that she's got quite a scientific brain (she's a doctor) but it took a fair while to explain it to her, despite the fact that she was (or at least seemed) genuinely keen to understand my comment that "there is more than one kind of infinity". I'm not convinced I'm going to convince a painter of this over lunch :-) –  Kevin Buzzard Sep 28 '10 at 18:24
I agree with Kevin on this one. I have a suspicion that: #(people who understand the setup) - #(people for whom the proof isn't "what else could it be?") = #(cranks who keep posting on the arXiv). –  Loop Space Sep 28 '10 at 18:30
What I had in mind when I wrote "Russell's paradox" is the barber paradox version. I think it can be understood by a painter. If it helps, you can even turn it into a painter paradox version, with the painter drawing portraits! The second part, about Cantor or Godel, can be put into language very similar to the barber paradox. While I don't expect a painter to understand all the words that fit in these statements, it should be possible to explain the similarity with the more tangible barber paradox. And you can confidently say that this idea has revolutionized math twice in the past century. –  Paul-Olivier Dehaye Sep 28 '10 at 19:11
I barely ever log into this stack exchange; I just browse. But the low score on this answer bugged me. It's a fantastic answer. I roomed with an art major my second and third year of college. He is particularly bright and very multi-talented individual but not trained in mathematics to any capacity. He understood Cantor's Diagonalization easily and declared, "Ross, you just blew my mind!" (as though the proof were my own.) Douglas Hofstadter provides a really simple explanation of all three of these suggestions. I might suggest skipping (the proof of) Godel's Incompleteness Thm., though. –  Ross Snider Nov 30 '10 at 17:34

The Monty Hall Problem is one possibility. I usually pose the problem as, "Should you always switch or always stay or does it even matter?" The argument that switching is the best strategy is itself not especially neat from a mathematical point-of-view, but since the result completely defies human intuition, I think the proof seems quite ingenious, especially to people outside math. It certainly solves a problem in a surprising or unusual way in that the answer is shocking. If you decide to do it, I would recommend bringing in 3 cards (two spades and a heart, say) as props to aid in your explanation and discussion.

-
Much easier explanation: Suppose there are a hundred doors... –  Harry Gindi Nov 30 '10 at 17:37
The problem with explaining this to a general audience is not that they won't believe your explanation of why it's 1/3 to 2/3, but rather that they will generate one or more explanations of why it's even probability, believe those too, and get confused. –  Elizabeth S. Q. Goodman Dec 1 '10 at 7:24

First, I'd suggest Erathostenes method of computing the radius of the Earth, unless it is really well-known to them.

Otherwise, here's a nice one. You go for a bike ride. At the end, each wheel has made a closed simple curve, and, suppose, you noticed that these two curves never met. What's the area encosed between them? The distance between the centers of the wheels is $r$.

Answer : $\pi r^2.$ Explanation: the line passing for the two contact points of the wheels on the ground, is tangent to the back wheel's curve, and during the trip, it made a complete $2\pi$ rotation. To convince your audience: imagine a disk (a pizza) cut into several very thin slices (with vertex in the center as usual). Make the slices slide on each other, so that a hole appears in the middle of the pizza. The curve bounding the hole is the one traced by the back wheel; the exterior boundary is the curve traced by the other wheel.

                                   <
/___~
() \- ()

-
done. A pizza bike for you! –  Pietro Majer Sep 29 '10 at 10:30

One of my students created the following proof that the medians of a triangle are concurrent while waiting to talk to me in office hours.

Choose any two medians.

1) the two medians do meet somewhere inside the triangle.

2) If we join the centers of the three sides, obtaining a "central triangle",

then the two given medians are also medians of that central triangle,

hence their meeting point is also inside that triangle.

3) We are done.

I.e. iterating the procedure shows that any two medians meet at the unique point common to all central triangles.

-
You need to show that the triangles doesn't have more than one common point: You could make this "proof" for any three lines from the vertices to the opposite sides. The difference is, that for the median, the area of the central triangles goes to 0, but it doesn't in general. –  Sune Jakobsen Dec 15 '10 at 18:38

Solving a math problem by appeal to electricity is pretty creative in my opinion. Check out squaring the square.

-

How about the fact that in hex the first player has a winning strategy?

-

The RSA algorithm publicly described in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT is a classic example of "Ingenuinity in Mathematics". Its the famous Public Key Cryptography scheme widely used everywhere and is solidly founded on Mathematics.

-

Consider a random walk on $\mathbb{Z}/n\mathbb{Z}$ starting at 0. At each step either add 1 or subtract 1, with probability 1/2 each. Let $0\neq i\in\mathbb{Z}/n\mathbb{Z}$. What is the probability $P_n(i)$ that $i$ is the last point to remain unvisited?

Solution. Consider the first time the walk reaches a point adjacent to $i$ (either $i-1$ or $i+1$). The probability that $i$ is the last point to remain unvisited is then the probability that the walk visits the other point adjacent to $i$ before visiting $i$. This probability is independent of $i$. Hence $P_n(i)=1/(n-1)$. (I don't know the origin of this classic problem.)

-

The problem:

A rectangle R can be tiled with smaller rectangles such that

• The sides of the smaller rectanges are parallel the sides of R.
• At least one side of each of the smaller rectangle is integral.

Show that at least one side of R is integral.

The proof:

Consider $\iint_{R} e^{2 \pi i (x+y)} dxdy$

This is zero, by adding up along each small rectangle. The result follows.

-
I think an analogous proof that can be explained to artists is to tile the rectangle w/ a black and white checkerboard parallel to the rectangles with squares of width 1/2. You can then show that a rectangle having equal black and white areas (of overlapped checkerboard squares) is necessary and sufficient for determining that it has an integral side. Each rectangle with integral sides then has equal black and white squares, which combine to show that the large rectangle has the same property and thus an integral side itself. –  Randy Qian Sep 28 '10 at 19:45

Among the fairly recent results, I like the proof of the joints conjecture (the final clean version that can be explained in a few sentences to anyone familiar with polynomials, derivatives, and elementary linear algebra). This may be a bit hard to the general audience though. Among all combinatorial geometry theorems, Bang's solution of Tarski's plank problem is unbeatable in my humble opinion. When presenting it, just do it for the unit ball in $\mathbb R^n$ assuming that all strips pass through the origin. It is then a one-liner (If the strips are $S_j=\{x:|(x,v_j)|\le |v_j|^2\}$ and $\sum_j |v_j|<1$, the point $y=\sum_j \pm v_j$ with the largest possible norm lies in the ball but in none of the strips). Once you have this idea in its pure form, the rest can be figured out in finite time. But how does one come up with ideas like that? (this is not a rhetoric question, by the way).

-

I think the 3 children with dirty faces puzzle is a good one for this type of talk (also referred to as the "blue-eyed islanders puzzle" on Tao's blog http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/):

I came home yesterday to find that my 3 kids had been playing rugby and all had dirty foreheads. I told them that whoever could tell me whether their own forehead was dirty would get a shiny new bike. After looking at each other for a moment, they seemed uncertain. I asked again, "No ones knows?" Still no reply. Finally I shrugged and said, "Well, if you can't tell me then no one gets a bike," at which point all three simultaneously shouted: "My forehead is dirty!".

-

Mathematicians are used to seeing these sorts of problems and are generally more intrigued by their solutions, but I came across this recently:

Colour every point in the plane either black or white.

Fix any positive distance $d$.

Can I find two identically coloured points which are a distance $d$ apart?

Answer: Of course. Look at the vertices of an equilateral triangle of side length $d$.

-

Let me mention that the question is closely related to a more recent one Proofs that require fundamentally new ways of thinking which I think also is about ingenuity in a sense. So indeed I was not sure where this answer better fits but I think the proof I would like to mention belongs here more.

This is Galvin's proof of the Dinitz conjecture: The Dinitz conjecture asserted that if you give me an n by n array and in each square you put a set of size n then you can chose one element from each set so that all the chosen elements in a row or in a column are distinct.

If all the sets are the same (say 1,2,...,n) then you just want a Latin square. You can simply chose at position (i,j) i+j modulo n,

Galvin's proof derive Dinitz conjecture from the Gale-Shapley marriage theorem (Actually he used a theorem of Maffray, related to the stable marriage theorem.). It is short, elementary and extremely surprising. ( I will try to find a link.)

-

Christian Blatter gave a wonderful proof of Pick's Theorem using thermodynamics (okay, it's really not that fancy, but it involves a thought experiment about heat distribution). It originally appeared in Math. Mag. Here is a free link: http://www.math.ethz.ch/~blatter/Pick.pdf.

-

I like very much the proof of fundamental theorem of algebra (using the winding number around the origin), but it will probably take too long to explain...

-