1.2: Magic Squares

Magic Squares
A magic square is an \(n \times n\) grid of numbers 1, 2, all the way up to \(n^2\). The numbers are placed in such a way that each row, column, and diagonal has the same sum \(s\), which is called its magic sum. Here's a magic square of order 4 (\(n = 4\)):

The magic sum for the square is 34.

The sum of all integers in a magic square follows this formula:

$$1 + 2 + 3 + \cdots + n^2 = \frac{n^2(n^{2} + 1)}{2}$$

Each row has the same magic sum \(s\). Since there are \(n\) rows, you can equate it with \(1 + 2 + 3 + \cdots + n^2\) to get:

$$ns = \frac{n^2(n^{2} + 1)}{2}$$

Or, cancelling \(n\),

$$s = \frac{n(n^{2} + 1)}{2}$$

The challenge is to find what values of \(n\) have a magic square, and then find general methods for making them. For \(n = 2\) there is no magic square, since \(s\) would equal 5, violating the rules set up for the squares. For the rest of the values, a square can be made.

de la Loubère's Method
There is a method devised by de la Loubère for finding magic squares when \(n\) is odd. You start from 1 then go all the way to \(n^2\) following this pattern:

• Put 1 in the middle square of the top row.
• For each successive number, put it in the square that is up and to the right of the previous square.
• When you reach the top row, put the next integer in the bottom row.
• When you reach the rightmost column, put the next integer in the left row.
• When you're placing numbers in the upper-right square and it's filled, place the number instead in the square immediately below the last square that was filled.

Here's a magic square of order 5 that follows these rules. See if you can follow along with it.

There are, of course, other methods, but they won't be mentioned here.

Magic Cubes

As always, let's take it to the next step. Define a magic cube of order \(n\) as an \(n \times n \times n\) cubical array made of the numbers \(1, 2, 3, \cdots, n^3\) such that for all lines parallel to the edge of a cube, the two diagonals of each cross section of the cube, and the four space diagonals, the sum of the numbers comes out to magic sum \(s\).

The value of \(s\) is \(\frac{n^{4} + n}{2}\). 

It is known that there's no magic cube of order 3. Let's see why. First, suppose we have a magic cube of order 3. Its magic sum would be 42. Take any 3x3 slice (plane) of it. You get a matrix of numbers of this style:

$$\begin{bmatrix}a\ b\ c\\x\ y\ z\\d\ e\ f\end{bmatrix}$$

With it being a magic square, each of the following sums equal 42. They follow the rules laid out in the definition for a magic square.

$$a + y + f\\b + y + e\\c + y + d\\a + b + c\\d + e + f$$

If you subtract the sum of the last two equations from the sum of the first three, everything but the \(y\) cancels out. You're left with \(3y = 42\) or, if you reduce, \(y = 14\). But this means 14 would have to appear in the cube seven times - in the dead center of the cube and in the middle of each face. But a number can only appear once in a magic cube, therefore there is a contradiction. From this we conclude, you can't have a magic cube of order 3.

There is more to it but, with this just being an introductory example, we'll stop here.

1.1: Perfect Cover of Chessboards

Here's a silly example of how combinatorics can be used. We're going to cover a chessboard with dominoes, then see how far we can generalize it.

Perfect Cover
Think of a typical chessboard. It's 8 squares by 8 squares in size, with alternating black and white colors. Now think of a pile of dominoes, each of which are big enough to cover exactly two squares on the chessboard. Question: can you completely cover the chessboard with those dominoes, where none of the dominoes hangs off the board? A situation where you can do this is called a perfect cover.

The answer is, yes, of course you can have such a situation, a perfect cover. That seems nice enough. Now let's go a step further and think on a more abstract level.

Discrete Math and Abstraction
Something you're going to discover early on is that in discrete math, things are taken to the abstract a lot. Numbers get replaced with variables, and we discover general patterns behind things. Let's see some of this abstraction in this problem.

You'll also see shortly why this is called discrete math. You're going to find (count) how many ways you can cover arbitrary chessboards. This isn't continuous - you're not finding the way to cover, say an 8x8, 8x8.0001, 8x8.0002, 8x8.003., etc. chessboard. We're using whole numbers here. On a Cartesian (x-y) graph these would be dots, not a line.

