Math Humor

I heard a funny joke today in my Multi-Variable Calculus class today (at least I thought it was funny):

e^x is walking down the street when he meets 2x. He says to 2x, "Hey, didn't you used to be x²?" 2x replies, "Yes, but the differential operators are out today. Watch out!"

e^x keep walking, and just as 2x said, he runs into a differential operator. The operator says, "I'm gonna differentiate you to 0!". e^x laughs and says, "Just try! I'm e^x."

The differential operator laughs back and says, "Ah, but I'm ^d/_dy."

A-Maze-Ing

Today was my last computer science lab of the semester, so I thought I'd share this problem we discussed...

The Problem:

Given a grid of empty and filled spaces, find the number of shortest paths from start to finish.

Example 1:


S 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 F

S is start, F is finish, and 0 is an empty space. Programmatically, we can determine that the answer is 84 paths. Now we just need a mathematical solution.

The length of a shortest path is 9 steps, for instance, 4 steps down and then 5 steps right. So, given 9 steps, at each step we have the option of moving vertically or horizontally, but we have to move 4 horizontal steps total. That sounds like a Combination!

Paths(S, F) = ₉C₃ = 84

And there we get our answer.

Example 2:


S 0 0 0 0 0 0
0 0 0 X 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 F

S is start, F is finish, 0 is an empty space, and X is a filled space. Programmatically, the answer is 54. Let's try combinations again.

Paths(S, F) = ₉C₃ = 84
Paths(S, X) = ₃C₁ = 3

Hmm... that doesn't help much. Or does it? 84 – 54 = 30. But where do we get a 10? On a guess, I tried:

Paths(X, F) = ₅C₂ = 10

Wow! Now we have the theory:

Number of Paths = Paths(S, F) – (Paths(S, X) · Paths(X, F))
Number of Paths = 84 – (3 · 10)
Number of Paths = 54

Does this work in other cases? Let's try it out.

Example 3


S 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 Y 0 0 0 0
0 0 0 0 0 0 F

Again, S is start, F is finish, 0 is an empty space, and now Y the a filled space. The answer is still 54.

Paths(S, F) = ₉C₃ = 84
Paths(S, Y) = ₄C₂ = 6
Paths(S, Y) = ₅C₁ = 5

Number of Paths = Paths(S, F) – (Paths(S, Y) · Paths(Y, F))
Number of Paths = 84 – (6 · 5)
Number of Paths = 54

Looks like we have a winner!

Example 4:


S 0 0 0 0 0 0
0 0 0 X 0 0 0
0 0 Y 0 0 0 0
0 0 0 0 0 0 F

In our final example, S is start, F is finish, 0 is an empty space, and this time both X and Y are filled spaces. The answer is 24.

This example combines both of the previous examples, so perhaps we can apply our theory twice:

Paths(S, F) = ₉C₃ = 84

Paths(S, X) = ₃C₁ = 3
Paths(X, F) = ₅C₂ = 10

Paths(S, Y) = ₄C₂ = 6
Paths(S, Y) = ₅C₁ = 5

Number of Paths = Paths(S, F) – (Paths(S, X) · Paths(X, F)) – (Paths(S, Y) · Paths(Y, F))
Number of Paths = 84 – (3 · 10) – (6 · 5)
Number of Paths = 24

It appears that this solution works, but I haven't tested it in any other situations yet. For now, this is my answer, and I'm sticking to it. Chris out!

Edit 2007-05-05

After thinking about it, I figured out why we multiply the two path counts. For every possible path from start to the filled square, there are a certain number of paths from the filled square to finish. All of those whole paths are no good. For example...

S 0 0 0 0 0 0   S 0 0 0 0 0 0   S 0 0 0 0 0 0
1 2 X 3 4 5 0   1 2 X 3 0 0 0   1 2 X 0 0 0 0
0 0 0 0 0 6 0   0 0 0 4 0 0 0   0 0 3 4 5 6 0
0 0 0 0 0 7 F   0 0 0 5 6 7 F   0 0 0 0 0 7 F

S 1 2 0 0 0 0   S 1 2 0 0 0 0   S 1 2 0 0 0 0
0 0 X 3 4 5 0   0 0 X 3 0 0 0   0 0 X 0 0 0 0
0 0 0 0 0 6 0   0 0 0 4 0 0 0   0 0 3 4 5 6 0
0 0 0 0 0 7 F   0 0 0 5 6 7 F   0 0 0 0 0 7 F

In the above grids, grids in the same row have the same path from start to the filled square, and different paths from the filled square to finish, and the opposite for columns. This is not all possible paths, just some examples. The number of starting paths multiplied by the number of ending paths is the total number of paths through the filled square, all of which are invalid paths. Therefore, this number is subtracted from the total number of paths to get the answer.

Edit 2007-05-07

A bit more experimentation, and I've come up with a general solution for cases where the filled spaces are only increasing; that is, filled spaces are only below and/or to the right of the previous filled space. For those with MathML enabled browsers (I think most are), you can view that solution here. For those who can't view the MathML, why not try Mozilla Firefox?

There's No Law of Conservation of Sanity?

Σ0 = 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + . . .
Σ0 = (1 − 1) + (1 − 1) + (1 − 1) + (1 − 1) + . . .
Σ0 = 1 − 1 + 1 − 1 + 1 − 1 + 1 − 1 + . . .
Σ0 = 1 + (−1 + 1) + (−1 + 1) + (−1 + 1) + (−1 + 1) + . . .
Σ0 = 1

Has something been created from nothing?

Too good to pass up...

I know this is old, but let's prove that 2 = 1.

• Let a and b be equal non-zero quantities
  
  a = b


• Multiply through by a
  
  a² = ab


• Subtract b²
  
  a² − b² = ab − b²


• Factor both sides
  
  (a − b)(a + b) = b(a − b)


• Divide out (a − b)
  
  a + b = b


• Observing that a = b
  
  b + b = b


• Combine like terms on the left
  
  2b = b


• Divide by the non-zero b
  
  2 = 1

Who can spot the fallacy?

Works Cited

"Invalid proof". Wikipedia. 26 Feb 2007. <http://en.wikipedia.org/wiki/False_proof>