This section is concerned with two very powerful elements of the proof-making arsenal: “Parity” is a way of referring to the result of an even/odd calculation; Counting arguments most often take the form of counting some collection in two different ways — and then comparing those results. These techniques have little to do with one another, but when they are applicable they tend to produce really elegant little arguments.

In (very) early computers and business machines, paper cards were used to store information. A so-called “punch card” or “Hollerith card” was used to store binary information by means of holes punched into it. Paper tape was also used in a similar fashion. A typical paper tape format would involve 8 positions in rows across the tape that might or might not be punched, often a column of smaller holes would appear as well which did not store information but were used to drive the tape through the reading mechanism on a sprocket. Tapes and cards could be “read” either by small sets of electrical contacts which would touch through a punched hole or be kept separate if the position wasn't punched, or by using a photo-detector to sense whether light could pass through the hole or not. The mechanisms for reading and writing on these paper media were amazingly accurate, and allowed early data processing machines to use just a couple of large file cabinets to store what now fits in a jump drive one can wear on a necklace. (About 10 or 12 cabinets could hold a gigabyte of data).

Paper media was ideally suited to storing binary information, but of course most of the real data people needed to store and process would be alphanumeric¹“Alphanumeric” is a somewhat antiquated term that refers to information containing both alphabetic characters and numeric characters — as well as punctuation marks, etc.. There were several encoding schemes that served to translate between the character sets that people commonly used and the binary numerals that could be stored on paper. One of these schemes still survives today — ASCII. The American Standard Code for Information Interchange uses 7-bit binary numerals to represent characters, so it contains 128 different symbols. This is more than enough to represent both upper- and lower-case letters, the 10 numerals, and the punctuation marks — many of the remaining spots in the ASCII code were used to contain so-called “control characters” that were associated with functionality that appeared on old-fashioned teletype equipment — things like “ring the bell,” “move the carriage backwards one space,” “move the carriage to the next line,” etc. These control characters are why modern keyboards still have a modifier key labeled “Ctrl” on them. The following listing gives the decimal and binary numerals from 0 to 127 and the ASCII characters associated with them — the non-printing and control characters have a 2 or 3 letter mnemonic designation.

Now it only takes 7 bits to encode the 128 possible values in the ASCII system, which can easily be verified by noticing that the left-most bits in all of the binary representations above are 0. Most computers use 8 bit words or “bytes” as their basic units of information, and the fact that the ASCII code only requires 7 bits lead someone to think up a use for that additional bit. It became a “parity check bit.” If the seven bits of an ASCII encoding have an odd number of 1's, the parity check bit is set to 1 — otherwise, it is set to 0. The result of this is that, subsequently, all of the 8 bit words that encode ASCII data will have an even number of 1's. This is an example of a so-called error detecting code known as the “even code” or the “parity check code.” If data is sent over a noisy telecommunications channel, or is stored in fallible computer memory, there is some small but calculable probability that there will be a “bit error.” For instance, one computer might send 10000111 (which is the ASCII code that says “ring the bell”) but another machine across the network might receive 10100111 (the 3rd bit from the left has been received in error) now if we are only looking at the rightmost seven bits we will think that the ASCII code for a single quote has been received, but if we note that this piece of received data has an odd number of ones we'll realize that something is amiss. There are other more advanced coding schemes that will let us not only detect an error, but (within limits) correct it as well! This rather amazing feat is what makes wireless telephony (not to mention communications with deep space probes — whoops! I mentioned it) work.

The concept of parity can be used in many settings to prove some fairly remarkable results.

In Section 6.3 we introduced the idea of a graph. This notion was first used by Leonhard Euler to solve a recreational math problem posed by the citizens of Königsberg, Prussia (this is the city now known as Kaliningrad, Russia.) Königsberg was situated at a place where two branches of the Pregel river²Today, this river is known as the Pregolya. come together — there is also a large island situated near this confluence. By Euler's time, the city of Königsberg covered this island as well as the north and south banks of the river and also the promontory where the branches came together. A network of seven bridges had been constructed to connect all these land masses. The townsfolk are alleged to have become enthralled by the question of whether it was possible to leave one's home and take a walk through town which crossed each of the bridges exactly once and, finally, return to one's home.

Euler settled the question (it can't be done) be converting the map of Königsberg into a graph and then making some simple observations about the parities of the nodes in this graph. The degree of a node in a graph is the number of edges that are incident with it (if a so-called “loop edge” is present it adds two to the node's degree). The “parity of a node” is shorthand for the “parity of the degree of the node.”