Chessboards of m-by-n Size
Let's look beyond 8-by-8 chessboards, and now consider m-by-n chessboards. This kind of "chessboard" is one that could be any number of squares wide by any number of squares - 5x3, 100x100, 7x99, and so on. On what dimensions can you have a perfect cover?

A moment's thinking will lead you to say there's a perfect cover whenever either \(m\) or \(n\) are divisible by 2. More generally, it's when either of these variables are even. (When dealing with discrete math, always remember to generalize and look for more than one answer!) If you do \(m \times n\) you get an even number of squares so you can also say you get a perfect cover if the number of squares is even. This makes sense. Imagine a 3x3 board, the same dimensions as a tic-tac-toe board. You're not going to get a perfect cover on that no matter how much you try. But for any \(m \times n\) board, if either dimension is even, you have a perfect cover.

Clipped Chessboards
Now take a standard 8-by-8 chessboard, and remove the upper-left and lower-right corners. Can you still have a perfect cover?

It turns out you can't. When covering the board, the domino will cover a black square and a white square. Therefore in order to have a perfect cover you need to have an equal number of both colors. When you remove the corners of a chessboard, you remove two of the same color. On the 8-by-8 chessboard, you go from, say, 32 black and 32 white, to 32 black and 30 white. That can't be a perfect cover.

Cliffhanger
Let's generalize. Does this same rule follow for any \(m \times n\) board? Not necessarily. Consider this case: the squares below and to the right of the upper-left corner square are removed. Then it's impossible to have a perfect covering no matter what, because there's no black square available.

At this point, the book stops asking about the dimensions of the chessboard, so we'll do so as well. Instead, it moves on to the domino. What if we change the size of the domino from 2 squares to some arbitrary number b?

b-ominoes

A b-omino is a 1-by-b object that covers a certain number of objects. A 1-omino is a monomio, a 2-omino is a domino, and anything above 2 will just be referred to by its numbers. Here's a 5-omino:

The definition of a perfect cover says the same: the b-ominos must completely cover the board without anything overlapping, falling over the board, and by definition the pieces each cover b spots. When does an \(m \times n\) board have a perfect cover of b-ominoes?

If we go back to the example of  dominoes on a regular chessboard, you can get part of the answer. b must be a factor of m or n. But is this enough? The textbook goes a bit more into detail and considers two cases: when b is a prime number, and when it's not.

Suppose b is a prime number, and you can get a perfect cover of b-ominos on an m-by-n board. Given what we already know, we can assume that b is a factor if \(m \times n\) and therefore a factor of either m or n. 

What if it's not a prime number? We want to show that when we divide m and n by b, we get a remainder for one or both of them. So do the division. You get quotients p and q, and remainders r and s.

$$m = pb + r, \ where\ 0 \le r \le b - 1\\
n = qb + s,\ where\ 0 \le s \le b - 1$$

That sounds weird, so let's use some real-world numbers. Given a 7x8 board and 3-ominoes, divide 7 and 8 by 3. 7 divided by 3 is 2 with a remainder of 1, and 8 divided by 3 is 2 with a remainder of 2. So those equations become:

$$7 = 2 \times 3 + 1\\
8 = 2 \times 3 + 2$$

The goal is to show that r is zero. First we constrain \(r \le s \). If the numbers we're given has an r larger than s - for instance, if the board is 8x7, not 7x8 - just switch the two numbers around. If r = 0, then a perfect cover of the board is possible with b-ominoes.

b-by-b Board with b Colors
At this point we have generalized board size and domino size. We have seen whether or not there can be a perfect cover with these. The last thing we will do is generalize the number of colors on the board. Because this is an example, some constraints will be put on the size of the board and dominoes. Replace the number of colors on the board from 2 to b, the size of the dominoes will be b (so they'll be b-ominoes), and let the dimensions of the board (m and n) both be b. Is there a perfect cover for this?

The board is colored in a specific way. Instead of color names (red, orange, blue...) numbers are used. Note that in this example, the order is 1, b, b-1, all the way down to 2.

So if this were done with \(b = 4\), the top row would be 1, 2, 3, 4; the second row 4, 1, 2, 3; the third row 3, 4, 1, 2; and the bottom row 2, 3, 4, 1.

Taking the board that was just made, make a larger board of size \(m \times n\) using whole copies of this board and also segments of it. This definitely calls for an example. With \(b = 4 \), \(m = 10\), and \(n = 11\), you can get the following board:

Because there are b colors and we're using b-ominoes, each b-omino will cover each color once. Since whole b-ominoes are being used (nothing's hanging off the board) and they cover each color once, there is the same number of each color on the larger board we assembled. Let's divide this bigger board into three sections. Each section has a blue border:

