Brian and Justin have been captured by prison master Andrew, and are held for questioning. Andrew has enough evidence to prove that Brian and Justin are indeed guilty, but cannot prove the entire extent of their crimes. As he is a good interrogator, Andrew splits Brian and Justin apart (somehow…) to question them individually. Each prisoner now has the opportunity to either “keep their stories straight” (cooperate) or “sell out the other” (defect). Andrew, well aware of this, presents each prisoner with the situation.

Andrew has enough evidence to put both Brian and Justin away for 3 months, but he can play one against the other to get more. If both prisoners cooperate, then he can only “reward” (outcome R) them with 3 months. If one prisoner defects and the other cooperates, then the traitor goes free (outcome T) and the sucker gets a year in prison (outcome S). If both prisoners defect then they are both “punished” (outcome P) with 6 months. In decreasing order, the preferred outcomes (for each prisoner) are then T > R > P > S. So, what would Brian and Justin do? (WWBJD?)

Consider Brian: if Justin cooperates, then Brian can cooperate and receive R or defect and receive T. Conversely, if Justin defects, then Brian can cooperate and receive S, or defect and receive P. Since T > R and P > S, it is to Brian’s advantage to defect regardless of Justin’s behaviour. The same arguments apply for Justin, so it is to both prisoners’ individual advantage to defect. If the prisoners cooperate it is better for them as a whole.

