Saturday, November 24, 2012

Criss-Cross Method: Multiplication Made Easy

In school, you are taught pretty early on how to do multiplication on paper. For instance:

x  8

That would be tough to pull off in your head. However, in school, you learn that you can simply do it in two steps.

1. 7 x 8 is 56. Write the 6 and carry the five.

x  8

2. 4 x 8 is 32. Add the five to that and you get 37.

x  8

And there you go. This works great for small problems like 2x1, 3x1, 4x1, 5x1, or even ones like 2x2 or 3x2. However, what about something like a 4x4. Your paper would look like:

x          6137
+  53532000

This method is basically the distributive property, where you are multiplying each number by every other number. For instance, a 3x3 algebraically would look like:

Let x = the first digit of the first factor
Let y = the second digit of the first factor
Let z = the third digit of the first factor
Let a = the first digit of the second factor
Let b = the second digit of the second factor
Let c = the third digit of the second factor
Let P = the product of the two factors

P = (z + 10y + 100x)(c + 10b + 100a)

Using this traditional multiplication method, this product then looks like:

P = c(z + 10y + 100x) + 10b(z + 10y + 100x) + 100a(z + 10y + 100x)

This looks pretty complicated. What this method then does is takes it one step further by distributing the a, b, and c through their parentheses. The one thing that it leaves factored out is the powers of ten that are coefficients of the a, b, and c. You don't multiply through the 10 and 100 that are in front of the b and the a.

P = [(c)(z) + (c)(10y) + (c)(100x)] + 10[(b)(z) + (b)(10y) + (b)(100x)] + 100[(a)(z) + (a)(10y) + a(100x)]

You might be thinking that you don't do that much work in your head. I mean, you've been doing this since third grade! But think through what you are doing. How are you creating the terms to add up?

The first term is created by multiplying the last digit of the second factor, or c, by each digit of the first factor. There is a multiplication method called partial products which would multiply the c by the 10y and 100x, but the traditional method uses the power of zero rule to just write the (c)(10y) to the left of the (c)(z), and the (c)(100x) to the left of that.

The second term is created similarly by multiplying the second digit of the second factor, which we denoted as b, by each digit of the first factor. However, we must remember to put a zero down first, which was something constantly driven into our heads by our math teachers. This is taking into account the ten in front of the brackets. The power of zero rule states that when multiplying by ten, we can just tack a zero onto the end of the other factor. So, we tack a zero onto the end of this number that was found by multiplying b by every digit of the first factor.

The third term is also created by multiplying the first digit of the second factor, which we called a, by each digit of the first factor. Since we have a 100 outside of the brackets, we must tack two zeros onto the end of this number.

Finally, we add up these terms, which is exactly what the equation does above to get the product.

Is this really how we want to get to our product? Can't we combine the terms in a little bit of an easier way?

Let's try it. Let's fully distribute every single term through. We will get:

P = 1cz + 10cy + 100cx + 10bz + 100by + 1000bx + 100az + 1000ay + 10000ax

How about we treat the coefficients as if they are variables. In that case, we have lots of like terms to add.

P = 1(cz) + 10(cy + bz) + 100(cx + by + az) + 1000(bx + ay) + 10000(ax)

That looks fairly simple, or at least compared to the first method. However, if you think it through, you might suspect that the numbers you are multiplying together will not be in natural places in your actual problem.

I want you to try to test this. Write the following on a piece of scrap paper lying around.

x     abc

Now, the first step is just cz. Draw a erasable line from z to c. You can see the relationship between the first two numbers being multiplied. Now, erase it.

Here's where it may appear to get awkward. (cy + bz). Draw an erasable line from c to y, and from b to z. What is a easy relationship here?

In fact, you have just made a cross. These two completely random terms have formed a cross on your paper. You can erase the cross now.

Try the third terms, which there are a lot of them! Draw lines between c and x, b and y, and a and z. Believe it or not, you will get a three-way cross, which might resemble an asterisk slightly.

If you continue this process with the other two, you will find just another cross on the left, and then a line on the left side of your problem.

Because of these crosses, this method is called the "Criss-Cross Method." With this crossing pattern in mind, let's try an example. How about 143 x 822.

x     822

If you'll remember, we first have a line on the right side of the problem, connecting the 3 and the 2. So, we must multiply three and two, which will give us six. We then place that directly under the 3 and the 2.

x     822