• The upper pb-by-n part (the upper 8x11 part in our example)
• The lower left r-by-qb part (2x8)
• The lower right r-by-s part (2x3)

Recall the equations for m and n from a few paragraphs ago to figure out how these numbers were found, or keep going if you're confident with these things. As a side note, observe that p is how many vertical b-ominoes would be used in each column, r would represent how many uncovered squares remain in the column if only vertical pieces were used, n is how many horizontal b-ominoes would be needed to cover a row, and s is how many uncovered squares would be leftover using only horizontal pieces.

In the upper part, each color appears \(p \times n\) times - in this case, \( 2 \times 11 = 22 \) times. In the lower left each color will be present \(q \times r\) times, which comes out to \( 2 \times 2 = 4\) times.

The question becomes, how many times does each color appear in the lower right area? There are \(r \times s\) squares in the section. Each color appears in a row exactly once, and there are b colors, so there are also \(r \times b) colors in the section. Equate the two:

$$rb = rs$$

If r does not equals zero, we can cancel it from both sides to get:

$$b = s$$

However, this contradicts the condition of \(s \le b - 1\) so it can never happen. r must always be zero. This is the condition needed to have a perfect cover. Our board has a perfect cover.

At this point we have generalized the problem to the point of madness. Because the math has worked out nicely we can conclude that an m-by-n board has a perfect cover if and only if b is a fact of m or n.

Trivial Covers

Define a trivial cover as one where all the b-ominoes are either all horizontal or all vertical. You can say that an m-by-n board has a perfect cover of b-ominoes if and only if it has a trivial cover.

This doesn't mean the only perfect covers possible are trivial covers, just that trivial covers are part of the total possible list of perfect covers.

Fault Lines

The last mental exercise for the section. Imagine a 4-by-4 chessboard perfectly covered with 8 standard dominoes. The task: show that it's possible to divide the board into two horizontal or vertical pieces without cutting through a domino. The line where this cut is made is called a fault line.

Think of it this way: the 4x4 board is composed of two smaller boards which also have perfect covers. Since we don't know the actual dimensions of the two sub-boards, we can just say they are k-by-4 and (4-k)-by-4. 

Now suppose there is a board where there is no fault line. The dominoes are placed on the board in such a way that each of the three vertical lines and each of the three horizontal lines in between the squares are all crossed by at least one domino somewhere. You can't divide this into two sub-boards.

Let \(x_1, x_2, x_3\) be the number of dominoes that cross over each horizontal line from top to bottom. The lack of a fault line means each of these variables has to be positive. Because of the nature of dominoes covering two squares each, each of the x's presented must be even. We get the formula:

$$x_1 + x_2 + x_3 \ge 2 + 2 + 2 = 6$$

Which means there are at least 6 vertical dominoes on the board, because each x counts dominoes. Similarly, we may conclude 6 horizontal dominoes exist. But the initial condition calls for only 8 dominoes. Since \(12 \gt 8\), there is a contradiction. You can't make a perfect cover on a 4x4 board without having some kind of fault line. (Go ahead and try a few times in your head if you're not convinced. Sometimes, playing things out mentally will reveal information.)

Confused Yet?

If you didn't fully understand everything in this section, it's alright. I've spent several days putting this post together, and there are one or two pieces that don't quite make sense to me. Some facts are presented without giving an explanation. You can only fit so much in a textbook. At the end of the chapter there will be problems similar to this one that can be used to work out the ambiguities.

MathJax

This blog will use a JavaScript library called MathJax. With MathJax, specifically-formatted plain text will be turned into mathematical symbols and variables to make it easier to understand the material presented.

This roughly reads as "there exists a variable x, where x is in the set V, such that x is less than 10": $$\exists x \{x \in V : x \lt 10 \}$$

Here's an example of summation notation: $$\left( \sum_{x_1+x_2+x_3=k}^n x_1^a x_2^b x_3^c \right)$$

I'm not even going to try and say what that previous line means. I'm just glad I'm smart enough to understand how that works.

Here's a simple formula of the $$y = mx + b$$ format: $$f\left(x\right) = \frac{1}{2}x+5$$