As described, this game consists of a onetime binary choice between two individuals. It can be generalized in many ways. Let’s first play the game more than once: Iterated Prisoner’s Dilemma (best reference ever: http://xkcd.com/696/). Now the actions of each prisoner would certainly influence the strategy of the other.

If the number of iterations of the game is known to both players, or if there is a known limit to the number of iterations then it is to the prisoners’ advantage to defect every time. Why?

We find out AFTER THE JUMP…
(more…)

This week the Nobel Prizes for the year 2011 will be announced. Last week another set of prizes, the Ig Nobels, were awarded to “honor achievements that first make people laugh, and then make them think”. The entire webcast is available here.

Among this year’s winners:

Chemistry: Makoto Imai et al. for their invention of the wasabi alarm.

Biology: Darryl Gwynne and David Rentz for their study of beetle mating habits with Australian beer bottles.

The complete list of winners (and from previous years which are absolute gold) can be found below.

[Improbable.com]

The legend goes…

G.H. Hardy, a Cambridge mathematician, visited his friend Srinivasa Ramanujan while he was ill. He remarked to Ramanujan that the taxicab on which he arrived was labelled 1729, an especially boring number.

Ramanujan replied: “No Hardy, 1729 is the smallest number which can be expressed as the sum of 2 cubes, in 2 ways!”

Indeed 1729 can either be expressed as 1^3 + 12^3 or as 9^3 + 10^3. This fact was known previously, but how one would know this immediately (especially before computers, and let’s not forget… Wikipedia) still amazes me.

So, what is a taxicab number? The first taxicab number is the smallest positive integer which can be expressed as the sume of two cubes. It is the number 1. The second taxicab number is the smallest positive integer that may expressed as the sum of two cubes in two ways. From above, we know that this is 1729. The third, is the smallest integer to be expressed as the sum of two cubes in three ways, and so on.

Now, it has been proven that given any integer n, there is a n-th taxicab number: a number that may be expressed as the sum of two cubes in n ways. Just to get a feeling for “scope”, the sixth taxicab number is 24153319581254312065344. This is the sort of thing that can be accomplished “easily” with computers. It makes you wonder how much more we can know about numbers by just “brute forcing” problems like this one.

Ramanujan’s story is rather tragic, and he was one of those (unfortunately few) which remind me: there are some people that are just TOO smart. How he could make such ridiculous observations (http://bit.ly/CtMy) blows me away.

Remember how weird the notion of infinity was? It gets even better. We know that not all infinities are the same, but let’s show that there is no largest infinity. Before we can do this we need to understand a (very) little set theory.

Say we have a set of objects, for example three different coloured markers. How many collections of markers can we make? Well, we can take no markers, or one marker (and there are 3 choices), two markers (here there are also 3 choices) or all three markers, for a total of 8 possible collections. If there were four markers, we would find 16 possible marker collections. For a given collection, each marker is either included, or it isn’t. So in general there are 2^N collections if we have a set of N objects.

The set of all collections of objects (in this sense) is called the power set. In
precise (but perhaps confusing) language, the power set is the set of all subsets of a given set. The size of the power set is always larger than the size of the set (a result known as Cantor’s theorem). Back to infinities, we’ll now prove by contradiction that there is no largest infinity.

Let’s assume that there is a largest infinity, and label it LI. Now let’s make a set with LI objects. This set has a power set, and by Cantor’s theorem we know that the size of power set is strictly larger than the size of the set (2^LI > LI). Thus we have a contradiction since we have assumed that LI was the largest infinity.

OK, so there’s no largest infinity, but now for the weirdest part: if we try to write a list of infinities, not only is this list infinite, but it is larger than any infinity itemized on the list!

Much of our current understanding of infinities is due to Georg Cantor. Unfortunately his ideas were dismissed by many as being “crazy” or not possible at the time. What is more unfortunate: this is not an isolated incident. Boltzmann and Galois for example were both dismissed in their respective communities, though both were founders of modern theories.

Seeing as last week all we saw were things that were unknown (and perhaps to celebrate what I hope to be my first proven theorem), why don’t we consider some strategies to establish proof? Of course there are many ways to establish proof, but different strategies work better in certain circumstances. So, let’s look at some ways to prove things.

Direct Proof

The most intuitive approach, which is probably the first avenue attempted. Say we need to establish that A leads to B. The task is then to start with A, then to show through some logical statements that we arrive at B. We could also show that NOT B leads to NOT A, which is equivalent. The latter strategy is known as proof by contrapositive.

Solve for the rest of this equation AFTER THE JUMP…
(more…)

Prime numbers are just strange, very strange. Let’s look at 2 bizarre properties.

The Goldbach conjecture

Any even number (greater than 2) can be expressed as the sum of two primes.
Try it for yourself, 4 is 2+2, 6 is 3+3, 8 is 5+3, etc. What is even weirder? It is not known whether this statement is true or false. How would we establish whether it is correct? We require either a rigorous proof or a single counter-example. Believe it or not, although much work has been done, a single counter-example has yet to be found.

Prime factorization

Say that I tell you a number is the product of two primes. Could you tell me what the primes are? 6 is clearly 2 times 3, and it is easy to see that 143 is 11 times 13. But what about 9017? Eventually, you would conclude that 9017 is 71 times 127. How about 12594917? I’ll just tell you that it’s 3527 times 3571. Notice how much more difficult it becomes as the prime numbers get larger. One would wonder: Is there a fast way to evaluate which primes they are?

For the moment, there is no known (or if there is, it is a VERY well kept secret) method of factoring products of prime numbers. The difficulty of this problem is the “magic” behind RSA public key cryptography. Judge for yourself how secure it is. The largest known prime has over 12000000 digits. Of course one could eventually try all possible combinations of prime numbers, but this would take an incredibly long time.

3 people are seated in a circle for some arbitrary, irrelevant purpose. For some reason, they decide to change seats. How many ways can they arrange themselves? It should be easy enough to see that there 6 possible rearrangements; there are 3 choices for the first seat, 2 for the second…

The simplest “movement” involves the 3 people staying where they are. If we perform a second movement after another, the end result is equivalent to another possible movement. For example, say the 3 people rotate seats clockwise twice. The 3 people could have just as easily rotated seats counter-clockwise once. Finally, for each movement, there is “opposite” movement which brings the 3 subjects back to their original seats.

Notice that the order in which we perform the rearrangements is important. We can see that if person switches chairs with person 2, then person 2 and person 3 switch we obtain a different set-up than if the rearrangements had been performed in the opposite order. There are consecutive rearrangements for which the order does not matter however. In this situation, rearrangements which involve all 3 people moving can be performed in any order.

The set of movements is an example of an algebraic object called a group. The obvious question “why would we care?” Well, groups show up anywhere there is symmetry. The rigid movements of a watch hand are described by cyclic groups. Rearrangements of objects (as above) are manifestations of the symmetric group. Symmetries of individual molecular crystals and extended solid state structures are represented by point groups and space groups respectively. Rotations are elements of the rotation group, transformations in (Minkowski) space-time are elements of the Lorentz (or more generally Poincaré) group, and (almost all) transformations in quantum mechanics are elements of the unitary group.

Outside of these physically motivated examples, group theory is awesome in its own right. Ever solved a Rubik’s cube? Notice that 3 by 3 cubes behave differently than 4 by 4 or 5 by 5 cubes?

Annoy your friends with details!
A group (G,*,e) is a set G along with a well-defined associative binary operation * for which the identity is e. Closure of the operation is implied by it being well defined. Every element g of G must have an inverse element, h, such that g*h=h*g=e.

You find yourself on stage contending in one of those old style game shows. The host presents you the challenge: “The game’s simple, all you’ve got to do is choose the right door and the dream prize is yours!” There are 3 doors, one of which guards the grand prize while the other two lead to http://sadtrombone.com/

Host: “So which door will it be? Door number one, door number two or door number three?” (canned applause)
After much arbitrary shouting from the audience…

You: “Well, (overly affectionate name for host) I’ll take door number two” (canned cheers)

Host: “Door number two, interesting choice. Let’s take a look at what’s behind door number three.”
Door number three is opened and we hear the sad trombone.

Host: “So, now that we’ve seen that it’s not door number three, are you still sure about door number two or do you want to switch to door number one?”

(Loud shouts from audience)

So, should you switch to door number one? Is there any advantage or is it the same probability either way?

Find out AFTER THE JUMP
(more…)

Math For Weirdos is a weekly column about the bizarre elements of mathematics and physics for those who enjoy to melt their brains with experimental computation.

Infinity is a weird idea, but just how weird? Would you believe that there are as many even integers as there are integers? How is this possible?

Take any integer, 5 for example, and multiply it by 2. The result (10 in our case) is an even integer, and is certainly unique. It should not be surprising that every even integer can be written as 2 times some integer. If on the other hand we take some even integer and divide by 2 the result is a unique integer, and each integer can be obtained by taking starting with some even integer. What have we done? We have defined a rule that takes an integer and produces an even integer such that there is a 1-to-1 correspondence between the two sets of numbers. This means that the two sets have the same number of elements.

This number is certainly infinite, but just how large? We call this the countable infinity, which is denoted aleph-nought. But how can infinity be countable? Take some really big number, something like 1000000. What is the next smallest integer? Well obviously it is 1000001! Given any integer we know immediately which integer is next in line, and hence we can “count” them.

What if we look at the (real) number 1.742? What is the next smallest real number? Would it be 1.743? What about 1.7421 or 1.74201? We cannot identify the next number in line since we can take arbitrarily small steps. This infinity is called the continuum, c , and is uncountable. There are as many real numbers between zero and one as there are between zero and two, and this number is the continuum.

You might ask if there is an infinity that is larger than the countable infinity yet smaller than the continuum. It has been proven that it is undecidable whether this statement is true or not. There are certainly larger infinities as well. For example, the number of possible rules which associate one real number to another is c to the power of c!

While we cannot give a genuine real world example, the following is close enough.

Get the example and much more AFTER THE JUMP…
(more…)