Now, we must draw our first cross, which is also on the right side of the problem. We have a line connecting the 4 and the 2, and a line connecting the 3 and the 2. Remember that it resembles an X, it is not two parallel lines connecting the four to the left two and the three to the right two. It is the other way around.

Let's find the products of the connected numbers. 4 x 2 = 8 and 3 x 2 = 6. If you'll remember from our algebra, we must add together these products. 8 + 6 = 14.

We cannot stick a 14 there, just like we can't do in any other multiplication method. We will have to put the four, and carry the one.

x     822    1

Now, we have our three-way cross. We must do three computations: 1 x 2, 4 x 2, and 3 x 8. Don't try to do them all at once, just do one at a time. 1 x 2 = 2, and add to that the one we carried to get three. 4 x 2 = 8, and add that to the three to get eleven. 3 x 8 = 24, and add that to the eleven to get thirty-five. We can then put the five and carry the three.

Notice that after each computation, we only had to remember one additional number. This is the power of keeping a running total after each step. The whole purpose of this is to make your final result easier and less messy, which keeping a running total will do.

x     822    3

Now, we will do the next criss-cross, which is the 1 x 2 and the 4 x 8. 1 x 2 = 2, which we can add to the three we carried to get five. 4 x 8 = 32, which we can add to that five to get thirty-seven. We will put the seven, and carry the three.

x     822    3

Now, we are in home stretch. 1 x 8 = 8, which we will add to the three to get eleven. Since there is nothing to carry over to, we will just put the eleven there.

x     822    3

Believe it or not, we have just found our answer. We can also continue this up to a 4x4, or a 5x5, or even higher if you want. The only change is the number of criss-crosses you make. For a 4x4, you do your first line, then a cross, then a three-way cross on the right side of the problem, then a four-way cross incorporating all of the numbers in the problem, followed by a three-way cross on the left side of the problem, followed by a two-way cross, followed by that same last line.

This may look a little cumbersome, especially with the gigantic crosses you have to do. However, this method is a lot easier than your traditional multiplication once you start getting into larger factors, and will take much less time to master.

Additionally, it is fun to impress your friends with. If you have them give you a 3x3 multiplication problem, you will be able to knock it out in ten seconds or less, and will not have written a single number on your paper. Since I am known for my mental math, the criss-cross method is something I can use to fool people into thinking I handled the whole problem in my head in one shot, rather than writing down each digit after I compute it.

Saturday, November 17, 2012

Game Theory: The Prisoner's Dilemma

A couple months ago, I posted several times about the fascinating aspects of game theory, which is the mathematics of games. However, the strategies that we played are formally referred to as spiteful; we won by forcing the opponent to lose. In this post, I will bring up a counterargument that brings up a case where playing spitefully will cost you the game.

This is probably the most classic game theory example: The Prisoner's Dilemma. To put it simply, two prisoners are getting charged for a crime that they most likely did together, but the police aren't sure. So, they set up a deal where they question each suspect privately, and they can choose to cooperate (admit to committing the crime) or defect (claim they did not commit the crime). The punishments are as follows:

If one prisoner cooperates and the other defects, the cooperator is let free while the defector must spend thirty years in prison.

If both prisoners defect, the police don't want to risk wasting the lives of two innocent men, so give them each an eighteen month sentence.

If both prisoners cooperate, they will be punished for their crime with a ten year sentence.

If we were to draw a matrix to represent the prisoners' payoffs, it would resemble this:

    Cooperate             -10, -10             0, -30       
Defect       -30, 0     -1.5, -1.5 

The dominant strategy is clearly to cooperate, with -10 and 0 as your payoffs verses -30 and -1.5 as your payoffs. Defecting seems to be insane.

Try playing this game with a friend repeatedly, and you will find that you both are cooperating every time, leading to a rough sentence for each of you. However, wouldn't you both be better off by both defecting?

Let's say there is a point where you stop playing, maybe twenty times. On the last one, you can get away with cooperating and your accomplice will have just earned himself a thirty year sentence. You just won the game. But maybe your friend thinks the same strategy, so you decide to betray him in the nineteenth game. And it goes on and on until you are cooperating from turn one.

There are a few strategies that seem to work well, which I will list below:

Strategy One: Defect until your friend betrays you

This strategy is the simplest of these three, and is by far the most spiteful. You start by defecting, and expect your friend to do the same. However, the moment he cooperates with the police, start betraying him. Never forgive him, as he deserves this punishment. It is hurting your payoff, but is hurting his even more.