And lastly, here's a couple formulas very important to discrete math. The equation for a combination is \( \frac{n!}{k!(n-k)!} \) which is represented as \[ \binom{n}{k} \]

Get MathJax here.

Introduction and Purpose

Hello!
This is my discrete mathematics blog. Here I will go through the topics and concepts of discrete mathematics, and I welcome you to come along, learn with me, and ask questions along the way!

Why are you doing this?
My university requires a class called Discrete Mathematics for my major. I've taken it two times now, and both times I've done poorly. Not only is this a blow to my GPA, it's taken a major hit out of my self-esteem. In order to make up for both of these things, I have decided to systematically go through the textbook (and other resources) and learn the material on a deep, comprehensive level. My goal is to go through the material that has been covered in the lectures and gain enough understanding that I could pass the class when I next take it, and also help others going through trouble with it.

What is discrete mathematics?
Discrete mathematics is a branch of math which seems to be gaining popularity. I couldn't find a good definition for it, but you might say that it's about counting things - counting how many objects are in a group, how many ways you can order things, etc. It's called discrete because it's not continuous. Let me explain that: I'm assuming, if you're looking for discrete math, you've probably got some experience with calculus. Calculus is continuous because you're playing with lines and graphs and things of that sort. Discrete math is discrete because you're just dealing with a finite number of objects, not entire lines. This will make more sense as time goes on.

On this blog, two main areas of discrete math will be looked at:

• Combinatorics - how many ways you can order things. Example: if you've ever done something like try to figure out how many ways you can order the letters A, B, and C, you've done a combinatorical problem.
• Graph theory - describes how things are related to each other. Example: have you ever looked at a map to see what roads to take to go from your home town to another city? The towns and streets make up a graph, and you were looking for the shortest path from your town to another.

What textbook are you using?

I will mainly be using Introductory Combinatorics, 5th Edition by Richard Brualdi. This is the book I've used for the last two semesters. I personally think it's a bit of a dry read. I will also dive into Discrete Mathematics and Its Applications, 7th Edition by Kenneth H. Rosen for a few chapters. It strikes me as more user friendly, but it doesn't have quite the same mathematical depth.

How will you do this?

I'm a concrete thinker. While I can handle things that are theoretical or abstract, it takes me a bit longer to really absorb them. Discrete math is a field that deals with a lot of theory. This is one of the things that put me at such a disadvantage in the two times I took the class. Plus I'm also not very quick when it comes to math beyond algebra and geometry. Therefore this blog is going to be decidedly detail-oriented. When I feel like things start to get too abstract, I'll be sure to include a small example using actual numbers. By doing that you can better get a "feel" of how the theory plays out. Concrete examples help me visualize how things work, and I imagine it will help others as well.

I'm also going to work on the problems at the end of each chapter to Introductory Combinatorics. That's because math is one of those fields that are best learned by practice and repetition. Particularly when you're a slow learner for it like me. I might also scour the Internet for other problems and resources.

Using subscripts and superscripts gets messy fast. I'm going to try and use LaTeX, a program that lets you type in code that turns text into something more mathematical looking.

Prerequisite Knowledge
If you're looking into discrete math, I'm going to assume you know algebra and calculus. There won't be a lot of calculus involved, but it's good to know for some sections. It also helps to be generally well versed with how to do math. You don't need to be a genius with it, but most problems will require you do a specific thing to reach the answer, and if you don't know the right property to use, it can be a headache.

Discrete Math and Time
If there is something I've learned about working discrete math problems, it's that they are definitely not things you can do in just a couple minutes. Usually the questions are going to require multiple steps to reach your intended goal. Occasionally, and rather frustratingly, they seem to rely on knowing some obscure fact about the numbers and variables at play. I assume this improves over time as you become familiar with the material and the theories.

Topics to Cover
Here's a list of some of the topics that will be covered on this blog.

• Basic set theory
• Permutations
• Combinations
• Multisets
• Pigeonhole Principle
• Ramsey's Theorem
• Induction
• Binomials
• Multinomials
• Pascal's Triangle
• Inclusion-Exclusion Principle
• Dearrangements
• Important number sequences
• Generating Functions
• Recurrence Relations
• Graphs
• Eulerian paths, cycles, and related concepts
• Hamilton paths, cycles, and related concepts
• Bipartite graphs
• Graph colorings
• Networks
• And a few other things here and there...