Take a strip of squares two rows high and \(n\) columns long, and a supply of dominoes. Three questions can be asked about it. Can the strip be covered exactly? If so, in how many ways? And if one square is removed from the strip, can what remains be covered?

The three questions concern the same object and are settled by three different kinds of argument. The first asks for existence, and an example answers it: stand \(n\) dominoes upright. The second asks for a number, and Exercise 7.9 found it with a recurrence. The third asks whether something is impossible, and no amount of failed attempts answers that; what answers it is the observation that \(2n-1\) squares is an odd number and dominoes cover squares two at a time. Seven chapters have supplied the methods. Each chapter’s exercises announced, by their position, which method to use. Outside a textbook nothing announces it. This last chapter is about the step that comes before any method: reading a claim closely enough to see what kind of evidence would settle it. It contains no new theorems of its own to memorize. It reorganizes what you know around the question “what is being asked?”

8.1 What kind of claim is it?

Chapter 1 sorted statements by logical form, and the form of a claim is still the best guide to its proof. In discrete mathematics the forms that occur again and again are few.

The fifth row deserves emphasis because it is where incomplete answers are most common. A question of the form “for which \(n\) is this possible?” is a biconditional, and Chapter 1 said that a biconditional needs two proofs. Showing that the condition is necessary usually takes an invariant or a count. Showing that it is sufficient takes a construction. The two halves use different tools, and an answer that supplies only one half has answered a different question.

The table is not an algorithm. It says where to begin. Many problems need a second look after the first method stalls, and the remaining sections are about that second look.

8.2 One claim, several proofs

When a claim can be reached by more than one method, the methods do not merely confirm each other. Each proves something slightly different along the way.

8.3 Both directions: invariants and constructions

An invariant can prove that a target is unreachable. It can never, by itself, prove that a target is reachable: the states sharing the invariant with the start may or may not all be attainable. The earlier chapters contain both outcomes. In the jug problem the invariant was the whole story; every multiple of the greatest common divisor could be measured. In the erasing game of Example 3.9 the parity invariant excluded the even final numbers, and a separate search was needed to see that all the odd ones occur. For degree lists, parity excluded some lists and left others, such as \(4,4,4,1,1\) , that fail for a different reason. A classification is finished only when the obstruction is matched by a construction.

8.4 Certificates

Consider how differently the two possible answers to a yes-or-no question may be supported. Asked whether \(91\) is composite, one can reply “yes: \(91=7\cdot 13\) ”, and the listener can check the reply by one multiplication without knowing how the factors were found. Evidence of this kind, short and checkable without trust, is a certificate.

Several theorems of this book can be read as statements that both answers to some question have certificates.

In each row, the easy observation is that the two certificates cannot both exist. The theorem is the statement that one of them always does. Theorems of this shape are especially valuable, because they turn a search of unknown length into a search with a guaranteed end: look for either certificate, and one will turn up.

Not every question is so well supplied. To show that two graphs are isomorphic, a bijection is a certificate. To show that they are not, one hopes for a distinguishing invariant, but no short list of invariants is known to separate all non-isomorphic graphs. To show that a graph can be coloured with three colours, a colouring is a certificate; for the answer no, nothing comparably short is known in general. Whether such questions have short certificates on both sides, and what follows for the difficulty of answering them, is the starting point of Discrete Optimization (math.discrete-optimization.models-complexity).

The practical lesson is a habit: finish an answer by stating its certificate. If the answer is “yes, it is possible”, exhibit the object. If the answer is “no”, name the invariant, the odd cycle, or the divisor. An answer without a certificate is an opinion.

8.5 Fitting the tool to the move

A method can be the right kind and still be the wrong instance. An invariant must be chosen to fit the moves or the pieces involved, and the first one to come to mind may be too weak to exclude anything.

Example 8.5: An invariant that fails and one that works

Claim. A \(6\times 6\) board cannot be covered exactly by tiles of size \(1\times 4\) , placed horizontally or vertically.

There are \(36\) squares, and \(36=9\cdot 4\) , so counting squares gives no obstruction.

A first attempt. Colour the board like a chessboard. Each tile covers two squares of each colour, and the board has \(18\) of each. Nothing is contradicted. The colouring that settled the board with two missing corners is useless here, because it was designed for dominoes.

