Neat solutions to tedious questions

Question

In mathematics there are often two ways of answering a question,

• Lots of thinking and little working,

• Little thinking and lots of working.

I was wondering what the most extreme cases of this would be? Questions where the "usual" answer is just to plough through the working and hope everything turns out all right, but a much more subtle solution exists (and ideally this subtle solution would point out what makes the question "tick", as it were).

For example,

Question: Prove that the symmetric difference operation is associative.

The symmetric difference of two sets, $S \triangle T$, is defined to be $(S\cup T)\setminus (S \cap T)$. Now, one could simply plough through the working, but the working is tedious and there is a "trick" half way through it. However, a much more subtle solution exists. It requires a bit of setting-up, but is overall much neater.

Proof: The idea is that $S\triangle T$ "looks like" addition mod $2$. To see this, notice that,

• If $x\in S$, $x\in T$ then $x\not\in S\triangle T$, which corresponds to $1+1=0 \text{ mod }2$

• If $x\in S$, $x\not\in T$ then $x\in S\triangle T$, which corresponds to $1+0=1\text{ mod }2$

• If $x\not\in S$, $x\in T$ then $x\in S\triangle T$, which corresponds to $0+1=1\text{ mod }2$

• If $x\not\in S$, $x\not\in T$ then $x\not\in S\triangle T$, which corresponds to $0+0=0\text{ mod }2$

This means that showing $(S\triangle T)\triangle U=S\triangle (T\triangle U)$ now comes down to showing that addition mod $2$ is associative. And it is, which is easily checked. So we're done.

Answer 1

I'm not sure these are good examples of what you want; but, for what it's worth:

This is well known:

Imagine you are studying infinite series and are presented with the following problem:

Two trains $B$ and $C$, each initially one mile from point $A$ are traveling towards each other, each with speed $1 $ mile per hour. A bee travels at two miles per hour, starting at train $A$, then heading to train $C$, then after reaching train $C$ heads back to train $A$, and so on...

What is the total distance the bee travels?

The tedious way is to compute the distance $s_n$ the bee travels at each stage, and then form the infinite series $s_n$ and compute its sum.

The easy way is to note the bee travels up to the time when the trains collide (poor bee!). Since the trains collide after one hour, the bee travels a total distance of two miles.

---

Lots of examples occur in probability:

Two players $A$ and $B$ are dueling. At each round, they shoot at each other with $A$ hitting $B$ with probability $a$, and $B$ hitting $A$ with probability $b$. What is the probability that $A$ wins the duel?

The tedious way is to compute for each positive integer $n$ the probability that $A$ wins on round $n$, and then compute the sum of those probabilities.

The clever way is to note that if both players miss on the first round, then given this, the probability that $A$ wins is the same as the original probability that $A$ wins.

So, if

$\ \ \ \ A_w$ is the event that $A$ wins the duel

$\ \ \ \ A_1$ is the event that both players hit on the first round

$\ \ \ \ A_2$ is the event that $A$ hits and $B$ misses on the first round

$\ \ \ \ A_3$ is the event that $A$ misses and $B$ hits on the first round

$\ \ \ \ A_4$ is the event that both miss on the first round,

then $$\eqalign{ P(A_w) &=P(A_w\cap A_1 )+ P(A_w\cap A_2 )+P(A_w\cap A_3 )+P(A_w\cap A_4 )\cr &= 0+ a(1-b)\cdot1+0+ (1-a)(1-b) P(A_w| A_4)\cr &= a(1-b)\cdot1+ (1-a)(1-b) P(A_w ) }, $$ which can be solved for $P(A_w)$.

Answer 2

Suppose a Markov chain has $n$ states arranged in a circle. Number the states $1, \cdots, n$. For any state the probability of going the next state in the clockwise direction is $p$ and the probability of going to the next state in the counterclockwise direction is $1 - p$, where $0 < p < 1$. Pick $k \in \{ 1, \cdots, n \} $ and rotate the diagram so that state $1$ is now located where state $k$ was. Notice that the transition matrices for both the original and rotated state spaces are the same. But then state $1$ and state $k$ have the same probability in both equilibrium distributions. Since $k$ was arbitrarily chosen and there are a total of $n$ states the probability of any state in the equilibrium distribution of any state is $\frac{1}{n}$. More generally, if the states Markov chain has a symmetry group $G$ then, for any state $k$, every state in the orbit of $k$ has the same probability in the equilibrium distribution.

Answer 3

Here's another example that's even about associativity. On any (projective) algebraic curve with (affine) equation $$y^2 = x^3 + ax^2 + bx + c$$

it is possible to define a group multiplication (see elliptic curve) on the points of the curve uniquely defined as follows: given two points $P, Q$, their sum $R$ is defined to be $(x, -y)$ where $(x, y)$ is obtained by drawing a line through $P, Q$ and taking the (unique, if multiplicities are taken into account) third point on the curve intersecting the line.

It is not at all obvious from the above definition that this operation is associative. There is a messy geometric proof and a possibly even messier algebraic proof, but a (to my mind) much cleaner proof is to prove that the group defined above is isomorphic to the divisor class group of the curve (the group of degree-zero divisors modulo the group of principal divisors), which is defined in such a way that it is obviously a group. The isomorphism sends a point $P$ to the divisor $P - O$ where $O$ is the point at infinity.

Answer 4

Elementary probability has lots of such questions. One of my favourites: Shuffle a standard deck of cards (52 cards, of which four are aces). What is the probability that the card directly below the second ace from the top is another ace?

[ For those who might want to puzzle it out, I'll wait a day or two before posting the elegant solution ]