7.2 Parity and Counting arguments

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 eight 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⁶⁰. 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 — The American Standard Code for Information Interchange (ASCII). ASCII uses 7-bit binary numerals to represent characters, so it contains 128 different symbols. (See Table 7.1.) 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.

Table 7.1: ASCII Table

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

Now, it only takes seven 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 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 seven 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.”

When 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 third 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⁶¹ 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. (See Figure 7.3.) 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.

Figure 7.3: A simplified map of Königsberg, Prussia circa 1736.

Euler settled the question (it can’t be done) be converting the map of Königsberg into a graph (Figure 7.4) 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.”

Figure 7.4: Euler’s solution of the “seven bridges of Königsberg problem” involved representing the town as an undirected graph.

The graph of Königsberg has four nodes: one of degree five and three of degree three. 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?

Exercise 7.5 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?

Exercise 7.6 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 1st, 3rd and 5th degree sequences, and you may have discovered some version of the following

Theorem 7.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 7.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\in V(G)} \deg(v), \]

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

Thus,

\[ \sum_{v\in V(G)} \deg(v) = 2 \cdot |E(G)|. \]

In particular we see that this sum is even.

 

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 \times 8\), but we would like to adopt a more liberal interpretation that a chessboard can be any rectangular grid of squares we might choose.⁶² 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.7 Figure 7.5 shows two five-by-five chessboards, each having a single square pruned. One can be tiled by dominoes and the other cannot. Which is which?

Figure 7.5: Two five-by-five chessboards. One with top-left square pruned. The other with the second square from the left in the top row pruned.

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⁶³ If we were used to monochromatic chessboards, we might never solve the previous two problems — unless of course we invented the colouring scheme in order to solve them. An odd-by-odd chessboard has more squares of one colour 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 coloured square is pruned it will still be impossible. Each domino covers two squares — one of each colour! (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. \[\begin{array}{|c|c|c|} \hline 1 & 6 & 8 \\ \hline 5 & 7 & 3 \\ \hline 9 & 2 & 4 \\ \hline \end{array}\]

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 7.3 A magic square of order \(n\) has a magic sum equal to \(\displaystyle\frac{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 + \ldots + n^2. \]

Using the formula for the sum of the first \(k\) positive integers ( \(\sum\limits_{i=1}^k i = \frac{k^2+k}{2}\)) and evaluating at \(n^2\) gives \[ S = \frac{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 obtain \[ nM = \frac{n^4 + n^2}{2}, \] implying that \[ M = \frac{n^3 + n}{2}. \]

7.2.1 Exercises

1. A walking tour of Königsberg 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 graph in Figure 7.6, determine whether an Eulerian circuit or path is possible, and if so, draw it.

   

   Figure 7.6: Graphs for exercise 1.

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

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

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

5. Figure 7.7 shows five tetrominoes (familiar to players of the video game Tetris) that are relatives of dominoes made up of four small squares.

   

   Figure 7.7: Five tetronominoes

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

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

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

8. Construct magic squares of order 4 and 5.

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

   

   Figure 7.8: Hexagonal array

10. Is there a magic hexagon of order 3?

---

60. “Alphanumeric” is a somewhat antiquated term that refers to information containing both alphabetic characters and numeric characters — as well as punctuation marks, etc.↩

61. Today, this river is known as the Pregolya.↩

62. 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.↩

63. 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 colour they left from and knights always switch colours as they move.↩