The graph of Königsberg has 4 nodes: one of degree 5 and three of degree 3. All the nodes are odd. Would it be possible to either modify Königsberg or come up with an entirely new graph having some even nodes? Well, the answer to that is easy — just tear down one of the bridges, and two of the nodes will have their degree changed by one; they'll both become even. Notice that, by removing one edge, we effected the parity of two nodes. Is it possible to create a graph with four nodes in which just one of them is even? More generally, given any short list of natural numbers, is it possible to draw a graph whose degrees are the listed numbers?

When it is possible to create a graph with a specified list of vertex degrees, it is usually easy to do. Of course, when it's impossible you struggle a bit… To help get things rolling (just in case you haven't really done the exercise) I'll give a hint — for the first list it is possible to draw a graph, for the second it is not. Can you distinguish the pattern? What makes one list of vertex degrees reasonable and another not?

Okay, now if you're reading this sentence you should know that every other list of vertex degrees above is impossible, you should have graphs drawn in the margin here for the 1st, 3rd and 5th degree sequences, and you may have discovered some version of the following

A slightly pithier statement is: All graphs have an even number of odd nodes.

We'll leave the proof of this theorem to the exercises but most of the work is done in proving the following equivalent result.

The question of whether a graph having a given list of vertex degrees can exist comes down to an elegant little argument using both of the techniques in the title of this section. We count the edge set of the graph in two ways — once in the usual fashion and once by summing the vertex degrees; we also note that since this latter count is actually a double count we can bring in the concept of parity.

Another perfectly lovely argument involving parity arises in questions concerning whether or not it is possible to tile a pruned chessboard with dominoes. We've seen dominoes before in Section 5.1 and we're just hoping you've run across chessboards before. Usually a chessboard is 8 × 8, but we would like to adopt a more liberal interpretation that a chessboard can be any rectangular grid of squares we might choose.³The game known as “draughts” in the UK and “checkers” in the US is played on an \(8 \times 8\) board, but (for example) international draughts is played on a \(10 \times 10\) board and Canadian checkers is played on a \(12 \times 12\) board. Suppose that we have a supply of dominoes that are of just the right size that if they are laid on a chessboard they perfectly cover two adjacent squares. Our first question is quite simple. Is it possible to perfectly tile an \(m \times n\) chessboard with such dominoes?

First let's specify the question a bit more. By “perfectly tiling” a chessboard we mean that every domino lies (fully) on the board, covering precisely two squares, and that every square of the board is covered by a domino.

The answer is straightforward. If at least one of \(m\) or \(n\) is even it can be done. A necessary condition is that the number of squares be even (since every domino covers two squares) and so, if both \(m\) and \(n\) are odd we will be out of luck.

A “pruned board” is obtained by either literally removing some of the squares or perhaps by marking them as being off limits in some way. When we ask questions about perfect tilings of pruned chessboards things get more interesting and the notion of parity can be used in several ways.

Here are two tiling problems regarding square chessboards:

1. An even-sided square board (e.g. an ordinary \(8 \times 8\) board) with diagonally opposite corners pruned.

2. An odd-sided board with one square pruned.

Both of these situations satisfy the basic necessary condition that the number of squares on the board must be even. You may be able to determine another “parity” approach to these tiling problems by attempting the following

Exercise 7.2.5

Below are two five-by-five chessboards each having a single square pruned. One can be tiled by dominoes and the other cannot. Which is which?

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

The pattern of black and white squares on a chessboard is an example of a sort of artificial parity, if we number the squares of the board appropriately then the odd squares will be white and the even squares will be black. We are used to chessboards having this alternating black/white pattern on them, but nothing about these tiling problems required that structure⁴Nothing about chess requires this structure either, but it does let us do some error checking. For instance, bishops always end up on the same color they left from and knights always switch colors as they move. If we were used to monochromatic chessboards, we might never solve the previous two problems — unless of course we invented the coloring scheme in order to solve them. An odd-by-odd chessboard has more squares of one color than of the other. An odd-by-odd chessboard needs to have a square pruned in order for it to be possible for it to be tiled by dominoes — but if the wrong colored square is pruned it will still be impossible. Each domino covers two squares — one of each color! (So the pruned board must have the same number of white squares as black.)

We'll close this section with another example of the technique of counting in two ways.

A magic square of order \(n\) is a square \(n \times n\) array containing the numbers \(1, 2, 3, \ldots , n^2\). The numbers must be arranged in such a way that every row and every column sum to the same number — this value is known as the magic sum.

For example, the following is an order \(3\) magic square.

The definition of a magic square requires that the rows and columns sum to the same number but says nothing about what that number must be. It is conceivable that we could produce magic squares (of the same order) having different magic sums. This is conceivable, but in fact the magic sum is determined completely by \(n\).