Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

7.2: Parity and Counting Arguments

  • Page ID
    19403
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    This section is concerned with two very powerful elements of the proofmaking 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 alphanumeric1. 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.

    \(\begin{array} &0\;\;\;\;\; &0000\; 0000\;\;\;\;\; &\text{NUL}\;\;\;\;\;\;\;\;\;\; &64\;\;\;\;\; &0100\; 0000\;\;\;\;\; &@ \\ 1\;\;\;\;\; &0000\; 0001 \;\;\;\;\;&\text{SOH}\;\;\;\;\;\;\;\;\;\; &65\;\;\;\;\; &0100\; 0001\;\;\;\;\; &\text{A}\\ 2\;\;\;\;\; &0000\; 0010 \;\;\;\;\;&\text{STX}\;\;\;\;\;\;\;\;\;\; &66\;\;\;\;\; &0100\; 0010\;\;\;\;\; &\text{B}\\ 3\;\;\;\;\; &0000\; 0011 \;\;\;\;\;&\text{ETX}\;\;\;\;\;\;\;\;\;\; &67\;\;\;\;\; &0100\; 0011\;\;\;\;\; &\text{C}\\ 4\;\;\;\;\; &0000\; 0100 \;\;\;\;\;&\text{EOT}\;\;\;\;\;\;\;\;\;\; &68\;\;\;\;\; &0100\; 0100\;\;\;\;\; &\text{D}\\ 5\;\;\;\;\; &0000\; 0101 \;\;\;\;\;&\text{ENQ}\;\;\;\;\;\;\;\;\;\; &69\;\;\;\;\; &0100\; 0101\;\;\;\;\; &\text{E}\\ 6\;\;\;\;\; &0000\; 0110 \;\;\;\;\;&\text{ACK}\;\;\;\;\;\;\;\;\;\; &70\;\;\;\;\; &0100 \;0110\;\;\;\;\; &\text{F}\\ 7\;\;\;\;\; &0000\; 0111 \;\;\;\;\;&\text{BEL}\;\;\;\;\;\;\;\;\;\; &71\;\;\;\;\; &0100 \;0111\;\;\;\;\; &\text{G}\\ 8\;\;\;\;\; &0000\; 1000 \;\;\;\;\;&\text{BS}\;\;\;\;\;\;\;\;\;\; &72\;\;\;\;\; &0100 \;1000\;\;\;\;\; &\text{H}\\ 9\;\;\;\;\; &0000\; 1001 \;\;\;\;\;&\text{TAB}\;\;\;\;\;\;\;\;\;\; &73\;\;\;\;\; &0100\; 1001\;\;\;\;\; &\text{I}\\ 10\;\;\;\;\; &0000\; 1010 \;\;\;\;\;&\text{LF}\;\;\;\;\;\;\;\;\;\; &74\;\;\;\;\; &0100 \;1010\;\;\;\;\; &\text{J}\\ 11\;\;\;\;\; &0000\; 1011 \;\;\;\;\;&\text{VT}\;\;\;\;\;\;\;\;\;\; &75\;\;\;\;\; &0100\; 1011\;\;\;\;\; &\text{K}\\ 12\;\;\;\;\; &0000\; 1100 \;\;\;\;\;&\text{FF}\;\;\;\;\;\;\;\;\;\; &76\;\;\;\;\; &0100 \;1100\;\;\;\;\; &\text{L}\\ 13\;\;\;\;\; &0000\; 1101 \;\;\;\;\;&\text{CR}\;\;\;\;\;\;\;\;\;\; &77\;\;\;\;\; &0100\; 1101\;\;\;\;\; &\text{M}\\ 14\;\;\;\;\; &0000\; 1110 \;\;\;\;\;&\text{SO}\;\;\;\;\;\;\;\;\;\; &78\;\;\;\;\; &0100 \;1110\;\;\;\;\; &\text{N}\\ 15\;\;\;\;\; &0000\; 1111 \;\;\;\;\;&\text{SI}\;\;\;\;\;\;\;\;\;\; &79\;\;\;\;\; &0100\; 1111 \;\;\;\;\;&\text{O}\\ 16\;\;\;\;\; &0001\; 0000 \;\;\;\;\;&\text{DLE}\;\;\;\;\;\;\;\;\;\; &80\;\;\;\;\; &0101\; 0000 \;\;\;\;\;&\text{P}\\ 17\;\;\;\;\; &0001\; 0001 ;\;\;\;\;&\text{DC1}\;\;\;\;\;\;\;\;\;\; &81\;\;\;\;\; &0101\; 0001 \;\;\;\;\;&\text{Q}\\ 18\;\;\;\;\; &0001\; 0010 \;\;\;\;\;&\text{DC2}\;\;\;\;\;\;\;\;\;\; &82\;\;\;\;\; &0101\; 0010 \;\;\;\;\;&\text{R}\\ 19\;\;\;\;\; &0001\; 0011 \;\;\;\;\;&\text{DC3}\;\;\;\;\;\;\;\;\;\; &83\;\;\;\;\; &0101\; 0011 \;\;\;\;\;&\text{S}\\ 20\;\;\;\;\; &0001\; 0100 \;\;\;\;\;&\text{DC4}\;\;\;\;\;\;\;\;\;\; &84\;\;\;\;\; &0101\; 0100 \;\;\;\;\;&\text{T}\\ 21\;\;\;\;\; &0001\; 0101 \;\;\;\;\;&\text{NAK}\;\;\;\;\;\;\;\;\;\; &85\;\;\;\;\; &0101\; 0101 \;\;\;\;\;&\text{U}\\ 22\;\;\;\;\; &0001\; 0110 \;\;\;\;\;&\text{SYN}\;\;\;\;\;\;\;\;\;\; &86\;\;\;\;\; &0101\; 0110 \;\;\;\;\;&\text{V}\\ 23\;\;\;\;\; &0001\; 0111 \;\;\;\;\;&\text{ETB}\;\;\;\;\;\;\;\;\;\; &87\;\;\;\;\; &0101\; 0111 \;\;\;\;\;&\text{W}\\ 24\;\;\;\;\; &0001\; 1000 \;\;\;\;\;&\text{CAN}\;\;\;\;\;\;\;\;\;\; &88\;\;\;\;\; &0101\; 1000 \;\;\;\;\;&\text{X}\\ 25\;\;\;\;\; &0001\; 1001 \;\;\;\;\;&\text{EM}\;\;\;\;\;\;\;\;\;\; &89\;\;\;\;\; &0101 \;1001 \;\;\;\;\;&\text{Y}\\ 26\;\;\;\;\; &0001\; 1010 \;\;\;\;\;&\text{SUB}\;\;\;\;\;\;\;\;\;\; &90\;\;\;\;\; &0101\; 1010 \;\;\;\;\;&\text{Z}\\ 27\;\;\;\;\; &0001 \;1011 \;\;\;\;\;&\text{ESC}\;\;\;\;\;\;\;\;\;\; &91\;\;\;\;\; &0101\; 1011 \;\;\;\;\;&[\\ 28\;\;\;\;\; &0001 \;1100 \;\;\;\;\;&\text{FS}\;\;\;\;\;\;\;\;\;\; &92\;\;\;\;\; &0101\; 1100 \;\;\;\;\;&\setminus \\ 29\;\;\;\;\; &0001 \;1101 \;\;\;\;\;&\text{GS}\;\;\;\;\;\;\;\;\;\; &93\;\;\;\;\; &0101\; 1101 \;\;\;\;\;&]\\ 30\;\;\;\;\; &0001 \;1110 \;\;\;\;\;&\text{RS}\;\;\;\;\;\;\;\;\;\; &94\;\;\;\;\; &0101\; 1110 \;\;\;\;\;&\text{^} \\ 31\;\;\;\;\; &0001 \;1111 \;\;\;\;\;&\text{US}\;\;\;\;\;\;\;\;\;\; &95\;\;\;\;\; &0101 \;1111 \;\;\;\;\;&\underline{\;}\\ 32\;\;\;\;\; &0010 \;0000 \;\;\;\;\;&\text{}\;\;\;\;\;\;\;\;\;\; &96\;\;\;\;\; &0110 \;0000 \;\;\;\;\;&‘\\ 33\;\;\;\;\; &0010 \;0001 \;\;\;\;\;&!\;\;\;\;\;\;\;\;\;\; &97\;\;\;\;\; &0110 \;0001 \;\;\;\;\;&\text{a}\\ 34\;\;\;\;\; &0010 \;0010 \;\;\;\;\;&" \;\;\;\;\;\;\;\;\;\;&98\;\;\;\;\; &0110 \;0010 \;\;\;\;\;&\text{b}\\ 35\;\;\;\;\; &0010 \;0011 \;\;\;\;\;&\#\;\;\;\;\;\;\;\;\;\; &99\;\;\;\;\; &0110\; 0011 \;\;\;\;\;&\text{c}\\ 36\;\;\;\;\; &0010 \;0100 \;\;\;\;\;&$ \;\;\;\;\;\;\;\;\;\;&100\;\;\;\;\; &0110\; 0100 \;\;\;\;\;&\text{d}\\ 37\;\;\;\;\; &0010 \;0101 \;\;\;\;\;&\% \;\;\;\;\;\;\;\;\;\;&101\;\;\;\;\; &0110\; 0101 \;\;\;\;\;&\text{e}\\38\;\;\;\;\; &0010 \;0110 \;\;\;\;\;&\& \;\;\;\;\;\;\;\;\;\;&102\;\;\;\;\; &0110\; 0110 \;\;\;\;\;&\text{f}\\ 39\;\;\;\;\; &0010 \;0111 \;\;\;\;\;&’ \;\;\;\;\;\;\;\;\;\;&103\;\;\;\;\; &0110\; 0111 \;\;\;\;\;&\text{g}\\ 40\;\;\;\;\; &0010 \;1000 \;\;\;\;\;&( \;\;\;\;\;\;\;\;\;\;&104\;\;\;\;\; &0110\; 1000 \;\;\;\;\;&\text{h}\\ 41\;\;\;\;\; &0010 \;1001 \;\;\;\;\;&) \;\;\;\;\;\;\;\;\;\;&105\;\;\;\;\; &0110 \;1001 \;\;\;\;\;&\text{i}\\ 42\;\;\;\;\; &0010 \;1010 \;\;\;\;\;&* \;\;\;\;\;\;\;\;\;\;&106\;\;\;\;\;&0110 \;1010 \;\;\;\;\;&\text{j}\\ 43\;\;\;\;\; &0010 \;1011 \;\;\;\;\;&+ \;\;\;\;\;\;\;\;\;\;&107\;\;\;\;\; &0110 \;1011 \;\;\;\;\;&\text{k}\\ 44\;\;\;\;\; &0010 \;1100 \;\;\;\;\;&, \;\;\;\;\;\;\;\;\;\;&108\;\;\;\;\; &0110 \;1100 \;\;\;\;\;&\text{l}\\ 45\;\;\;\;\; &0010 \;1101 \;\;\;\;\;&- \;\;\;\;\;\;\;\;\;\;&109\;\;\;\;\; &0110 \;1101 \;\;\;\;\;&\text{m}\\ 46\;\;\;\;\; &0010 \;1110 \;\;\;\;\;&. \;\;\;\;\;\;\;\;\;\;&110\;\;\;\;\; &0110 \;1110 \;\;\;\;\;&\text{n}\\ 47\;\;\;\;\; &0010 \;1111 \;\;\;\;\;&/ \;\;\;\;\;\;\;\;\;\;&111\;\;\;\;\; &0110 \;1111 \;\;\;\;\;&\text{o}\\ 48\;\;\;\;\; &0011 \;0000 \;\;\;\;\;&0 \;\;\;\;\;\;\;\;\;\;&112\;\;\;\;\; &0111 \;0000 \;\;\;\;\;&\text{p}\\ 49\;\;\;\;\; &0011 \;0001 \;\;\;\;\;&1 \;\;\;\;\;\;\;\;\;\;&113\;\;\;\;\; &0111 \;0001 \;\;\;\;\;&\text{q}\\ 50\;\;\;\;\; &0011 \;0010 \;\;\;\;\;&2 \;\;\;\;\;\;\;\;\;\;&114\;\;\;\;\; &0111 \;0010 \;\;\;\;\;&\text{r}\\ 51\;\;\;\;\; &0011 \;0011 \;\;\;\;\;&3 \;\;\;\;\;\;\;\;\;\;&115\;\;\;\;\; &0111 \;0011 \;\;\;\;\;&\text{s}\\ 52\;\;\;\;\; &0011 \;0100 \;\;\;\;\;&4 \;\;\;\;\;\;\;\;\;\;&116\;\;\;\;\; &0111 \;0100 \;\;\;\;\;&\text{t}\\ 53\;\;\;\;\; &0011 \;0101 \;\;\;\;\;&5 \;\;\;\;\;\;\;\;\;\;&117\;\;\;\;\; &0111\; 0101 \;\;\;\;\;&\text{u}\\ 54\;\;\;\;\; &0011 \;0110 \;\;\;\;\;&6 \;\;\;\;\;\;\;\;\;\;&118\;\;\;\;\; &0111 \;0110 \;\;\;\;\;&\text{v}\\ 55\;\;\;\;\; &0011 \;0111 \;\;\;\;\;&7 \;\;\;\;\;\;\;\;\;\;&119\;\;\;\;\; &0111 \;0111 \;\;\;\;\;&\text{w}\\ 56\;\;\;\;\; &0011 \;1000 \;\;\;\;\;&8 \;\;\;\;\;\;\;\;\;\;&120\;\;\;\;\; &0111 \;1000 \;\;\;\;\;&\text{x}\\ 57\;\;\;\;\; &0011 \;1001 \;\;\;\;\;&9 \;\;\;\;\;\;\;\;\;\;&121\;\;\;\;\; &0111 \;1001 \;\;\;\;\;&\text{y}\\ 58\;\;\;\;\; &0011 \;1010 \;\;\;\;\;&: \;\;\;\;\;\;\;\;\;\;&122\;\;\;\;\; &0111 \;1010 \;\;\;\;\;&\text{z}\\ 59\;\;\;\;\; &0011 \;1011 \;\;\;\;\;&; \;\;\;\;\;\;\;\;\;\;&123\;\;\;\;\; &0111 \;1011 \;\;\;\;\;&\{ \\ 60\;\;\;\;\; &0011 \;1100 \;\;\;\;\;&< \;\;\;\;\;\;\;\;\;\;&124\;\;\;\;\; &0111 \;1100 \;\;\;\;\;&| \\ 61\;\;\;\;\; &0011 \;1101 \;\;\;\;\;&= \;\;\;\;\;\;\;\;\;\;&125\;\;\;\;\; &0111 \;1101 \;\;\;\;\;&\} \\ 62\;\;\;\;\; &0011 \;1110 \;\;\;\;\;&> \;\;\;\;\;\;\;\;\;\;&126\;\;\;\;\; &0111 \;1110 \;\;\;\;\;& \sim \\ 63\;\;\;\;\; &0011 \;1111 \;\;\;\;\;&? \;\;\;\;\;\;\;\;\;\;&127\;\;\;\;\; &0111 \;1111 \;\;\;\;\;&\text{DEL} \end{array} \)

    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 \(3^{\text{rd}}\) 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 river2 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.

    clipboard_e95426028650bfa3af75fe48af0857510.png
    Figure \(\PageIndex{1}\): A simplified map of Königsberg, Prussia circa \(1736\). (Copyright; author via source)

    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?

    clipboard_eace03ef52178817dddc2fcec43d54b21.png
    Figure \(\PageIndex{2}\): Euler’s solution of the “seven bridges of Königsberg problem” involved representing the town as an undirected graph. (Copyright; author via source)
    Practice

    Try drawing graphs having the following lists of vertex degrees. (In some cases it will be impossible. . . )

    • \(\{1, 1, 2, 3, 3\}\)
    • \(\{1, 2, 3, 5\}\)
    • \(\{1, 2, 3, 4\}\)
    • \(\{4, 4, 4, 4, 5\}\)
    • \(\{3, 3, 3, 3\}\)
    • \(\{3, 3, 3, 3, 3\}\)

    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?

    Practice

    (If you didn’t do the last exercise, stop being such a lame-o and try it now. BTW, if you did do it, good for you! You can either join with me now in sneering at all those people who are scurrying back to do the last one, or try the following:)

    Figure out a way to distinguish a sequence of numbers that can be the degree sequence of some graph from the sequences that cannot be.

    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 \(1^{\text{st}}\), \(3^{\text{rd}}\) and \(5^{\text{th}}\) degree sequences, and you may have discovered some version of the following

    Theorem \(\PageIndex{1}\)

    In an undirected graph, the number of vertices having an odd degree is even.

    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.

    Theorem \(\PageIndex{2}\)

    In an undirected graph, the sum of the degrees of the vertices is even.

    Proof

    The sum of the degrees of all the vertices in a graph \(G\),

    \[\sum_{v∈V (G)} \text{deg}(v),\]

    counts every edge of \(G\) exactly twice.

    Thus,

    \[\sum_{v∈V (G)} \text{deg}(v) = 2 · |E(G)|.\]

    In particular we see that this sum is even.

    Q.E.D.

    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.3 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 × 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 × 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

    Practice

    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?

    clipboard_ea2b4c873d0118bfefd6421ff5a1a7f63.png

    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 structure4. 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×n\) array containing the numbers \(1, 2, 3, . . . , 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.

    \(1\) \(6\) \(8\)
    \(5\) \(7\) \(3\)
    \(9\) \(2\) \(4\)

    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\).

    Theorem \(\PageIndex{3}\)

    A magic square of order \(n\) has a magic sum equal to \(\dfrac{n^3 + n}{2}\).

    Proof

    We count the total of the entries in the magic square in two ways. The sum of all the entries in the magic square is

    \[S = 1 + 2 + 3 + . . . + n^2.\]

    Using the formula for the sum of the first \(k\) naturals \(( \sum^{k}_{i=1} i = \dfrac{k^2+k}{2} )\) and evaluating at \(n^2\) gives

    \[S = \dfrac{n^4 + n^2}{2}.\]

    On the other hand, if the magic sum is \(M\), then each of the \(n\) rows has numbers in it which sum to \(M\) so

    \[S = nM.\]

    By equating these different expressions for \(S\) and solving for \(M\), we prove the desired result:

    \[nM = \dfrac{n^4 + n^2}{2},\]

    therefore

    \[M = \dfrac{n^3 + n}{2} .\]

    Q.E.D.

    Exercises:

    Exercise \(\PageIndex{1}\)

    A walking tour of K¨onigsberg such as is described in this section, or more generally, a circuit through an arbitrary graph that crosses each edge precisely once and begins and ends at the same node is known as an Eulerian circuit. An Eulerian path also crosses every edge of a graph exactly once but it begins and ends at distinct nodes. For each of the following graphs determine whether an Eulerian circuit or path is possible, and if so, draw it.

    clipboard_e77adc7a18a660735fc4af90ca89125e3.png

    Exercise \(\PageIndex{2}\)

    Complete the proof of the fact that “Every graph has an even number of odd nodes.”

    Exercise \(\PageIndex{3}\)

    Provide an argument as to why an \(8 × 8\) chessboard with two squares pruned from diagonally opposite corners cannot be tiled with dominoes.

    Exercise \(\PageIndex{4}\)

    Prove that, if \(n\) is odd, any \(n × n\) chessboard with a square the same color as one of its corners pruned can be tiled by dominoes.

    Exercise \(\PageIndex{5}\)

    The five tetrominoes (familiar to players of the video game Tetris) are relatives of dominoes made up of four small squares.

    clipboard_ef5c46527fecd34c795f1970be80d6cf7.png

    All together these five tetrominoes contain \(20\) squares so it is conceivable that they could be used to tile a \(4 ×5\) chessboard. Prove that this is actually impossible.

    Exercise \(\PageIndex{6}\)

    State necessary and sufficient conditions for the existence of an Eulerian circuit in a graph.

    Exercise \(\PageIndex{7}\)

    State necessary and sufficient conditions for the existence of an Eulerian path in a graph.

    Exercise \(\PageIndex{8}\)

    Construct magic squares of order \(4\) and \(5\).

    Exercise \(\PageIndex{9}\)

    A magic hexagon of order \(2\) would consist of filling-in the numbers from \(1\) to \(7\) in the hexagonal array below. The magic condition means that each of the \(9\) “lines” of adjacent hexagons would have the same sum. Is this possible?

    clipboard_efbef545b4330f900344e6a4b789c235e.png

    Exercise \(\PageIndex{10}\)

    Is there a magic hexagon of order \(3\)?

    • Was this article helpful?