Strategy Two: Do whatever your friend's most recent move was

This strategy is known as "Tit for Tat," which is supposed to come from this for that. Your first move is a defection, and from then on, do whatever your friend did the last turn. If he cooperates in turn two, you cooperate in turn three. This will never make you win, but you will always be extremely close, and if you were in a situation where everyone played their strategy against ten other people, you would come close to winning.

It is effective because of three main reasons (four are generally presented, but I lumped two together since they are closely related):

Niceness/Non-Competitiveness - You are starting by defecting, and it isn't striving to beat out your friend. You won't betray them at the end either, which leads to a mutual trust. As I said earlier, you can't win, so people will be happy to play against you.

Retaliation - If someone decides to betray you, you won't let it slide. You will punish them by cooperating the next turn, which will lose them points as well. In a big competition, they will not like this.

Forgiveness - After you punish your accomplice, you are back on good terms very quickly. If they are willing to regain your friendship, you are happy to start defecting with them.

Tit for Tat is personally my favorite strategy, but some people feel it is still too mean. If you are playing someone who is also doing Tit for Tat, but breaks his strategy to get a few extra points, you are going to be punishing each other each turn for the punishment they gave you. It is then impossible to forgive each other.

Strategy Three: Always defect unless your friend crosses the line

Personally, I think this strategy is too nice. You will always defect except for these four situations:

1. Your accomplice cooperates on the first turn. Immediately switch to tit for tat.
2. Your accomplice cooperates twice in three turns. Switch to tit for tat.
3. Your accomplice cooperates three times in twenty turns. Switch to tit for tat.
4. Your accomplice cooperates five times in one hundred turns. Switch to tit for tat.

It is easier to forgive your accomplice, and will eventually retaliate. However, I think the retaliation is a little to nice. Nonetheless, they are all great strategies that you won't find in your everyday game.

Saturday, November 10, 2012

Triangular Day: Sum of the Cubes is the Square of the Sum

Just like last week, today is a triangular day! It is the tenth of November and 10 is the fourth triangular number. Here are the triangular numbers just to remind you.

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, ...

Most of the proofs I've done with triangular numbers just involved some simple algebra. We just would perform the necessary operations to the explicit formula for triangular numbers n(n+1)/2 and it would simplify to the answer we wanted.

Today, I will be doing something very different that can't be proved with this method. Rather than looking at triangular numbers, let's look at cube numbers. Here are the first few:

1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, ...

Let's just add up the cubes. We will start by adding the first one, then the first two, the first three, and so on.

1 = 1
1 + 8 = 9
1 + 8 + 27 = 36
1 + 8 + 27 + 64 = 100
1 + 8 + 27 + 64 + 125 = 225
1 + 8 + 27 + 64 + 125 + 216 = 441

Do you notice any pattern with the sums? If you look closely, you'll see that they are all square numbers. But not any square numbers. Look again.

1 = 1 = (1)^2
1 + 8 = 9 = (3)^2
1 + 8 + 27 = 36 = (6)^2
1 + 8 + 27 + 64 = 100 = (10)^2
1 + 8 + 27 + 64 + 125 = 225 = (15)^2
1 + 8 + 27 + 64 + 125 + 216 = 441 = (21)^2

They are squares of the triangular numbers. When I first saw this, I was stunned that this happened, and thought there was no way this could continue to work forever. But in fact, we can prove it.

You could try doing it algebraically, but we can't represent cube numbers in a form that can be simplified. For this, we have to use something that I've mentioned before called proof by induction.

We already know it works for the first number. We know that:

1^3 = 1^2
1^3 = (1(1+1)/2)^2

Remember that triangular numbers can be found with the formula n(n+1)/2. Since we are squaring it, let's just simplify that.

(n(n + 1)/2)^2
((n(n + 1))^2)/((2)^2)
n^2(n + 1)^2/4

We know it works at some point, that is when n = 1, we can state our induction hypothesis. This is saying that for some number k, we know it will work.

1^3 + 2^3 + ... + (k - 1)^3 + k^3 = k^2(k + 1)^2/4

Now, we want to find out if we continue forward, it will keep working. In other words, we want to know if it holds true for k+1.

1^3 + 2^3 + ... + (k - 1)^3 + k^3 + (k + 1)^3 = (k + 1)^2(k + 2)^2/4

Based on our induction hypothesis, we know what the sum of the first k cubes is. So, we can substitute that into the new equation to get:

