Different problems aren’t always different

Magic Squares are much less frequent than latin squares in computer science (on which we may come back in the future), but they have a number of (fun) applications.

Historically, magic squares are tied to numerology, alchemy and other esoteric sytems. However, as you may already know, I’m not interested in pseudoscience except to debunk it, so this post isn’t about using magic squares turtles to predict the level of the river running behind your house.

Albrech Dürer's Melancholia I

Albrech Dürer's Melancholia I

No, I’m rather going to talk about seeing connections between things where there are apparently none, and how solving a problem may lead to the solution of the (apparently) unrelated problem. Consider the following magic square (the only 3×3 square, once removed from rotations, mirrors, etc.):

8 1 6
3 5 7
4 9 2

This magic square has a magic constant of 15, that is, each row, column and diagonals add to 15.

Now consider the following “game”. The numbers are layed out linearly 1,2,3,…,8,9. Two players confront; each pick a number, the first that is capable of adding three of its picked numbers to 15 wins the game.

That game sounds rather hard and not very fun. Or is it that hard? Well, if a player plays with O and the other with X, and the numbers are arranged in the 3×3 magic square, well… you’ve got tic-tac-toe, which isn’t remotely hard to play, since you can even build a tinkertoy computer to play it!

O   X
  O O
X X X

There are other applications of magic squares beyond tic-tac-toe although most of them seems to be recreational mathematics and in number theory.

*
* *

Each of us has a different walk of life, know different things, and are or have been interested in his own eclectic choice of science topics, whether it’s programming languages theory, number theory, graph theory, algorithmics, or data compression. When we feel a problems sounds like or looks like another problem we know well (or merely better) in another context, I think we should take time to see if there’s a mapping between the problem at hand and something else, see if there’s a possible reduction.

Reductions aren’t always easy to find. They may bring you very far from your original problem’s statement, but they may also bring you in a solution space where the problem is easy/easier to solve, with solid theory and fast algorithms, where you benefit from the works of others.

Just another way of saying that many things share unlikely connections; and that we should be looking for them.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: