Ingenuity in mathematics

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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

Wikipedia link: Randomness extractor

Answer 4

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

Answer 5

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?

Answer 6

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

Answer 7

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

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

Does the problem of The Monkey and the Coconuts count?

Answer 12

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

Answer 13

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

Answer 14

Theorem [Inaba]. Any configuration of 10 points in the plane can be covered by disjoint unit disks.

Proof. Put a dense packing of unit disks on the plane at random.

Then the average number of covered points is $10\cdot \frac{\pi}{2\sqrt3}=9.069\ldots>9.$

See Covering Points with Disjoint Unit Disks for the history.

Answer 15

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.

Answer 16

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

Answer 17

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.

Answer 18

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

Answer 19

First, I'd suggest Eratosthenes's 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.

                                   <           
                                  /___~ 
                                () \- () 

Answer 20

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

Answer 21

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.

Answer 22

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.

Answer 23

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

Answer 24

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.

Answer 25

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

Answer 26

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

Answer 27

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.

Answer 28

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

Answer 29

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

Answer 30

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.