1^3 + 2^3 + ... + (k - 1)^3 + k^3 + (k + 1)^3 = (k + 1)^2(k + 2)^2/4
k^2(k + 1)^2/4 + (k + 1)^3 = (k + 1)^2(k + 2)^2/4

If you look on the left side, you will see that both terms have a factor of (k+1)^2. The distributive property says that we can "factor out" or restructure the equation so that the (k+1)^2 is multiplied at a different time. This gives us:

k^2(k + 1)^2/4 + (k + 1)^3 = (k + 1)^2(k + 2)^2/4
(k + 1)^2 • (k^2/4) + (k + 1)^2 • (k + 1) = (k + 1)^2(k + 2)^2/4
((k + 1)^2)(k^2/4 + k + 1) = (k + 1)^2(k + 2)^2/4

Now, rather than having a denominator on just one term, let's create a common denominator of 4.

((k + 1)^2)(k^2/4 + k + 1) = (k + 1)^2(k + 2)^2/4
(k + 1)^2(k^2 + 4k + 4)/4 = (k + 1)^2(k + 2)^2/4

The two sides are almost identical. The only thing that is different is the (k + 2)^2. But we can simplify that.

(k + 2)^2
(k + 2)(k + 2)
(k)(k) + (k)(2) + (2)(k) + (2)(2)
k^2 + 2k + 2k + 4
k^2 + 4k + 4

Let's substitute that in for (k + 2)^2.

(k + 1)^2(k^2 + 4k + 4)/4 = (k + 1)^2(k + 2)^2/4

(k + 1)^2(k^2 + 4k + 4)/4 = (k + 1)^2(k^2 + 4k + 4)/4

And now the two sides are equal. So, when all of the dust settled, it showed that the sum of the first k+1 cubes equalled the square of the k+1st triangular number, or the sum of the cubes is the square of the sum. In other words, the sequence continued to work from k to k+1 meaning that whatever value k is, the next value will hold true as well.

This proof is very complicated, with factoring, substituting and simplifying. But if you look at it a couple of times, it makes perfect sense and makes the fact even cooler.

Saturday, November 3, 2012

Triangular Day... times eight plus one

I don't know if you noticed, but today is a triangular day! It is the third of November and three is a triangular number. Next week is also a triangular day, and I will be mentioning probably my favorite thing about them.

Let me quickly list some triangular numbers.

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120,...

They are basically the sum of consecutive natural numbers. So, 1 = 1, 3 = 1+2, 6 = 1+2+3, and so on.

This week, I wanted to try something. In August, we tried doing a triangular number times nine plus one. That resulted in other triangular numbers, which was fairly cool.

Today, let's try taking that down a notch. We will multiply by eight and add one.

1 x 8 + 1 = 9
3 x 8 + 1 = 25
6 x 8 + 1 = 49
10 x 8 + 1 = 81
15 x 8 + 1 = 121
21 x 8 + 1 = 169
28 x 8 + 1 = 225

Do you see any pattern? This is a little bit harder than the rest, but look closely.

They are all square numbers! It is fascinating to me that triangular numbers generate squares on their own, but it is true.

1 x 8 + 1 = 9 = 3^2
3 x 8 + 1 = 25 = 5^2
6 x 8 + 1 = 49 = 7^2
10 x 8 + 1 = 81 = 9^2
15 x 8 + 1 = 121 = 11^2
21 x 8 + 1 = 169 = 13^2
28 x 8 + 1 = 225 = 15^2

How do we know this goes on forever? Well, let's try to prove it. We know that the triangular numbers follow the formula n(n+1)/2. You can click here to see the post where that was proved.

Also, notice the numbers being squared. They are 3, 5, 7, 9, 11, and so on, which are all odd numbers. They fit into the formula:

2n + 1.

So, we can set up the following equation, considering n is what term we are using in the sequence. So, for the second triangular number, n = 2.

8(n(n + 1)/2) + 1 = (2n + 1)^2

Now, we will multiply through on both sides, so there are no parentheses.

8(n(n + 1)/2) + 1 = (2n + 1)(2n + 1)
8(n^2 + n)/2 + 1 = 4n^2 + 2n + 2n + 1
4n^2 + 4n + 1 = 4n^2 + 4n + 1

And already, we see that the two things are equal.

I found this pattern especially cool because of the switch between sequences, which Fibonacci numbers do all of the time. Probably next spring, I will be talking about the fact that triangulars and squares are much closer related than you'd think. Just look at their names and you should be able to see what I mean.