A colouring fitted to the tile. Number the rows and columns from \(0\) to \(5\) and give the square in row \(i\) and column \(j\) the colour \((i+j)\bmod 4\) . Along any row or column the colours run through \(0,1,2,3\) in cyclic order, so a \(1\times 4\) tile, wherever it is placed, covers exactly one square of each of the four colours. Nine tiles would therefore cover nine squares of each colour. But the board has \(9\) , \(10\) , \(9\) , and \(8\) squares of colours \(0\) , \(1\) , \(2\) , \(3\) respectively. So no covering exists.

An exhaustive search confirms that the \(6\times 6\) board has no covering, while the \(4\times 6\) board, for which the four colours occur \(6\) times each, has \(4\) coverings. The method, a colouring under which every piece covers a fixed pattern, was right both times. What changed was the choice of colouring, and the guide to that choice is the piece: a tile of length \(4\) calls for a colouring with period \(4\) .

The same care applies to every tool in the book, and the mismatches fall into a short list.

Common mistake. Treating a necessary condition as sufficient. An even degree sum does not guarantee a graph; divisibility of the target by the greatest common divisor guarantees an integer solution of \(ax+by=c\) and not a solution in natural numbers; equal numbers of squares of each colour do not guarantee a tiling. After finding an obstruction, ask separately whether its absence is enough, and prove that by a construction or find a counterexample.

Common mistake. Applying a rule outside its hypotheses because the situation resembles one where it worked. The product rule needs the number of options at each stage to be independent of earlier choices. The division rule needs every object to be counted the same number of times. Cancellation in a congruence needs the cancelled factor to be coprime to the modulus. Induction on structures needs every larger object to reduce to a smaller one. Before using a theorem, say its hypotheses aloud and check each against the problem in front of you.

8.6 Several chapters in one argument

Real questions do not respect chapter boundaries. The last example of the book asks a question about an algorithm from Chapter 4 and answers it with induction from Chapter 3 and the growth estimates of Chapter 7.

Exercises

1. For each claim say which row of the table in Section 8.1 it belongs to and name a method you would try first, without carrying out the proof: (a) every tree with at least two vertices is bipartite; (b) no integer of the form \(4k+3\) is a perfect square; (c) the number of strings of five decimal digits whose digits sum to \(7\) ; (d) the set of \(n\) for which \(K_n\) has an Euler circuit; (e) among any \(100\) integers, two have a difference divisible by \(99\) ; (f) the sequence with \(a_0=2\) and \(a_n=3a_{n-1}-2\) satisfies \(a_n=3^{n}+1\) .

   Answer

   (a) A universal statement about trees; induction on the number of vertices, removing a leaf, or the level colouring of Theorem 6.18. (b) An impossibility; a congruence, namely the squares modulo \(4\) . (c) A count; stars and bars for five natural numbers adding to \(7\) , where the upper bound of \(9\) on each digit is harmless because \(7<10\) . (d) A classification; two directions, both given by Theorem 6.22. (e) An existence statement; the pigeonhole principle on remainders modulo \(99\) . (f) A closed form; guess and verify by Proposition 7.2.

2. Prove in two ways that \(n^{3}-n\) is divisible by \(6\) for every integer \(n\ge 0\) : by induction, and by showing that \(n^{3}-n=6\binom{n+1}{3}\) . Say what the second proof tells you that the first does not.

   Solution

   By induction. For \(n=0\) , \(0^{3}-0=0\) is divisible by \(6\) . Assume \(6\mid k^{3}-k\) . Then

   \[ (k+1)^{3}-(k+1)=(k^{3}-k)+3k^{2}+3k=(k^{3}-k)+3k(k+1). \]

   The product \(k(k+1)\) of two consecutive integers is even, so \(3k(k+1)\) is divisible by \(6\) , and the sum of two multiples of \(6\) is a multiple of \(6\) .

   By counting. Factor \(n^{3}-n=(n-1)n(n+1)\) . The number of \(3\) -element subsets of a set with \(n+1\) elements is \(\binom{n+1}{3}=\frac{(n+1)n(n-1)}{6}\) , which is an integer because it counts something. Hence \(n^{3}-n=6\binom{n+1}{3}\) is \(6\) times an integer. For \(n=0\) and \(n=1\) both sides are \(0\) .

   The induction shows that the claim is true. The second proof shows what the quotient is: \((n^{3}-n)/6\) is the number of ways to choose three objects from \(n+1\) . It explains the divisibility by exhibiting the integer, and it generalizes at once: the product of any \(k\) consecutive integers is divisible by \(k!\) .

