Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
"comes down to showing that addition mod 2 is associative. And it is, which is easily checked. So we're done." -- Sorry, I fail to understand how addition mod 2 being associative is any easier to check than the associativity of $\Delta$. –  Srivatsan Jan 20 '12 at 12:53
1  
Last 10 digits of 50! Could be worked out the hard way, or it could be noticed that $5^{10}.2^{10}|50!$ so they are 0s. –  Angela Richardson Jan 20 '12 at 12:56
1  
@Srivatsan: Well, there are $8$ cases to prove...less if you factor in commutativity...or, we've reduced the question to something we known stuff about. I mean, if you've ever heard of a group, or have even just come across modular arithmetic at some point then you don't need to do anything... –  user1729 Jan 20 '12 at 13:18
3  
And now you are simply waving your hands. At some stage, you need to verify associativity to show that integers modulo 2 form an additive abelian group. I still don't see how that work got reduced. –  Srivatsan Jan 20 '12 at 19:37
2  
@Srivatsan: this proof of associativity of the symmetric difference was addressed by Halmos in his article "Does mathematics have elements?" available here: math.uh.edu/~tomforde/Articles/Elements-Halmos.pdf see pages 3-4. –  Bruno Stonek Jan 20 '12 at 20:55

4 Answers 4

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

share|improve this answer

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.

share|improve this answer

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 ]

share|improve this answer
2  
The answer is $1/13$. An elegant solution goes something like this: given the position of the second ace, all cards below it have equal probabilities of being an ace. In particular the probability is the same for the card on the bottom of the deck. But the (unconditional) probability of that card being an ace is $1/13$. –  Robert Israel Jan 23 '12 at 1:45

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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