3. Prove in two ways that \(\sum_{k=0}^{n}\binom nk 2^{k}=3^{n}\) : from the binomial theorem, and by counting the functions from \([n]\) to \(\{0,1,2\}\) according to the number of elements not sent to \(0\) .

   Solution

   From the binomial theorem. Put \(x=2\) and \(y=1\) in Theorem 5.8: \((2+1)^{n}=\sum_{k=0}^{n}\binom nk 2^{k}1^{n-k}\) , which is the claim.

   By counting. There are \(3^{n}\) functions from \([n]\) to \(\{0,1,2\}\) , by Corollary 5.3. Sort them by the number \(k\) of elements of \([n]\) that are not sent to \(0\) . To specify such a function, choose which \(k\) elements are not sent to \(0\) , in \(\binom nk\) ways, and then choose for each of them one of the two values \(1\) and \(2\) , in \(2^{k}\) ways; the remaining elements are sent to \(0\) . So there are \(\binom nk 2^{k}\) functions with exactly \(k\) elements not sent to \(0\) . The classes for different \(k\) are disjoint and cover all functions, so the sum over \(k\) is \(3^{n}\) .

   The combinatorial proof is the proof of the binomial theorem itself, specialized: choosing a term from each factor of \((2+1)^{n}\) is choosing a value for each element.

4. Count the domino coverings of a \(2\times n\) strip that contain exactly \(k\) pairs of horizontal dominoes, by describing such a covering as a sequence of blocks. Combine your answer with Exercise 7.9 to obtain an identity for \(F_{n+1}\) , and verify it for \(n=10\) .

   Solution

   In a covering of the \(2\times n\) strip, every domino is either vertical, filling one column, or one of a pair of horizontal dominoes that together fill two adjacent columns, as shown in the solution of Exercise 7.9. So a covering is a sequence of blocks read from left to right, each block being a single column (one vertical domino) or a double column (a horizontal pair). A covering with exactly \(k\) horizontal pairs has \(k\) double blocks and \(n-2k\) single blocks, hence \(n-k\) blocks in all, and it is determined by which \(k\) of the \(n-k\) positions in the sequence hold the double blocks. There are \(\binom{n-k}{k}\) such coverings.

   Summing over \(k\) and using \(d_n=F_{n+1}\) from Exercise 7.9,

   \[ F_{n+1}=\sum_{k\ge 0}\binom{n-k}{k}, \]

   the sum running over \(k\) with \(2k\le n\) . For \(n=10\) : \(1+9+28+35+15+1=89=F_{11}\) .

5. For which positive integers \(n\) can the set \(\{1,2,\dots,n\}\) be divided into two subsets with equal sums? Prove necessity with a parity argument and sufficiency with a construction that passes from \(n\) to \(n+4\) .

   Solution

   The answer is: exactly when \(n\) leaves remainder \(0\) or \(3\) on division by \(4\) .

   Necessity. If the set splits into two subsets of equal sum, the total \(\frac{n(n+1)}{2}\) is twice that common sum, hence even, so \(4\mid n(n+1)\) . One of \(n\) and \(n+1\) is odd, so \(4\) divides the other: \(n\equiv 0\) or \(n\equiv 3\pmod 4\) .

   Sufficiency. For \(n=3\) take \(\{1,2\}\) and \(\{3\}\) . For \(n=4\) take \(\{1,4\}\) and \(\{2,3\}\) . Now suppose \(\{1,\dots,n\}\) has been split into subsets \(X\) and \(Y\) of equal sum. The four new numbers \(n+1,n+2,n+3,n+4\) split into the pairs \(\{n+1,n+4\}\) and \(\{n+2,n+3\}\) , each with sum \(2n+5\) . So \(X\cup\{n+1,n+4\}\) and \(Y\cup\{n+2,n+3\}\) split \(\{1,\dots,n+4\}\) into subsets of equal sum. By induction in steps of \(4\) from the two base cases, every \(n\ge 3\) with \(n\equiv 3\) or \(n\equiv 0\pmod 4\) has a split. This covers all positive integers allowed by the necessary condition.

   The parity argument alone would have left open whether, say, \(n=7\) works. The construction settles it: \(\{1,2,4,7\}\) and \(\{3,5,6\}\) , each with sum \(14\) .

6. Prove that every list of \(n\) integers \(a_1,\dots,a_n\) has a nonempty block of consecutive entries \(a_{i+1},\dots,a_j\) whose sum is divisible by \(n\) . Consider the \(n+1\) sums \(0,\ a_1,\ a_1+a_2,\ \dots,\ a_1+\dots+a_n\) and their remainders.

   Solution

   Let \(s_0=0\) and \(s_j=a_1+\dots+a_j\) for \(1\le j\le n\) . These are \(n+1\) integers, and there are only \(n\) possible remainders on division by \(n\) . By the pigeonhole principle two of them, say \(s_i\) and \(s_j\) with \(0\le i<j\le n\) , have the same remainder. Then \(n\) divides \(s_j-s_i=a_{i+1}+\dots+a_j\) , by Theorem 4.11(b). Since \(i<j\) this block is nonempty.

   The pigeons are the \(n+1\) partial sums and the boxes are the \(n\) remainders. Including the empty sum \(s_0=0\) is what provides the extra pigeon; with it, the case in which some \(s_j\) is itself divisible by \(n\) needs no separate treatment, since then \(s_j\) and \(s_0\) share the remainder \(0\) .

7. For each question describe what a certificate for the answer yes and a certificate for the answer no would look like, and say whether a theorem of this book guarantees that one of the two exists: (a) is \(91\) prime? (b) does \(12x\equiv 8\pmod{20}\) have a solution? (c) is a given graph bipartite? (d) are two given graphs isomorphic?

   Answer

   (a) No: the factorization \(91=7\cdot 13\) . A yes-certificate for primality of a number \(N\) is a check that no prime up to \(\sqrt N\) divides it; one always exists for a prime, by trial. (b) Yes: a solution, such as \(x=4\) , since \(48=2\cdot 20+8\) ; a no-certificate would be a common divisor of \(12\) and \(20\) not dividing \(8\) ; Theorem 4.16 guarantees one or the other. (c) A two-colouring or an odd cycle; Theorem 6.18 guarantees one or the other. (d) An isomorphism, or a distinguishing invariant; no theorem of this book guarantees that a simple invariant exists when the graphs are not isomorphic.

8. Find the least number \(m\) such that every graph with \(n\) vertices and at least \(m\) edges is connected. Prove both that \(m\) edges force connectedness and that \(m-1\) edges do not, by considering a graph with one isolated vertex.

   Hint

   \(m=\binom{n-1}{2}+1\) . The graph consisting of \(K_{n-1}\) and one isolated vertex has \(\binom{n-1}{2}\) edges and is disconnected. Conversely, a disconnected graph has a component with \(k\) vertices, \(1\le k\le n-1\) , and no edges between it and the rest, so it has at most \(\binom n2-k(n-k)\) edges; show that \(k(n-k)\ge n-1\) .

9. Let \(n\) be a positive integer divisible by neither \(2\) nor \(5\) . Prove that some number written with ones only, such as \(111\) or \(111111\) , is a multiple of \(n\) . Apply the pigeonhole principle to the remainders of the first \(n+1\) such numbers, and then use a result about coprime divisors.

   Solution

   For \(k\ge 1\) let \(R_k\) be the number written with \(k\) ones, so \(R_k=\frac{10^{k}-1}{9}\) . Consider \(R_1,R_2,\dots,R_{n+1}\) . These are \(n+1\) integers and there are \(n\) possible remainders on division by \(n\) , so by the pigeonhole principle two of them, \(R_i\) and \(R_j\) with \(i<j\) , have the same remainder. Then \(n\) divides

   \[ R_j-R_i=\underbrace{1\cdots 1}_{j-i}\underbrace{0\cdots 0}_{i}=R_{j-i}\cdot 10^{i}. \]

   Since \(n\) is divisible by neither \(2\) nor \(5\) , it shares no prime factor with \(10^{i}\) , so \(\gcd(n,10^{i})=1\) . By Theorem 4.7(a), \(n\) divides \(R_{j-i}\) , a number written with ones only.

   The proof is nonconstructive in form, but it bounds the search: some \(R_k\) with \(k\le n\) works. For \(n=7\) the first is \(111111=7\cdot 15873\) , and for \(n=3\) it is \(111=3\cdot 37\) .

10. A sequence is defined by \(a_1=1\) and \(a_n=a_{\lfloor n/2\rfloor}+1\) for \(n\ge 2\) . Compute \(a_n\) for \(n\le 16\) , conjecture a description of \(a_n\) in terms of the binary representation of \(n\) , and prove it by strong induction.

    Hint

    The values for \(n=1,\dots,16\) are \(1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5\) . The conjecture is that \(a_n\) is the number of binary digits of \(n\) . In the inductive step, note that \(\lfloor n/2\rfloor\) is obtained from \(n\) by deleting its last binary digit, and that \(1\le\lfloor n/2\rfloor<n\) for \(n\ge 2\) .

11. Let \(G\) be a connected graph with at least two vertices and define \(u\sim v\) to mean that there is a walk of even length from \(u\) to \(v\) . Prove that \(\sim\) is an equivalence relation, that it has at most two classes, and that it has exactly two classes if and only if \(G\) is bipartite.

    Solution

    Equivalence relation. Reflexive: the walk of length \(0\) at \(u\) has even length. Symmetric: a walk reversed has the same length. Transitive: an even walk from \(u\) to \(v\) followed by an even walk from \(v\) to \(w\) is a walk from \(u\) to \(w\) whose length is a sum of two even numbers.

    At most two classes. Fix a vertex \(r\) . Since \(G\) is connected, every vertex \(v\) is joined to \(r\) by some walk. If that walk has even length, \(v\sim r\) . If it has odd length, pick a neighbour \(s\) of \(r\) , which exists because \(G\) is connected and has at least two vertices; the walk from \(v\) to \(r\) followed by the edge \(rs\) has even length, so \(v\sim s\) . Hence every vertex lies in the class of \(r\) or the class of \(s\) .

    Two classes exactly when bipartite. Being connected with at least two vertices, \(G\) has an edge. Suppose first that \(G\) is bipartite with parts \(X\) and \(Y\) . Every edge crosses between the parts, so a walk of even length ends in the part where it started. Vertices in different parts are therefore not related, both parts are nonempty because there is an edge, and so there are at least two classes; by the previous paragraph there are exactly two.

    For the converse we prove the contrapositive: if \(G\) is not bipartite, there is only one class. By Theorem 6.18, \(G\) has a cycle of odd length \(\ell\) ; let \(w\) be a vertex on it. Let \(u\) and \(v\) be any vertices, and take a walk from \(u\) to \(w\) , of length \(p\) , and a walk from \(w\) to \(v\) , of length \(q\) . If \(p+q\) is even, their concatenation is an even walk from \(u\) to \(v\) . If \(p+q\) is odd, insert one trip round the cycle at \(w\) : the resulting walk has length \(p+\ell+q\) , which is even. Either way \(u\sim v\) , so all vertices lie in one class. The hypothesis of at least two vertices is needed for the first direction: a graph with a single vertex is connected and bipartite and has only one class.

12. To count the \(5\) -element subsets of \(\{1,\dots,10\}\) containing no two consecutive integers, a student reasons: “Choose the first element in \(10\) ways; this rules out it and a neighbour, leaving \(8\) ; then \(6\) , then \(4\) , then \(2\) . Divide by \(5!\) for the order: \(\frac{10\cdot 8\cdot 6\cdot 4\cdot 2}{5!}=32\) .” Find two errors, and count the subsets correctly by a method from Example 8.2.

    Solution

    First error: a miscount. “This rules out it and a neighbour” is false. A chosen number excludes itself and each of its neighbours, and a number from \(2\) to \(9\) has two neighbours. Choosing \(5\) rules out \(4\) , \(5\) , and \(6\) , leaving \(7\) numbers, not \(8\) ; only the choices \(1\) and \(10\) leave \(8\) .

    Second error: the product rule does not apply. Correcting the factor does not help, because no single number is right. The product rule of Theorem 5.2 needs the number of options at each stage to be the same whatever was chosen before. Here it is \(8\) after an end number and \(7\) after an interior one, and at later stages it depends also on whether the excluded neighbourhoods overlap: after choosing \(1\) and \(3\) six numbers remain, and after choosing \(1\) and \(5\) only five. So the ordered selections cannot be counted by multiplying fixed factors.

    The division by \(5!\) is not an error in itself: each subset does arise from exactly \(5!\) orders of choosing, so the division rule would apply to a correct count of ordered selections. A sanity check exposes the answer \(32\) at once, since listing the subsets finds far fewer.

    Correct count. Encode a subset as a bit string of length \(10\) with ones in the chosen positions. The condition is that the string has exactly five ones and no two consecutive ones. By Example 8.2 the number of such strings is \(\binom{n-k+1}{k}\) with \(n=10\) and \(k=5\) , that is, \(\binom 65=6\) . The six subsets are \(\{1,3,5,7,9\}\) , \(\{1,3,5,7,10\}\) , \(\{1,3,5,8,10\}\) , \(\{1,3,6,8,10\}\) , \(\{1,4,6,8,10\}\) , and \(\{2,4,6,8,10\}\) .

13. A student notes that \(6x+10y\) is always even and concludes that every even number \(c\ge 0\) can be written as \(6x+10y\) with natural numbers \(x\) and \(y\) . List the even numbers for which this fails, and state what the parity observation does and does not prove.

    Answer

    The even numbers that cannot be written as \(6x+10y\) with \(x,y\in\mathbb N\) are \(2\) , \(4\) , \(8\) , and \(14\) ; every other even number \(c\ge 0\) can. The parity observation proves necessity only: an odd number is never of this form. By Theorem 4.5 every even number is \(6x+10y\) for some integers \(x\) , \(y\) , but they may be negative.

14. Count the proper colourings with three colours of the path \(P_n\) , and then of the cycle \(C_n\) for \(n\ge 3\) , by deriving a recurrence that relates the count for \(C_n\) to the counts for \(P_n\) and \(C_{n-1}\) . Solve the recurrence and check your formula for \(n=3\) and \(n=4\) .

    Solution

    Paths. Colour the vertices of \(P_n\) in order. The first has \(3\) options and each later vertex must differ from its predecessor, \(2\) options. So \(P_n\) has \(p_n=3\cdot 2^{n-1}\) proper colourings.

    Cycles. Let \(c_n\) be the number for \(C_n\) . A proper colouring of the path \(v_1,\dots,v_n\) is either one in which \(v_1\) and \(v_n\) have different colours, and these are exactly the proper colourings of \(C_n\) ; or one in which \(v_1\) and \(v_n\) have the same colour, and merging \(v_1\) with \(v_n\) turns these, bijectively, into the proper colourings of \(C_{n-1}\) for \(n\ge 4\) . Hence \(p_n=c_n+c_{n-1}\) , that is,

    \[ c_n=3\cdot 2^{n-1}-c_{n-1}\quad(n\ge 4),\qquad c_3=6 . \]

    Guess \(c_n=2^{n}+2(-1)^{n}\) and verify by Proposition 7.2. At \(n=3\) it gives \(8-2=6\) . And \(3\cdot 2^{n-1}-\bigl(2^{n-1}+2(-1)^{n-1}\bigr)=2^{n}+2(-1)^{n}\) . So the formula holds for all \(n\ge 3\) . Checks: \(c_3=6\) , the \(3!\) ways to colour a triangle, and \(c_4=16+2=18\) .

    For even \(n\) the count with two colours in place of three is positive, and for odd \(n\) it is zero, consistent with Theorem 6.18.

15. How many divisions does Euclid’s algorithm perform on the pair \((89,55)\) ? Use the claim of Example 8.6 to find the largest possible number of divisions when the larger number is below \(2\,000\,000\) , given that \(F_{31}=1346269\) and \(F_{32}=2178309\) .

    Answer

    \((89,55)=(F_{11},F_{10})\) takes \(9\) divisions. If \(n\) divisions occur then \(F_{n+2}\le a<2000000\) , and since \(F_{31}\le a\) is possible while \(F_{32}\) is too large, \(n+2\le 31\) : at most \(29\) divisions, attained by \((F_{31},F_{30})\) .

16. Prove that \(\binom n2=\Theta(n^{2})\) with explicit constants, and prove that \(\binom{n}{\lfloor n/2\rfloor}\ge\frac{2^{n}}{n+1}\) for \(n\ge 1\) by comparing the largest binomial coefficient with the average. Conclude that \(\binom{n}{\lfloor n/2\rfloor}\) is not \(O(n^{k})\) for any \(k\) .

    Solution

    Quadratic growth. \(\binom n2=\frac{n(n-1)}{2}=\frac{n^{2}}{2}-\frac n2\) . For all \(n\ge 1\) , \(\binom n2\le\frac12 n^{2}\) , so \(C=\frac12\) and \(n_0=1\) witness \(O(n^{2})\) . For \(n\ge 2\) we have \(\frac n2\le\frac{n^{2}}{4}\) , so \(\binom n2\ge\frac14 n^{2}\) , and \(c=\frac14\) , \(n_0=2\) witness \(\Omega(n^{2})\) .

    The middle coefficient. The \(n+1\) binomial coefficients \(\binom n0,\dots,\binom nn\) add up to \(2^{n}\) by Theorem 5.7(c), so their average is \(\frac{2^{n}}{n+1}\) , and the largest of them is at least the average. The largest is \(\binom{n}{\lfloor n/2\rfloor}\) , because \(\binom n{k+1}/\binom nk=\frac{n-k}{k+1}\) is at least \(1\) exactly when \(k\le\frac{n-1}{2}\) , so the coefficients increase up to the middle and decrease after it.

    Conclusion. If \(\binom{n}{\lfloor n/2\rfloor}\le Cn^{k}\) held for all large \(n\) , then \(2^{n}\le C(n+1)n^{k}\le 2Cn^{k+1}\) would hold for all large \(n\) , making \(2^{n}=O(n^{k+1})\) and contradicting Theorem 7.10(b).

17. At a party of \(n\) couples, nobody shakes hands with their own partner, and no pair shakes hands twice. The host asks the other \(2n-1\) people how many hands they shook and receives \(2n-1\) different answers. Determine how many hands the host’s partner shook, starting with the two people who answered \(0\) and \(2n-2\) and reducing to a smaller party.

    Hint

    Nobody shakes more than \(2n-2\) hands, so the answers are \(0,1,\dots,2n-2\) . The person who answered \(2n-2\) shook hands with everyone except their own partner, so everyone else shook at least one hand, and the partner must be the person who answered \(0\) . Remove that couple; every remaining answer drops by \(1\) , and the party has \(n-1\) couples with the same property. The host’s partner shook \(n-1\) hands.

18. For which \(n\ge 1\) does there exist a graph with \(n\) vertices in which every vertex has degree \(3\) ? Prove necessity and sufficiency separately, giving an explicit construction.

    Solution

    The answer is: exactly when \(n\) is even and \(n\ge 4\) .

    Necessity. By the handshake lemma the degree sum \(3n\) is even, so \(n\) is even. A vertex of degree \(3\) needs three other vertices, so \(n\ge 4\) .

    Sufficiency. Let \(n=2m\) with \(m\ge 2\) , and take vertices \(0,1,\dots,n-1\) . Join \(i\) to \(i+1\) modulo \(n\) , forming a cycle, and join \(i\) to \(i+m\) modulo \(n\) , the opposite vertex. Each vertex \(i\) has the neighbours \(i-1\) , \(i+1\) , and \(i+m\) modulo \(n\) . These are three different vertices, different from \(i\) : \(i+m\) differs from \(i\pm 1\) because \(m\ne 1\) and \(m\ne n-1\) when \(n\ge 4\) . The opposite of \(i+m\) is \(i\) , so the diagonal edges are well defined as \(m\) edges. Hence every vertex has degree exactly \(3\) .

    For \(n=4\) this graph is \(K_4\) , and for \(n=6\) it is the graph \(G_3\) of Example 6.2.

19. For each question say which course in this library would treat it as its own subject, and what the present course contributes to it: (a) find the cheapest set of roads connecting ten towns; (b) find the chance that a random arrangement of four hats returns nobody’s own hat; (c) describe all the different multiplication tables a set of six elements can have if every element is to have an inverse; (d) decide whether the ratios \(F_{n+1}/F_n\) approach a limit.

    Answer

    (a) Discrete Optimization, as a minimum-cost spanning tree; this course contributes the definition and characterizations of spanning trees. (b) Probability Theory; this course contributes the count, \(9\) derangements among \(24\) arrangements. (c) Abstract Algebra, as the classification of groups of order six; this course contributes modular arithmetic and permutations as examples. (d) Real Analysis, for the notion of a limit; this course contributes the closed form of Example 7.4.

20. Write a one-page explanation, for a reader who has finished Chapter 3 only, of why an invariant can prove that a position is unreachable but cannot prove that it is reachable. Use Example 8.5 and Exercise 5 as your two illustrations, one of each outcome.

    Hint

    Organize the page around the two quantifiers. Unreachability is a universal statement about all sequences of moves, and an invariant proves it for all of them at once. Reachability is an existential statement and needs a witness, a particular sequence of moves or a construction. In Example 8.5 the invariant differs between start and target; in Exercise 5 the invariant agrees for \(n=7\) , and only the exhibited split shows that the target can be reached.