0$. Use mathematical induction to prove that $$ \sqrt{a+\sqrt{a+\sqrt{a+\cdots + \sqrt{a}}}} < \dfrac{1+\sqrt{4a+1}}{2}, $$ where the left member contains an arbitrary number of radicals. \begin{answerXproofs} Let $$P(n): \ \ \ \underbrace{\sqrt{a+\sqrt{a+\sqrt{a+\cdots + \sqrt{a}}}}}_{n \ \mathrm{radicands}} < \dfrac{1+\sqrt{4a+1}}{2}. $$Let us prove $P(1)$, that is $$\forall a > 0, \ \ \ \sqrt{a} < \dfrac{1+\sqrt{4a+1}}{2}.$$ To get this one, let's work backwards. If $a>\dfrac{1}{4}$ $$ \begin{array}{lll}\sqrt{a} < \dfrac{1+\sqrt{4a+1}}{2} & \iff & 2\sqrt{a} < 1 + \sqrt{4a + 1} \\ & \iff & 2\sqrt{a} -1 < \sqrt{4a + 1} \\ & \iff & (2\sqrt{a} -1)^2 < (\sqrt{4a + 1})^2 \\ & \iff & 4a - 4\sqrt{a} + 1 < 4a + 1 \\ & \iff & -2\sqrt{a} < 0. \end{array}$$ all the steps are reversible and the last inequality is always true. If $a\leq \dfrac{1}{4}$ then trivially $2\sqrt{a} -1 < \sqrt{4a + 1}$. Thus $P(1)$ is true. Assume now that $P(n)$ is true and let's derive $P(n + 1)$. From $$\underbrace{\sqrt{a+\sqrt{a+\sqrt{a+\cdots + \sqrt{a}}}}}_{n \ \mathrm{radicands}} < \dfrac{1+\sqrt{4a+1}}{2} \implies \underbrace{\sqrt{a+\sqrt{a+\sqrt{a+\cdots + \sqrt{a}}}}}_{n+1 \ \mathrm{radicands}} < \sqrt{a+ \dfrac{1+\sqrt{4a+1}}{2}}. $$ we see that it is enough to shew that $$\sqrt{a+ \dfrac{1+\sqrt{4a+1}}{2}} = \dfrac{1+\sqrt{4a+1}}{2}. $$ But observe that $$\begin{array}{lll} (\sqrt{4a + 1} + 1)^2 = 4a + 2\sqrt{4a + 1} + 2 & \implies & \dfrac{1+\sqrt{4a+1}}{2}=\sqrt{a+ \dfrac{1+\sqrt{4a+1}}{2}}, \end{array}$$proving the claim. \end{answerXproofs} \end{pro} \begin{pro} Use the AM-GM Inequality: $\forall x \geq 0, \forall y \geq 0, \ \ \sqrt{xy} \leq \dfrac{x + y}{2}$ in order to prove that for all quadruplets of non-negative real numbers $a, b, c, d$ we have $$ \sqrt[4]{abcd} \leq \dfrac{a + b + c + d}{4}. $$ Then, by choosing a special value for $d$ above, deduce that $$ \sqrt[3]{uvw} \leq \dfrac{u + v + w}{3}$$ for all non-negative real numbers $u, v, w$. \begin{answerXproofs}We have $$ \sqrt[4]{abcd} = \sqrt{\sqrt{ab}\cdot \sqrt{cd}} \leq \dfrac{\sqrt{ab} + \sqrt{cd}}{2} \leq \dfrac{\dfrac{a+b}{2} + \dfrac{c + d}{2}}{2} = \dfrac{a+b+c+d}{4}.$$ Now let $a = u, b = v, c = w$ and $d = \dfrac{u + v + w}{3}$. Then $$\begin{array}{lll} \sqrt[4]{uvw\left(\dfrac{u + v + w}{3}\right)} \leq \dfrac{u + v + w + \dfrac{u + v + w}{3}}{4} & \implies & (uvw)^{1/4}\left(\dfrac{u + v + w}{3}\right)^{1/4} \leq \dfrac{u + v + w}{3} \\ & \implies & (uvw)^{1/4} \leq \left(\dfrac{u + v + w}{3}\right)^{1-1/4} \\ & \implies & (uvw)^{1/4} \leq \left(\dfrac{u + v + w}{3}\right)^{3/4} \\ & \implies & (uvw)^{1/3} \leq \dfrac{u + v + w}{3}, \\ \end{array} $$whence the required result follows. \end{answerXproofs} \end{pro} \begin{pro} Let $a, b, c$ be real numbers. Prove that if $a, b, c$ are real numbers then $$ a^2 + b^2 + c^2 -ab -bc - ca \geq 0. $$ By direct multiplication, or otherwise, prove that $$ a^3 + b^3 + c^3 -3abc = (a+b+c)(a^2 + b^2 + c^2 -ab -bc - ca).$$ Use the above two results to prove once again that $$ \sqrt[3]{uvw} \leq \dfrac{u + v + w}{3}$$ for all non-negative real numbers $u, v, w$. \begin{answerXproofs} Since squares of real numbers are non-negative, we have $$\begin{array}{lll}(a-b)^2 +(b-c)^2+(c-a)^2 \geq 0 & \iff & 2a^2 + 2b^2 + 2c^2 -2ab-2bc -2ca \geq 0 \\ & \iff & a^2 + b^2 + c^2 -ab -bc - ca \geq 0.\end{array}$$ \bigskip Now, use the identity $$x^3 + y^3 = (x + y)^3 - 3xy(x + y)$$twice. Then $$ \begin{array}{lll} a^3 + b^3 + c^3 - 3abc & = & (a + b)^3 + c^3 - 3ab(a + b) - 3abc \\ & = & (a + b + c)^3 - 3(a + b)c(a + b + c) - 3ab(a + b + c) \\ & = & (a + b + c)((a + b + c)^2 - 3ac - 3bc - 3ab) \\ & = & (a + b + c)(a^2 + b^2 + c^2 - ab - bc - ca) \end{array} $$ If $a, b, c$ are non-negative then $a + b + c \geq 0$ and also $a^2 + b^2 + c^2 - ab - bc - ca \geq 0$. This gives $$\frac{a^3 + b^3 + c^3}{3} \geq abc.$$ The desired inequality follows upon putting $u = a^3, v = b^3, w = c^3$. \end{answerXproofs} \end{pro} \begin{pro} Use the fact that any odd number is of the form $8k\pm 1$ or $8k \pm 3$ in order to give a direct proof that the square of any odd number leaves remainder $1$ upon division by $8$. Use this to prove that $2001$ is not the sum of three odd squares. \begin{answerXproofs} We have $$ (8k\pm 1)^2 = 64k^2 \pm 16k + 1 = 8(8k^2 \pm 2) + 1, $$ $$ (8k\pm 3)^2 = 64k^2 \pm 48k + 9 = 8(8k^2 \pm 6 + 1) + 1, $$proving that in all cases the remainder is $1$ upon division by $8$. \bigskip Now, a sum of three odd squares must leave remainder $3$ upon division by $8$. Thus if $2001$ were a sum of three squares, it would leave remainder $3 = 1 + 1 + 1$ upon division by $8$. But $2001$ leaves remainder $1$ upon division by $8$, a contradiction to the assumption that it is a sum of three squares. \end{answerXproofs} \end{pro} \begin{pro} Find, and prove by induction, the sum of the first $n$ positive odd numbers. \begin{answerXproofs} We are required to find $$1 + 3 + \cdots + (2n-1). $$Observe that $1 = 1^2$; $1+3 = 2^2$; $1+3+5=3^2$; $1+3+5+7=4^2$. We suspect that $$1 + 3 + \cdots + (2n-1) = n^2, $$which we will prove by induction. We have already established this for $n=1$. Let $P_{n-1}$ be the proposition $$1 + 3 + \cdots + (2n-3) = (n-1)^2, $$which we assume true. Now $$\begin{array}{lll}1 + 3 + \cdots + (2n-1) & = & 1 + 3 + \cdots + (2n-3) + (2n-1) \\ & = & (n-1)^2 + 2n-1 \\ & = & n^2 -2n + 1 + 2n-1 \\ & = & n^2, \end{array} $$ establishing the truth of $P_n$. \end{answerXproofs} \end{pro} \begin{pro} Prove by induction that if $n$ non-parallel straight lines on the plane intersect at a common point, they divide the plane into $2n$ regions. \begin{answerXproofs} The assertion is clear for $n=1$ since a straight line divides the plane into two regions. Assume $P_{n-1}$, that is, that $n-1$ non-parallel straight lines intersecting at a common point divide the plane into $2(n-1) = 2n-2$ regions. A new line non-parallel to them but passing through a common point will lie between two of the old lines, and divide the region between them into two more regions, producing then $2n-2 + 2 = 2n$ regions, demonstrating the assertion. \end{answerXproofs} \end{pro} \begin{pro} Demonstrate by induction that no matter how $n$ straight lines divide the plane, it is always possible to colour the regions produced in two colours so that any two adjacent regions have different colours. \begin{answerXproofs} For $n = 1$ straight lines this is clear. Assume $P_{n-1}$, the proposition that this is possible for $n-1>1$ lines is true. So consider the plane split by $n-1$ lines into regions and coloured as required. Consider now a new line added to the $n-1$ lines. This line splits the plane into two regions, say I and II. We now do the following: in region I we leave the original coloration. In region II we switch the colours. We now have a coloring of the plane in the desired manner. For, either the two regions lie completely in region I or completely in region II, and they are coloured in the desired manner by the induction hypothesis. If one lies in region I and the other in region II, then they are coloured in the prescribed manner because we switched the colours in the second region. \end{answerXproofs} \end{pro} \begin{pro} Demonstrate by induction that whenever the formula makes sense one has $$(\cos \theta)(\cos 2\theta)\cdots (\cos 2^n\theta) = \dfrac{\sin 2^{n+1}\theta }{2^{n+1}\sin \theta}. $$ \begin{answerXproofs} For $n=0$ this is the identity $\sin 2\theta = 2\sin\theta \cos \theta$. Assume the statement is true for $n-1$, that is, assume that $$(\cos \theta)(\cos 2\theta)\cdots (\cos 2^{n-1}\theta) = \dfrac{\sin 2^{n}\theta }{2^{n}\sin \theta} .$$ Then $$\begin{array}{lll} (\cos \theta)(\cos 2\theta)\cdots (\cos 2^{n}\theta) & = &(\cos \theta)(\cos 2\theta)\cdots (\cos 2^{n-1}\theta)(\cos 2^{n}\theta) \\ & = & \dfrac{\sin 2^{n}\theta }{2^{n}\sin \theta}(\cos 2^{n}\theta)\\ & = &\dfrac{\sin 2^{n+1}\theta }{2^{n+1}\sin \theta},\\ \end{array} $$as wanted. \end{answerXproofs} \end{pro} \begin{pro} Demonstrate by induction that whenever the formula makes sense one has $$\sin x + \sin 2x + \cdots + \sin nx = \dfrac{\sin \frac{n+1}{2}x}{\sin \frac{x}{2}}\cdot\sin \frac{nx}{2}. $$ \begin{answerXproofs} The formula clearly holds for $n=1$. Assume that $$\sin x + \sin 2x + \cdots + \sin (n-1)x = \dfrac{\sin \frac{n}{2}x}{\sin \frac{x}{2}}\cdot\sin \frac{(n-1)x}{2}. $$ Then $$\begin{array}{lll} \sin x + \sin 2x + \cdots + \sin nx & = & \sin x + \sin 2x + \cdots + \sin (n-1)x+ \sin nx \\ & = &\dfrac{\sin \frac{n}{2}x}{\sin \frac{x}{2}}\cdot\sin \frac{(n-1)x}{2} + \sin nx \\ & = &\dfrac{\sin \frac{n}{2}x}{\sin \frac{x}{2}}\cdot\sin \frac{(n-1)x}{2} + 2\sin \frac{nx}{2}\cos\frac{nx}{2} \\ & = &\left(\dfrac{\sin \frac{(n-1)x}{2} + 2\cos\frac{nx}{2}\sin \frac{x}{2}}{\sin \frac{x}{2}} \right)(\sin \frac{nx}{2}) \\ & = &\left(\dfrac{\sin \frac{nx}{2} \cos \frac{x}{2} - \sin \frac{x}{2}\cos \frac{nx}{2} + 2\cos\frac{nx}{2}\sin \frac{x}{2}}{\sin \frac{x}{2}} \right)(\sin \frac{nx}{2}) \\ & = &\left(\dfrac{\sin \frac{nx}{2} \cos \frac{x}{2} + \sin \frac{x}{2}\cos \frac{nx}{2} }{\sin \frac{x}{2}} \right)(\sin \frac{nx}{2}) \\ & = & \dfrac{\sin \frac{n+1}{2}x}{\sin \frac{x}{2}}\cdot\sin \frac{nx}{2}, \end{array}$$where we have used the sum identity $$\sin (a\pm b) = \sin a\cos b \pm \sin b \cos a.$$ \end{answerXproofs} \end{pro} \begin{pro} Prove by induction that $2^n > n$ for integer $n\geq 0$. \begin{answerXproofs} For $n =0$ we have $2^0 = 1 > 0$, and for $n =1$ we have $2^1 = 2 > 1$ so the assertion is true when $n= 0$ and $n=1$. Assume the assertion is true for $n-1 >0$, that is, assume that $2^{n-1}>n-1$. Examine $$2^n = 2(2^{n-1}) = 2^{n-1} + 2^{n-1} > n-1 + n-1 \geq n-1 + 1 = n, $$using the induction hypothesis and the fact that $n-1 \geq 1$. \end{answerXproofs} \end{pro} \begin{pro} Prove, by induction on $n$, that $$1\cdot 2 + 2\cdot 2^2 + 3\cdot 2^3 + \cdots + n\cdot 2^n = 2 + (n - 1)2^{n + 1}. $$ \begin{answerXproofs}For $n = 1$ we have $1\cdot 2 = 2 + (1-1)2^2$, and so the statement is true for $n = 1$. Assume the statement is true for $n$, that is, assume $$P(n): 1\cdot 2 + 2\cdot 2^2 + 3\cdot 2^3 + \cdots + n\cdot 2^n = 2 + (n - 1)2^{n + 1}. $$ We would like to prove that we indeed have $$P(n+1): 1\cdot 2 + 2\cdot 2^2 + 3\cdot 2^3 + \cdots + (n+1)\cdot 2^{n+1} = 2 + n2^{n + 2}. $$ But adding $(n+1)2^{n+1}$ to both sides of $P(n)$ we obtain $$1\cdot 2 + 2\cdot 2^2 + 3\cdot 2^3 + \cdots + n\cdot 2^n + (n+1)2^{n+1} = 2 + (n - 1)2^{n + 1} + (n+1)2^{n+1} = 2 + 2n2^{n+1} = 2 + n2^{n+2}, $$ proving $P(n+1)$. \end{answerXproofs} \end{pro} \begin{pro} An urn contains $28$ blue marbles, $20$ red marbles, $12$ white marbles, $10$ yellow marbles, and $8$ magenta marbles. How many marbles must be drawn from the urn in order to assure that there will be $15$ marbles of the same color? \begin{answerXproofs} If all the magenta, all the yellow, all the white, $14$ of the red and $14$ of the blue marbles are drawn, then in among these $8 + 10 + 12 + 14 + 14 = 58$ there are no $15$ marbles of the same color. Thus we need $59$ marbles in order to insure that there will be $15$ marbles of the same color. \end{answerXproofs} \end{pro} \begin{pro} The nine entries of a $3\times 3$ grid are filled with $-1$, $0$, or $1$. Prove that among the eight resulting sums (three columns, three rows, or two diagonals) there will always be two that add to the same number. \begin{answerXproofs} There are seven possible sums, each one a number in $\{-3,-2,-1,0,1,2,3\}$. By the Pigeonhole Principle, two of the eight sums must add up to the same. \end{answerXproofs} \end{pro} \begin{pro} Forty nine women and fifty one men sit around a round table. Demonstrate that there is at least a pair of men who are facing each other. \begin{answerXproofs} Pick a pair of different sex facing one another, that is, forming a ``diameter'' on the table. On either side of the diameter there must be an equal number of people, that is, forty nine. If all the men were on one side of the diameter then we would have a total of $49+1 = 50$, a contradiction. \end{answerXproofs} \end{pro} \begin{pro} An eccentric widow has five cats\footnote{Why is it always eccentric widows who have multiple cats?}. These cats have $16$ kittens among themselves. What is the largest integer $n$ for which one can say that at least one of the five cats has $n$ kittens? \begin{answerXproofs} We have $ \ceil{\frac{16}{5}} = 4$, so there is at least one cat who has four kittens. \end{answerXproofs} \end{pro} \begin{pro} No matter which fifty five integers may be selected from $$\{ 1, 2, \ldots , 100\},$$ prove that one must select some two that differ by $10$. \begin{answerXproofs} First observe that if we choose $n + 1$ integers from any string of $2n$ consecutive integers, there will always be some two that differ by $n$. This is because we can pair the $2n$ consecutive integers $$ \{ a + 1, a + 2, a + 3, \ldots , a + 2n\}$$ into the $n$ pairs $$ \{ a + 1, a + n + 1\}, \{ a + 2, a + n + 2\}, \ldots , \{ a + n, a + 2n\},$$and if $n + 1$ integers are chosen from this, there must be two that belong to the same group. \bigskip So now group the one hundred integers as follows: $$ \{ 1, 2, \ldots 20 \} , \{ 21, 22, \ldots , 40\} ,$$ $$ \{ 41, 42, \ldots , 60\}, \ \{ 61, 62, \ldots , 80\} $$ and $$ \{ 81, 82, \ldots , 100\} .$$ If we select fifty five integers, we must perforce choose eleven from some group. From that group, by the above observation (let $n = 10$), there must be two that differ by $10$. \end{answerXproofs} \end{pro} \begin{pro}[AHSME 1994] Label one disc ``${\bf 1}$'', two discs ``${\bf 2}$'', three discs ``${\bf 3}$'', \ldots , fifty discs $``{\bf 50}$''. Put these $1 + 2 + 3 + \cdots + 50 = 1275$ labeled discs in a box. Discs are then drawn from the box at random without replacement. What is the minimum number of discs that must me drawn in order to guarantee drawing at least ten discs with the same label? \begin{answerXproofs} If we draw all the $1 + 2 + \cdots + 9 = 45$ labelled ``${\bf 1}$'', \ldots , ``${\bf 9}$'' and any nine from each of the discs ``${\bf 10}$'', \ldots , ``${\bf 50}$'', we have drawn $45 + 9\cdot 41 = 414$ discs. The $415$-th disc drawn will assure at least ten discs from a label. \end{answerXproofs} \end{pro} \begin{pro} Given any set of ten natural numbers between $1$ and $99$ inclusive, prove that there are two disjoint nonempty subsets of the set with equal sums of their elements. \begin{answerXproofs} There are $2^{10} - 1 = 1023$ non-empty subsets that one can form with a given 10-element set. To each of these subsets we associate the sum of its elements. The maximum value that any such sum can achieve is $90 + 91 + \cdots + 99 = 945 < 1023.$ Therefore, there must be at least two different subsets that have the same sum. \end{answerXproofs} \end{pro} \Closesolutionfile{discans} \section*{Answers}\addcontentsline{toc}{section}{Answers}\markright{Answers} {\small\input{discansC2}} \chapter{Logic, Sets, and Boolean Algebra} \Opensolutionfile{discans}[discansC3] \section{Logic} \begin{df} A {\em boolean proposition} is a statement which can be characterised as either $\TRUE$ or $\FALSE$. \end{df} Whether the statement is {\em obviously} true or false does not enter in the definition. One only needs to know that its certainty can be established. \begin{exa} The following are boolean propositions and their values, if known: \begin{dingautolist}{202} \item $7^2 = 49$. ($\TRUE$) \item $5>6$. ($\FALSE$) \item If $p$ is a prime then $p$ is odd. ($\FALSE$) \item There exists infinitely many primes which are the sum of a square and $1$. (unknown) \item There is a G-d. (unknown) \item There is a dog. ($\TRUE$) \item I am the Pope. ($\FALSE$) \item Every prime that leaves remainder $1$ when divided by $4$ is the sum of two squares. ($\TRUE$) \item Every even integer greater than $6$ is the sum of two distinct primes. (unknown) \end{dingautolist} \end{exa} \begin{exa} The following are not boolean propositions, since it is impossible to assign a $\TRUE$ or $\FALSE$ value to them. \begin{dingautolist}{202} \item Whenever I shampoo my camel. \item Sit on a potato pan, Otis! \item $y\GETS x$. \item This sentence is false. \end{dingautolist} \end{exa} \begin{df} A {\em boolean operator} is a character used on boolean propositions. Its output is either $\TRUE$ or $\FALSE$ \end{df} We will consider the following boolean operators in these notes. They are listed in order of operator precedence and their evaluation rules are given in Table \ref{tab:evaluation_rules}. \begin{dingautolist}{202} \item $\neg$ ({\bf not} or negation), \item $\wedge$ ({\bf and} or conjunction) \item $\vee$ ({\bf or} or disjunction) \item $\implies$ ({\bf implies}) \item $=$ ({\bf equals}) \end{dingautolist} $\neg$ has right-to-left associativity, all other operators listed have left-to-right associativity. \begin{table}[h] \begin{center} \begin{tabular}{|cc|ccccc|} \hline $a$ & $b$ & $(\neg a)$ & $(a \wedge b)$ & $(a \vee b)$ & $(a \implies b)$ & $(a = b)$ \\ \hline $F$ & $F$& $T$ & $F$ &$F$&$T$&$T$ \\ $F$ & $T$& $T$ & $F$ &$T$&$T$&$F$ \\ $T$ & $F$& $F$ & $F$ &$T$&$F$&$F$ \\ $T$ & $T$& $F$ & $T$ &$T$&$T$&$T$ \\ \hline \end{tabular} \footnotesize\hangcaption{Evaluation Rules}\label{tab:evaluation_rules} \end{center} \end{table} \begin{rem} The $\vee = \OR$ is inclusive, meaning that if $a\vee b$ then either $a$ is true, or $b$ is true, or both $a$ and $b$ are true. \end{rem} \begin{exa} Consider the propositions: \begin{itemize} \item $a:$ I will eat my socks. \item $b:$ It is snowing. \item $c:$ I will go jogging. \end{itemize} The sentences below are represented by means of logical operators. \begin{dingautolist}{202} \item $(b \vee \neg b) \implies c$: Whether or not it is snowing, I will go jogging. \item $b \implies \neg c$: If it is snowing, I will not go jogging. \item $b \implies (a \wedge \neg c)$: If it is snowing, I will eat my socks, but I will not go jogging. \end{dingautolist} \end{exa} \begin{exa} $\neg a \implies a \vee b$ is equivalent to $(\neg a) \implies (a\vee b)$ upon using the precedence rules.\end{exa} \begin{exa} $a\implies b \implies c$ is equivalent to $(a\implies b)\implies c$ upon using the associativity rules. \end{exa} \begin{exa} $a \wedge \neg b \implies c$ is equivalent to $(a \wedge \neg b) \implies c$ by the precedence rules. \end{exa} \begin{exa}Write a code fragment that accepts three numbers, decides whether they form the sides of a triangle. \end{exa} Solution: First we must have $a > 0, b>0, c>0$. Sides of length $a, b, c$ form a triangle if and only they satisfy the triangle inequalities:: $$ a+b>c, $$ $$ b + c>a, $$ $$ c+a>b. $$ \bcp[Ovalbox]{IsItATriangle}{(a,b,c)} \IF ((a > 0) \AND (b>0) \AND (c>0) \\ \AND ((a+b > c )\AND (b+c > a) \AND (c+a>b)) \THEN \mathrm{istriangle} \GETS \TRUE \ELSE \mathrm{istriangle} \GETS \FALSE \\ \RETURN{\mathrm{istriangle} } \ecp \begin{df} A {\em truth table} is a table assigning all possible combinations of $T$ or $F$ to the variables in a proposition. If there are $n$ variables, the truth table will have $2^n$ lines. \end{df} \begin{exa} \label{exa:truth_table_example} Construct the truth table of the proposition $a \vee \neg b \wedge c$. \end{exa} Solution: Since there are three variables, the truth table will have $2^3 = 8$ lines. Notice that by the precedence rules the given proposition is equivalent to $a \vee (\neg b \wedge c)$, since $\wedge$ has higher precedence than $\vee$. The truth table is in Table \ref{tab:truth_table_example}. \begin{table}[h] \begin{center} \begin{tabular}{|ccc|cc|c|} \hline $a$ & $b$ & $c$ & $(\neg b)$ & $(\neg b \wedge c)$ & $a \vee (\neg b \wedge c)$ \\ \hline $F$ & $F$ & $F$ & $T $ & $F $ & $F $ \\ $F$ & $F$ & $T$ & $T $ & $T $ & $T $ \\ $F$ & $T$ & $F$ & $F $ & $F $ & $F $ \\ $F$ & $T$ & $T$ & $F $ & $F $ & $F $ \\ $T$ & $F$ & $F$ & $ T$ & $F $ & $T $ \\ $T$ & $F$ & $T$ & $T $ & $T $ & $T $ \\ $T$ & $T$ & $F$ & $F $ & $F $ & $T $ \\ $T$ & $T$ & $T$ & $F$ & $F $ & $T $ \\ \hline \end{tabular} \footnotesize\hangcaption{Example \ref{exa:truth_table_example}.}\label{tab:truth_table_example} \end{center} \end{table} \begin{df} Two propositions are said to be {\em equivalent} if they have the same truth table. If proposition $P$ is equivalent to proposition $Q$ we write $P = Q$. \end{df} \begin{thm}[Double Negation]\label{thm:double_negation} $\neg (\neg a) = a$. \end{thm} \begin{pf} From the truth table \ref{tab:double negation} the entries for $a$ and $\neg (\neg a)$ produce the same output, proving the assertion. \begin{table}[h] \begin{center} \begin{tabular}{|c|cc|} \hline $a$ & $(\neg a) $ & $(\neg (\neg a))$ \\ \hline $F$ & $T$ & $F$ \\ $T$ & $F $ & $T $ \\ \hline \end{tabular} \footnotesize\hangcaption{Theorem \ref{thm:double_negation}.}\label{tab:double negation} \end{center} \end{table} \end{pf} \begin{thm}[De Morgan's Rules]\label{thm:demorgan} $\neg (a\vee b) = \neg a \wedge \neg b$ and $\neg (a\wedge b) = \neg a \vee \neg b$. \end{thm} \begin{pf}Truth table \ref{tab:demorgan1} proves that $\neg (a\vee b) = \neg a \wedge \neg b$ and truth table \ref{tab:demorgan2} proves that $\neg (a\wedge b) = \neg a \vee \neg b$. \begin{table}[h] \begin{minipage}{7cm} \begin{tabular}{|cc|ccccc|} \hline $a$ & $b$ & $(a\vee b)$ & $\neg (a\vee b)$ & $(\neg a)$ & $(\neg b)$ & $(\neg a \wedge \neg b)$ \\ \hline $F$ & $F$ & $F$ & $T $ & $T $ & $T $ & $T$ \\ $F$ & $T$ & $T$ & $F $ & $T $ & $F $ & $F$ \\ $T$ & $F$ & $T$ & $F $ & $F $ & $T $ & $F$ \\ $T$ & $T$ & $T$ & $F $ & $F $ & $F $ & $F$ \\ \hline \end{tabular} \footnotesize\hangcaption{$\neg (a\vee b) = \neg a \wedge \neg b$ .}\label{tab:demorgan1} \end{minipage} \hfill \begin{minipage}{7cm} \begin{tabular}{|cc|ccccc|} \hline $a$ & $b$ & $(a\wedge b)$ & $\neg (a\wedge b)$ & $(\neg a)$ & $(\neg b)$ & $(\neg a \vee \neg b)$ \\ \hline $F$ & $F$ & $F$ & $T $ & $T $ & $T $ & $T$ \\ $F$ & $T$ & $F$ & $T $ & $T $ & $F $ & $T$ \\ $T$ & $F$ & $F$ & $T $ & $F $ & $T $ & $T$ \\ $T$ & $T$ & $T$ & $F $ & $F $ & $F $ & $F$ \\ \hline \end{tabular} \footnotesize\hangcaption{$\neg (a\wedge b) = \neg a \vee \neg b$.}\label{tab:demorgan2} \end{minipage} \end{table} \end{pf} \begin{exa} Negate $A \vee \neg B$.\end{exa} Solution: Using the De Morgan Rules and double negation: $\neg (A \vee \neg B) = \neg A \wedge \neg (\neg B) = \neg A \wedge B.$ \begin{exa} Let $p$ and $q$ be propositions. Translate into symbols: either $p$ or $q$ is true, but not both simultaneously. \end{exa} Solution: By the conditions of the problem, if $p$ is true then $q$ must be false, which we represent as $p \wedge \neg q$. Similarly if $q$ is true, $p$ must be false and we must have $\neg p \wedge q$. The required expression is thus $$ (p \wedge \neg q) \vee (\neg p \wedge q). $$ \begin{df} A {\em predicate} is a sentence containing variables, whose truth or falsity depends on the values assigned to the variables. \end{df} \begin{df}[Existential Quantifier] We use the symbol $\exists$ to mean ``there exists.'' \end{df} \begin{df}[Universal Quantifier] We use the symbol $\forall$ to mean ``for all.'' \end{df} Observe that $\neg \forall = \exists$ and $\neg \exists = \forall$. \begin{exa} Write the negation of $(\forall n\in\BBN)(\exists x\in ]0;+\infty[)(nx<1)$. \end{exa} Solution: Since $\neg (\forall n\in\BBN) = (\exists n\in\BBN)$, $\neg (\exists x\in ]0;+\infty[) = (\forall x\in ]0;+\infty [)$ and $\neg (nx<1) = (nx \geq 1)$, the required statement is $$ (\exists n\in\BBN)(\forall x\in ]0;+\infty [)(nx \geq 1).$$ \section{Sets} We will consider a {\em set}\index{set} na{i}vely as a collection of objects called {\em elements}\index{elements}. We use the boldface letters $\BBN$ to denote the natural numbers (non-negative integers) and $\BBZ$ to denote the integers. The boldface letters $\BBR$ and $\BBC$ shall respectively denote the real numbers and the complex numbers. \bigskip If $S$ is a set and the element $x$ is in the set, then we say that $x$ {\em belongs to} $S$ and we write this as $x \in S.$ If $x$ does not belong to $S$ we write $x\not\in S.$ For example if $S = \{ n\in \BBN : n$ is the square of an integer $\}$, then $4 \in S$ but $2 \not\in S.$ We denote by $\card{A}$ the {\em cardinality} of $A$, that is, the number of elements that $A$ has. \bigskip If a set $A$ is totally contained in another set $B$, then we say that $A$ {\em is a subset of} $B$ and we write this as $A \subseteq B$ (some authors use the notation $A \subset B$). For example, if $S = \{$squares of integers$\}$, then $A = \{ 1, 4, 9, 16\}$ is a subset of $S.$ If $\exists x \in A$ such that $x \not\in B$, then $A$ is not a subset of $B$, which we write as $A \not\subseteq B.$ Two sets $A$ and $B$ are equal if $A \subseteq B$ and $B \subseteq A.$ \begin{exa}\label{exa:subsets3element} Find all the subsets of $\{a, b, c\}$. \end{exa} Solution: They are $$\begin{array}{lll} S_1 & = & \varnothing \\ S_2 & = & \{a\} \\ S_3 & = & \{b\} \\ S_4 & = & \{c\} \\ S_5 & = & \{a, b\} \\ S_6 & = & \{b, c\} \\ S_7 & = & \{c, a\} \\ S_8 & = & \{a, b, c\} \\ \end{array} $$ \begin{exa} \label{exa:subsets4element} Find all the subsets of $\{a, b, c, d\}$. \end{exa} Solution: The idea is the following. We use the result of example \ref{exa:subsets3element}. Now, a subset of $\{a, b, c, d\}$ either contains $d$ or it does not. Since the subsets of $\{a, b, c\}$ do not contain $d$, we simply list all the subsets of $\{a, b, c\}$ and then to each one of them we add $d$. This gives $$\begin{array}{lllllll} S_1 & = & \varnothing & \hspace{2cm} & S_9 & = & \{d\} \\ S_2 & = & \{a\} & \hspace{2cm} & S_{10} & = & \{a, d\} \\ S_3 & = & \{b\}& \hspace{2cm} & S_{11} & = & \{b, d\} \\ S_4 & = & \{c\} & \hspace{2cm} & S_{12} & = & \{c, d\} \\ S_5 & = & \{a, b\}& \hspace{2cm} & S_{13} & = & \{a, b, d\} \\ S_6 & = & \{b, c\}& \hspace{2cm} & S_{14} & = & \{b, c, d\} \\ S_7 & = & \{c, a\} & \hspace{2cm} & S_{15} & = & \{c, a, d\} \\ S_8 & = & \{a, b, c\} & \hspace{2cm} & S_{16} & = & \{a, b, c, d\} \\ \end{array} $$ \begin{thm} A finite $n$-element set has $2^n$ subsets. \end{thm} \begin{pf} We use induction and the idea of example \ref{exa:subsets4element}. Clearly a set $A$ with $n = 1$ elements has $2^1 = 2$ subsets: $\varnothing$ and $A$ itself. Assume every set with $n - 1$ elements has $2^{n-1}$ subsets. Let $B$ be a set with $n$ elements. If $x\in B$ then $B\setminus \{x\}$ is a set with $n - 1$ elements and so by the induction hypothesis it has $2^{n-1}$ subsets. For each subset $S \subseteq B\setminus \{x\}$ we form the new subset $S\cup \{x\}$. This is a subset of $B$. There are $2^{n-1}$ such new subsets, and so $B$ has a total of $2^{n-1} + 2^{n-1} = 2^n$ subsets. \end{pf} \begin{df} The {\em union} of two sets $A$ and $B$, is the set $$A\cup B = \{x:(x\in A)\ \vee\ (x\in B)\}.$$ This is read ``$A$ union $B$.'' See figure \ref{fig:a_union_b}. The {\em intersection} of two sets $A$ and $B$, is $$A\cap B = \{x:(x\in A)\ \wedge \ (x\in B)\}.$$ This is read ``$A$ intersection $B$.'' See figure \ref{fig:a_intersection_b}. The {\em difference} of two sets $A$ and $B$, is $$A\setminus B = \{x:(x\in A)\ \wedge (x\not\in B)\}.$$ This is read ``$A$ set minus $B$.'' See figure \ref{fig:a_minus_b}. \end{df} \vspace{1cm} \begin{figure}[h] \begin{minipage}{4cm}$$\psset{unit=1pc} \pscircle[fillstyle=hlines, fillcolor=red](-1,0){2}\pscircle[fillstyle=hlines, fillcolor=red](1,0){2} \uput[d](-1,-2){A}\uput[d](1,-2){B} $$\vspace{1cm}\footnotesize\hangcaption{$A\cup B$} \label{fig:a_union_b} \end{minipage} \hfill \begin{minipage}{4cm}$$ \psset{unit=1pc} \pscircle(-1,0){2}\pscircle(1,0){2} \uput[d](-1,-2){A}\uput[d](1,-2){B} \pscustom[fillstyle=solid,fillcolor=green]{\psarc(1,0){2}{120}{240}\psarc(-1,0){2}{270}{60}} $$\vspace{1cm}\footnotesize\hangcaption{$A\cap B$} \label{fig:a_intersection_b} \end{minipage} \hfill \begin{minipage}{4cm}$$\psset{unit=1pc} \pscircle[fillstyle=solid,fillcolor=blue](-1,0){2}\pscircle(1,0){2} \uput[d](-1,-2){A}\uput[d](1,-2){B} \pscustom[fillstyle=solid,fillcolor=white]{\psarc(1,0){2}{120}{240}\psarc(-1,0){2}{270}{60}} $$\vspace{1cm}\footnotesize\hangcaption{$A\setminus B$} \label{fig:a_minus_b} \end{minipage} \hfill \begin{minipage}{4cm} $$\psset{unit=1pc} \pscustom[fillstyle=solid,fillcolor=white]{\psline(-3.5,2.5)(-3.5,-2.5)(3.5,-2.5)(3.5,2.5)(-3.5,2.5)} \uput[r](1.5,1.5){\comp A} \pscircle[fillstyle=solid,fillcolor=green](0,0){2} \uput[u](0,0){A} $$\vspace{1cm}\footnotesize\hangcaption{$\comp A$} \label{fig:a_complement} \end{minipage} \end{figure} \begin{df} Let $A \subseteq X$. The {\em complement} of $A$ with respect to $X$ is $\complement A = X\setminus A$. \end{df} \bigskip Observe that $\comp A$ is all that which is outside $A$. Usually we assume that $A$ is a subset of some universal set $U$ which is tacitly understood. The complement $\comp A$ represents the event that $A$ does not occur. We represent $\comp A$ pictorially as in figure \ref{fig:a_complement}. \begin{exa}Let $U = \{0,1,2,3,4,5,6,7,8,9\}$ be the universal set of the decimal digits and let $A = \{0,2,4,6,8\}\subset U$ be the set of even digits. Then $\comp A = \{1,3,5,7,9\}$ is the set of odd digits. \end{exa} Observe that \begin{equation} \comp A\cap A =\ \varnothing . \end{equation} We also have the {\em De Morgan Laws}: if $A$ and $B$ share the same universal set, we have \begin{equation} \comp (A\cup B) =\ \comp A\cap \comp B, \end{equation} \begin{equation} \comp (A\cap B) =\ \comp A\cup \comp B. \end{equation} We will now prove one of the De Morgan's Rules. \begin{exa} Prove that $\comp (A\cup B) = \comp A\cap \comp B.$ \end{exa} Solution: Let $x \in \comp (A\cup B)$. Then $x \not\in A \cup B$. Thus $x \not\in A \wedge x \not\in B$, that is, $x \in \comp A \wedge x \in \comp B.$ This is the same as $x \in \comp A \cap \comp B.$ Therefore $\comp (A \cup B) \subseteq \comp A \cap \comp B.$ \bigskip Now, let $x \in \comp A \cap \comp B.$ Then $x\in \comp A \wedge x\in \comp B$. This means that $x \not\in A \wedge x \not\in B$ or what is the same $x \not\in A \cup B.$ But this last statement asserts that $x \in \comp (A \cup B)$. Hence $\comp A \cap \comp B \subseteq \comp (A \cup B).$ \bigskip Since we have shown that the two sets contain each other, it must be the case that they are equal. \begin{exa} Prove that $A\setminus(B \cup C) = (A\setminus B) \cap(A\setminus C)$. \end{exa} Solution: We have $$\begin{array}{lll} x \in A\setminus(B \cup C) & \iff & x \in A \wedge x\not \in (B \vee C) \\ & \iff & (x \in A) \ \ \ \wedge \ \ \ ( (x \not \in B) \ \ \ \wedge\ \ \ (x \not \in C)) \\ & \iff & (x \in A \ \ \ \wedge \ \ \ x \not \in B) \ \ \ \wedge \ \ \ (x \in A \ \ \ \wedge \ \ \ x \not \in C) \\ & \iff & (x \in A\setminus B) \ \ \ \wedge\ \ \ (x \in A \setminus C) \\ & \iff & x \in (A\setminus B) \cap(A\setminus C) \end{array} $$ \begin{exa} Shew how to write the union $A \cup B \cup C$ as a {\em disjoint} union of sets.\end{exa} Solution: The sets $A, B \setminus A, C \setminus (A \cup B)$ are clearly disjoint and $$ A \cup B \cup C = A \cup (B \setminus A) \cup (C \setminus (A \cup B)).$$ \begin{exa} Let $x_1 < x_2 < \cdots < x_n$ and $y_1 < y_2 < \cdots < y_m$ be two strictly increasing sequences of integers. Write an algorithm to determine $$\{x_1, x_2, \ldots , x_n\} \cap \{y_1, y_2, \ldots , y_m\}. $$ \end{exa} Solution: \bcp[Ovalbox]{Intersection}{n,m,X,Y} \COMMENT{$X$ is an array of length $n$.} \\ \COMMENT{$Y$ is an array of length $m$.} \\ n1 \GETS 0\\ m1 \GETS 0\\ \mathrm{common} \GETS 0 \\ \WHILE (n1 \neq n ) \AND (m1 \neq m) \DO \BEGIN \IF X[n1 + 1] < Y[m1+1] \THEN n1 \GETS n1 + 1 \ELSE \IF X[n1 + 1] > Y[m1+1] \THEN m1 \GETS m1 + 1 \ELSE \BEGIN n1 \GETS n1 + 1 \\ m1 \GETS m1 + 1 \\ \mathrm{common} \GETS \mathrm{common}+1 \END\END \ecp \section{Boolean Algebras and Boolean Operations} \begin{df} A {\em boolean algebra} consists of a set $X$ with at least two different elements $0$ and $1$, two binary operations $+$ (addition) and $\cdot$ (multiplication), and a unary operation $\overline{\hspace{4mm}}$ (called {\em complementation}) satisfying the following axioms. (We use the juxtaposition $AB$ to denote the product $A\cdot B$.) \begin{enumerate} \item \label{axi:BA-1} $A+B=B+A$ (commutativity of addition) \item \label{axi:BA-2} $AB=BA$ (commutativity of multiplication) \item \label{axi:BA-3} $A+(B+C)=(A+B)+C$ (associativity of addition) \item \label{axi:BA-4} $A(BC)=(AB)C$ (associativity of multiplication) \item \label{axi:BA-5} $A(B+C) = AB + AC$ (distributive law) \item \label{axi:BA-6} $A+(BC) = (A+B)(A+C)$ (distributive law) \item \label{axi:BA-7} $A +0 = A$ ($0$ is the additive identity) \item \label{axi:BA-8} $A1 = A$ ($1$ is the multiplicative identity) \item \label{axi:BA-9} $A + \overline{A} = 1$ \item \label{axi:BA-10} $A\overline{A}=0$ \end{enumerate} \end{df} \begin{exa} If we regard $0 = F$, $1=T$, $+=\vee$, $\cdot = \wedge$, and $\overline{\hspace{4mm}}=\neg$, then the logic operations over $\{F, T\}$ constitute a boolean algebra. \end{exa} \begin{exa} If we regard $0 = \varnothing$, $1=U$ (the universal set), $+=\cup$, $\cdot = \cap$, and $\overline{\hspace{4mm}}=\complement$, then the set operations over the subsets of $U$ constitute a boolean algebra. \end{exa} \begin{exa} Let $X = \{1, 2, 3, 5, 6, 10, 15, 30\}$, the set of positive divisors of $30$. We define $+$ as the least common multiple of two elements, $\cdot$ as the greatest common divisor of two elements, and $\overline{A} = \dfrac{30}{A}$. The additive identity is $1$ and the multiplicative identity is $30$. Under these operations $X$ becomes a boolean algebra. \end{exa} \bigskip The operations of complementation, addition and multiplication act on $0$ and $1$ as shewn in table \ref{tab:evaluation_rulesboolean}. \begin{table}[h] \begin{center} \begin{tabular}{|cc|ccc|} \hline $A$ & $B$ & $\overline{A}$ & $A + B$ & $AB$ \\ \hline $0$ & $0$ & $1$ & $0$ & $0$ \\ $0$ & $1$ & $1$ & $1$ & $0$ \\ $1$ & $0$ & $0$ & $1$ & $0$ \\ $1$ & $1$ & $0$ & $1$ & $1$ \\ \hline \end{tabular} \footnotesize\hangcaption{Evaluation Rules}\label{tab:evaluation_rulesboolean} \end{center} \end{table} The following properties are immediate. \begin{thm} $\overline{0} = 1$ and $\overline{1} = 0$. \end{thm} \begin{pf} Since $0$ is the additive identity, $\overline{0} = \overline{0} + 0$. But by axiom \ref{axi:BA-9}, $\overline{0} + 0 = 1$ and thus $\overline{0} = \overline{0} + 0 = 1$. \bigskip Similarly, since $1$ is the multiplicative identity, $\overline{1} = 1\cdot \overline{1}$. But by axiom \ref{axi:BA-10}, $1\cdot \overline{1} = 0$ and thus $\overline{1} = 1\cdot \overline{1} = 0$. \end{pf} \begin{thm}[Idempotent Laws] $A + A = A$ and $AA = A$ \end{thm} \begin{pf} We have $$A = A + 0 = A + A\cdot \overline{A} = (A + A)(A + \overline{A}) = (A + A)(1) = A + A. $$ \bigskip Similarly $$A = A1 = A(A + \overline{A}) = AA + A\cdot\overline{A} = AA + 0 = AA. $$ \end{pf} \begin{thm}[Domination Laws] $A + 1 = 1$ and $A\cdot 0 = 0$. \end{thm} \begin{pf} We have $$A + 1 = A + (A + \overline{A}) = (A + A) + \overline{A} = A + \overline{A} = 1. $$ \bigskip Also, $$A\cdot 0 = A(A\cdot \overline{A}) = (AA)\overline{A} = A\overline{A} = 0. $$ \end{pf} \begin{thm}[Uniqueness of the Complement] If $AB = 0$ and $A + B = 1$ then $B = \overline{A}$. \end{thm} \begin{pf} We have $$B = B1 = B(A + \overline{A}) = BA + B\overline{A} = 0 + B\overline{A} = B\overline{A}. $$ Also, $$\overline{A} = \overline{A}1 = \overline{A}(A + B) = \overline{A}\cdot A + \overline{A}B = \overline{A}B. $$Thus $$B = B\overline{A} = \overline{A}B = \overline{A}. $$ \end{pf} \begin{thm}[Involution Law] $\overline{\overline{A}} = A$ \end{thm} \begin{pf} By axioms \ref{axi:BA-9} and \ref{axi:BA-10}, we have the identities $$ 1 = \overline{A} + \overline{\overline{A}} \ \ \mathrm{and}\ \ \ \overline{\overline{A}}\cdot \overline{A} = 0. $$By uniqueness of the complement we must have $A = \overline{\overline{A}}$. \end{pf} \begin{thm}[De Morgan's Laws] $\overline{A + B} = \overline{A}\cdot \overline{B}$ and $\overline{A\cdot B} = \overline{A}+ \overline{B}$. \end{thm} \begin{pf} Observe that $$(A+B) + \overline{A}\cdot \overline{B} = (A + B + \overline{A})(A + B + \overline{B}) = (B + 1)(A + 1) = 1, $$and $$(A+B)\overline{A}\cdot \overline{B} = A\overline{A}\cdot \overline{B} + B\overline{A}\cdot \overline{B} = 0 + 0 = 0. $$ Thus $\overline{A}\cdot \overline{B} $ is the complement of $A+B$ and so we must have $\overline{A}\cdot \overline{B} = \overline{A+B}$. \bigskip To obtain the other De Morgan Law put $\overline{A}$ instead of $A$ and $\overline{B}$ instead of $B$ in the law just derived and use the involution law: $$\overline{\overline{A} + \overline{B}} = \overline{\overline{A}} \cdot \overline{\overline{B}} = AB. $$Taking complements once again we have $$\overline{\overline{A} + \overline{B}} = AB \implies \overline{A} + \overline{B} = \overline{AB}. $$ \end{pf} \begin{thm} $AB + A\overline{B} = A$. \end{thm} \begin{pf} Factoring $$AB + A\overline{B} = A(B + \overline{B}) = A(1) = A. $$ \end{pf} \begin{thm} $A(\overline{A} + B) = AB$ and $A + \overline{A}B = A+B$. \end{thm} \begin{pf} Multiplying $$A(\overline{A} + B)= A\overline{A} + AB = 0 + AB = AB.$$Using the distributive law, $$A + \overline{A}B = (A + \overline{A})(A + B) = 1(A+B) = A+B.$$ \end{pf} \begin{thm}[Absorption Laws] $A + AB = A$ and $A(A+B) = A$. \end{thm} \begin{pf} Factoring and using the domination laws: $$A + AB = A(1 + B) = A1 = A. $$Expanding and using the identity just derived: $$A(A+B) = AA + AB = A + AB = A. $$ \end{pf} \section{Sum of Products and Products of Sums} Given a truth table in some boolean variables, we would like to find a function whose output is that of the table. This can be done by either finding a {\em sum of products} (SOP) or a {\em product of sums} (POS) for the table. To find a sum of products from a truth table: \begin{dingautolist}{202} \item identify the rows having output $1$. \item for each such row, write the variable if the variable input is $1$ or write the complement of the variable if the variable input is $0$, then multiply the variables forming a term.\item add all such terms. \end{dingautolist} To find a product of sums from a truth table: \begin{dingautolist}{202} \item identify the rows having output $0$. \item for each such row, write the variable if the variable input is $0$ or write the complement of the variable if the variable input is $1$, then add the variables forming a sum \item multiply all such sums. \end{dingautolist} \begin{exa} Find a SOP and a POS for $Z$. $$\begin{array}{lll|l} A & B & C & Z \\ \hline 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array}$$ \end{exa} Solution: The output ($Z$) $1$'s occur on the rows (i) $A = 0, B = 0, C = 0$, so we form the term $(\overline{A}) (\overline{B})(\overline{C})$, (ii) $A = 0, B=1, C = 0$, so we form the term $\overline{A}B \overline{C}$, (iii) $A = 1, B = 1, C = 0$, so we form the term $AB \overline{C}$, and (iv) $A = B = C = 1$, giving the term $ABC$. The required SOP is $$Z = (\overline{A}) (\overline{B})(\overline{C}) + \overline{A}B \overline{C} + AB \overline{C} + ABC.$$ The output ($Z$) $0$'s occur on the rows (i) $A = 0, B = 0, C = 1$, so we form the term $A + B + \overline{C}$, (ii) $A = 0, B=1, C = 1$, so we form the term $A + \overline{B} + \overline{C}$, (iii) $A = 1, B = 0, C = 0$, so we form the term $\overline{A} + B + C$, and (iv) $A =1, B = 0, C = 1$, giving the term $\overline{A} + B + \overline{C}$. The required POS is $$Z = (A + B + \overline{C})(A + \overline{B} + \overline{C})( \overline{A} + B + C) ( \overline{A} + B + \overline{C}).$$ \bigskip Using the axioms of a boolean algebra and the aforementioned theorems we may simplify a given boolean expression, or transform a SOP into a POS or viceversa. \begin{exa} Convert the following POS to a SOP: $$(A + \overline{B}C)(A + \overline{B}D).$$ \end{exa} Solution: $$\begin{array}{lll} (A + \overline{B}C)(A + \overline{B}D) & = & AA + A\overline{B}D + A\overline{B}C + \overline{B}C\overline{B}D \\ & = & A + A\overline{B}D + A\overline{B}C + \overline{B}CD \\ & = & A + \overline{B}CD. \end{array}$$ \begin{exa} Convert the following SOP to a POS: $$A\overline{B} + \overline{C}D.$$ \end{exa} Solution: $$ \begin{array}{lll} A\overline{B} + \overline{C}D & = & (A\overline{B} + \overline{C})(A\overline{B} + D) \\ & = & (A + \overline{C})(\overline{B} + \overline{C})(A + D)(\overline{B} + D). \end{array} $$ \begin{exa} Write $\overline{W}XY + \overline{W}XZ + \overline{Y + Z}$ as a sum of two products. \end{exa} Solution: We have $$\begin{array}{lll} \overline{W}XY + \overline{W}XZ + \overline{Y + Z} & = & \overline{W}X(Y + Z) + \overline{Y + Z} \\ & = & \overline{W}X + \overline{Y + Z} \\ & = & \overline{W}X + \overline{Y}\cdot \overline{Z}, \end{array} $$where we have used the fact that $AB + \overline{B} = A+\overline{B}$ and the De Morgan laws. \section{Logic Puzzles} The boolean algebra identities from the preceding section may help to solve some logic puzzles. \begin{exa} Brown, Johns and Landau are charged with bank robbery. The thieves escaped in a car that was waiting for them. At the inquest Brown stated that the criminals had escaped in a blue Buick; Johns stated that it had been a black Chevrolet, and Landau said that it had been a Ford Granada and by no means blue. It turned out that wishing to confuse the Court, each one of them only indicated correctly either the make of the car or only its colour. What colour was the car and of what make? \end{exa} Solution: Consider the sentences \begin{center} \begin{tabular}{lll} $A$ & = & the car is blue \\ $B$ & = & the car is a Buick \\ $C$ & = & the car is black \\ $D$ & = & the car is a Chevrolet \\ $E$ & = & the car is a Ford Granada \\ \end{tabular}\end{center} Since each of the criminals gave one correct answer, it follows that Brown's declaration $A + B$ is true. Similarly, Johns's declaration $C + D$ is true, and Landau's declaration $\overline{A} + E$ is true. It now follows that $$(A + B) \cdot (C + D) \cdot (\overline{A} + E)$$ is true. Upon multiplying this out, we obtain $$ (A\cdot C\cdot \overline{A}) + (A \cdot C \cdot E) + (A \cdot D \cdot \overline{A}) + (A \cdot D \cdot E) + (B \cdot C \cdot \overline{A}) + (B \cdot C \cdot E) + (B \cdot D \cdot \overline{A}) + (B \cdot D \cdot E) .$$ From the hypothesis that each of the criminals gave one correct answer, it follows that each of the summands, except the fifth, is false. Thus $B \cdot C \cdot \overline{A}$ is true, and so the criminals escaped in a black Buick. \begin{exa} Margie, Mimi, April, and Rachel ran a race. Asked how they made out, they replied: \\ Margie: ``April won; Mimi was second.'' \\ Mimi: ``April was second and Rachel was third.''\\ April: ``Rachel was last; Margie was second.'' \bigskip If each of the girls made one and only one true statement, who won the race? \end{exa} Solution: Consider the sentences \begin{center} \begin{tabular}{lll} $A$ & = & April was first \\ $B$ & = & April was second \\ $C$ & = & Mimi was second \\ $D$ & = & Margie was second \\ $E$ & = & Rachel was third \\ $F$ & = & Rachel was last \end{tabular}\end{center} Since each of the girls gave one true statement we have that $$(A + C)(B + E)(F + D) = 1. $$ Multiplying this out $$ABF + ABD + AEF + AED + CBF + CBD + CEF + CED = 1. $$ Now, $AB = EF = BC = CD = 0$ so the only surviving term is $AED$ and so April was first, Margie was second, Rachel was third, and Mimi was last. \begin{exa} Having returned home, Maigret rang his office on quai des Orf\`{e}vres. \\ \par\indent ``Maigret here . Any news?'' \\ \par\indent ``Yes Chief. The inspectors have reported. Torrence thinks that if Fran\c{c}ois was drunk, then either Etienne is the murderer or Fran\c{c}ois is lying. Justin is of the opinion that either Etienne is the murderer or Fran\c{c}ois was not drunk and the murder occurred after midnight. Inspector Lucas asked me to tell you that if the murder had occurred after midnight, then either Etienne is the murderer or Fran\c{c}ois is lying. Then there was a ring from \ldots .'' \par\indent ``That's all, thanks. That's enough!'' The commissar replaced the receiver. He knew that when Fran\c{c}ois was sober he never lied. Now everything was clear to him. Find, with proof, the murderer. \end{exa} Solution: Represent the following sentences as: \begin{center} \begin{tabular}{lll}$A $ & = & {\rm Fran\c{c}ois\ was\ drunk},\\$B$ & = & {\rm Etienne\ is\ the\ murderer},\\ $C$ & = & {\rm Fran\c{c}ois\ is\ telling\ a\ lie},\\ $D$ & = & {\rm the\ murder\ took\ place\ after\ midnight}. \\ \end{tabular} \end{center} We then have $$A \implies (B + C), \ \ B + \overline{A}D, \ \ D \implies (B + C).$$Using the identity $$X \implies Y = \overline{X} + Y,$$we see that the output of the product of the following sentences must be 1: $$(\overline{A} + B + C)(B + \overline{A}D)(\overline{D} + B + C).$$After multiplying the above product and simplifying, we obtain $$B + C\overline{A}D.$$So, either Etienne is the murderer, or the following events occurred simultaneously: Fran\c{c}ois lied, Fran\c{c}ois was not drunk and the murder took place after midnight. But Maigret knows that $\overline{A}C = 0$, thus it follows that $E = 1,$ i.e., Etienne is the murderer. \section*{Homework}\addcontentsline{toc}{section}{Homework}\markright{Homework} \small \begin{pro} Construct the truth table for $(p \implies q) \wedge q$. \\ \begin{answer3} $$ \begin{array}{|cc|cc|} \hline p & q & p \implies q & (p\implies q) \wedge q \\ F & F & T & F \\ F & T & T & T \\ T & F & F & F \\ T & T & T & T\\ \hline \end{array}$$ \end{answer3} \end{pro} \begin{pro} By means of a truth table, decide whether $(p\wedge q) \vee (\neg p) = p \vee (\neg p)$. That is, you want to compare the outputs of $(p\wedge q) \vee (\neg p)$ and $p \vee (\neg p)$. \begin{answer3} The desired truth table is $$\begin{array}{|cc|cccc|}\hline p & q & p\wedge q & \neg p & p \vee \neg p & (p\wedge q) \vee (\neg p) \\ \hline F & F & F & T & T & T\\ F & T & F & T & T & T\\ T & F & F & F & T& F \\ T & T & T & F & T & T\\ \hline \end{array} $$ \end{answer3} \end{pro} \begin{pro} Explain whether the following assertion is true and negate it without using the negation symbol $\neg$: $$ \forall n\in\BBN\ \exists m\in \BBN\ \big(n>3\implies (n+7)^2>49+m\big) $$ \begin{answer3} The assertion is true. We have $$(n+7)^2>49+m \iff n^2 + 14n > m. $$ Hence, taking $m = n^2+14n -1$ for instance (or any smaller number), will make the assertion true. \end{answer3} \end{pro} \begin{pro} Explain whether the following assertion is true and negate it without using the negation symbol $\neg$: $$ \forall n\in\BBN\ \exists m\in \BBN\ \big(n^2>4n\implies 2^n>2^m+10\big) $$ \end{pro} \begin{pro} Prove by means of set inclusion that $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$. \begin{answer3} We have, $$\begin{array}{lll} x \in (A \cup B) \cap C & \iff & x\in (A \cup B) \wedge x\in C \\ & \iff & (x\in A \vee x\in B) \wedge x\in C \\ & \iff & (x\in A \wedge x \in C) \vee (x\in B \wedge x\in C) \\ & \iff & (x\in A\cap C) \vee (x\in B \cap C)\\ & \iff & x \in (A \cap C) \cup (B \cap C), \end{array}$$which establishes the equality. \end{answer3} \end{pro} \begin{pro} Obtain a sum of products for the truth table $$\begin{array}{lll|l} A & B & C & Z \\ \hline 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ \end{array}$$ \begin{answer3} $$\overline{A}\cdot \overline{B}\cdot \overline{C} + \overline{A}\cdot \overline{B}\cdot C + \overline{A}\cdot B \cdot \overline{C} + A\cdot \overline{B}\cdot \overline{C} $$ \end{answer3} \end{pro} \begin{pro} Use the Inclusion-Exclusion Principle to determine how many integers in the set $\{1,2,\ldots , 200\}$ are neither divisible by $3$ nor $7$ but are divisible by $11$. \begin{answer3} $10$ \end{answer3} \end{pro} \Closesolutionfile{discans} \section*{Answers}\addcontentsline{toc}{section}{Answers}\markright{Answers} {\small\input{discansC3}} \chapter{Relations and Functions} \section{Partitions and Equivalence Relations} \begin{df} Let ${\mathscr S} \neq \varnothing$ be a set. A {\em partition} of ${\mathscr S}$ is a collection of non-empty, pairwise disjoint subsets of ${\mathscr S}$ whose union is ${\mathscr S}$. \end{df} \begin{exa} Let $$2\BBZ = \{ \ldots , -6, -4, -2, 0, 2, 4, 6, \ldots\}= \overline{0}$$ be the set of even integers and let $$2\BBZ + 1 = \{ \ldots , -5, -3, -1, 1, 3, 5, \ldots\}= \overline{1}$$ be the set of odd integers. Then $$(2\BBZ)\cup (2\BBZ + 1) = \BBZ, \ \ (2\BBZ)\cap (2\BBZ + 1) = \varnothing,$$ and so $\{2\BBZ, 2\BBZ + 1\}$ is a partition of $\BBZ$. \label{ex:mod2}\end{exa} \begin{exa} Let $$3\BBZ = \{ \ldots -9, , -6, -3, 0, 3, 6, 9, \ldots\} = \overline{0}$$ be the integral multiples of $3$, let $$3\BBZ + 1 = \{ \ldots , -8, -5, -2, 1, 4, 7, \ldots\}= \overline{1}$$ be the integers leaving remainder $1$ upon division by $3$, and let $$3\BBZ + 2 = \{ \ldots , -7, -4, -1, 2, 5, 8, \ldots\} = \overline{2}$$ be integers leaving remainder $2$ upon division by $3$. Then $$(3\BBZ)\cup (3\BBZ + 1) \cup (3\BBZ + 2) = \BBZ, $$ $$ (3\BBZ)\cap (3\BBZ + 1) = \varnothing, \ (3\BBZ)\cap (3\BBZ + 2) = \varnothing, (3\BBZ + 1)\cap (3\BBZ + 2) = \varnothing,$$ and so $\{3\BBZ, 3\BBZ + 1, 3\BBZ + 2\}$ is a partition of $\BBZ$. \label{ex:mod3}\end{exa} \begin{rem} Notice that $\overline{0}$ and $\overline{1}$ do not mean the same in examples \ref{ex:mod2} and \ref{ex:mod3}. Whenever we make use of this notation, the integral divisor must be made explicit. \end{rem} \begin{exa} Observe $$\BBR = (\BBQ) \cup (\BBR \setminus \BBQ), \ \ \varnothing = (\BBQ) \cap (\BBR \setminus \BBQ),$$which means that the real numbers can be partitioned into the rational and irrational numbers. \end{exa} \begin{df} Let $A, B$ be sets. A {\em relation} $R$ is a subset of the Cartesian product $A\times B$. We write the fact that $(x, y)\in R$ as $x \sim y.$ \end{df} \begin{df} Let $A$ be a set and $R$ be a relation on $A\times A$. Then $R$ is said to be \begin{itemize} \item {\bf reflexive} if $(\forall x\in A), x\sim x$, \item {\bf symmetric} if $(\forall (x, y)\in A^2), x\sim y \implies y \sim x$, \item {\bf anti-symmetric} if $(\forall (x, y)\in A^2), (x\sim y) \AND (y \sim x) \implies x = y$, \item {\bf transitive} if $(\forall (x, y, z)\in A^3), (x\sim y)\AND (y\sim z) \implies (x\sim z)$. \end{itemize} A relation $R$ which is reflexive, symmetric and transitive is called an {\em equivalence relation} on $A$. A relation $R$ which is reflexive, anti-symmetric and transitive is called a {\em partial order} on $A$. \end{df} \begin{exa} Let ${\mathscr S} = $\{All Human Beings\}, and define $\sim$ on ${\mathscr S}$ as $a\sim b$ if and only if $a$ and $b$ have the same mother. Then $a\sim a$ since any human $a$ has the same mother as himself. Similarly, $a\sim b \implies b\sim a$ and $(a\sim b)\AND (b\sim c) \implies (a\sim c)$. Therefore $\sim$ is an equivalence relation. \end{exa} \begin{exa} Let $L$ be the set of all lines on the plane and write $l_1\sim l_2$ if $l_1 || l_2$ (the line $l_1$ is parallel to the line $l_2$). Then $\sim$ is an equivalence relation on $L$. \end{exa} \begin{exa} Let $X$ be a collection of sets. Write $A\sim B$ if $A \subseteq B$. Then $\sim$ is a partial order on $X$. \end{exa} \begin{exa} For $(a, b)\in\BBR^2$ define $$a\sim b \Leftrightarrow a^2 + b^2 > 2.$$ Determine, with proof, whether $\sim$ is reflexive, symmetric, and/or transitive. Is $\sim$ an equivalence relation? \end{exa} Solution: Since $0^2 + 0^2 \ngtr 2$, we have $0\nsim 0$ and so $\sim$ is not reflexive. Now, $$\begin{array}{lll} a \sim b & \Leftrightarrow & a^2 + b^2 \\ & \Leftrightarrow & b^2 + a^2 \\ & \Leftrightarrow & b \sim a,\end{array}$$ so $\sim$ is symmetric. Also $0 \sim 3$ since $0^2 + 3^2 > 2$ and $3 \sim 1$ since $3^2 + 1^2 > 2$. But $0 \nsim 1$ since $0^2 + 1^2 \ngtr 2$. Thus the relation is not transitive. The relation, therefore, is not an equivalence relation. \begin{exa} For $(a, b) \in(\BBQ^*)^2$ define the relation $\sim$ as follows: $a\sim b \Leftrightarrow \frac{a}{b} \in \BBZ$. Determine whether this relation is reflexive, symmetric, and/or transitive. \end{exa} Solution: $a \sim a$ since $\frac{a}{a} = 1\in \BBZ$, and so the relation is reflexive. The relation is not symmetric. For $2 \sim 1$ since $\frac{2}{1}\in \BBZ$ but $1 \nsim 2$ since $\frac{1}{2} \not\in \BBZ$. The relation is transitive. For assume $a\sim b$ and $b\sim c$. Then there exist $(m, n)\in \BBZ^2$ such that $\frac{a}{b} = m, \frac{b}{c} = n$. This gives $$\frac{a}{c} = \frac{a}{b}\cdot\frac{b}{c} = mn\in\BBZ,$$and so $a\sim c.$ \begin{exa} Give an example of a relation on $\BBZ^*$ which is reflexive, but is neither symmetric nor transitive. \end{exa} Solution: Here is one possible example: put $a\sim b \Leftrightarrow \frac{a^2 + a}{b}\in \BBZ$. Then clearly if $a\in\BBZ^*$ we have $a\sim a$ since $\frac{a^2 + a}{a} = a + 1 \in \BBZ$. On the other hand, the relation is not symmetric, since $5\sim 2$ as $\frac{5^2 + 5}{2} = 15\in \BBZ$ but $2\not\sim 5$, as $\frac{2^2 + 2}{5} = \frac{6}{5}\not\in \BBZ$. It is not transitive either, since $\frac{5^2 + 5}{3}\in\BBZ\implies 5 \sim 3$ and $\frac{3^2 + 3}{12}\in\BBZ\implies 3 \sim 12$ but $\frac{5^2 + 5}{12}\not\in\BBZ$ and so $5\nsim 12$. \begin{df} Let $\sim$ be an equivalence relation on a set ${\mathscr S}$. Then the {\em equivalence class of $a$} is defined and denoted by $$[a] = \{x\in {\mathscr S}: x\sim a\} .$$ \end{df} \begin{lem} Let $\sim$ be an equivalence relation on a set ${\mathscr S}$. Then two equivalence classes are either identical or disjoint. \label{lem:equiv_classes}\end{lem} \begin{pf} We prove that if $(a, b)\in {\mathscr S}^2$, and $[a]\cap [b] \neq \varnothing$ then $[a] = [b]$. Suppose that $x\in [a]\cap [b]$. Now $x\in [a]\implies x\sim a \implies a\sim x$, by symmetry. Similarly, $x\in [b]\implies x\sim b.$ By transitivity $$(a\sim x)\AND (x\sim b) \implies a\sim b.$$Now, if $y\in [b]$ then $b\sim y$. Again by transitivity, $a\sim y$. This means that $y\in [a]$. We have shewn that $y\in [b]\implies y\in [a]$ and so $[b]\subseteq [a]$. In a similar fashion, we may prove that $[a]\subseteq [b]$. This establishes the result. \end{pf} \bigskip As a way of motivating the following result, let us consider the following example. Suppose that a child is playing with $10$ bricks, which come in $3$ different colours and are numbered $1$ through $10$. Bricks $1$ through $3$ are red, bricks $4$ through $7$ are white and bricks $8$ through $10$ are blue. \bigskip Suppose we induce the relation $a\sim b$ whenever brick number $a$ has the same colour as brick number $b$. The $\sim$ is clearly an equivalence relation and the bricks are partitioned according to colour. In this partition we have $3$ classes (colours): bricks with numbers in $\{1, 2, 3\}$ belong to the ``red'' class; bricks with numbers in $\{4, 5, 6, 7\}$ belong to the ``white'' class; and bricks with numbers in $\{8, 9, 10\}$ belong to the ``blue'' class. Suppose that instead of grouping the bricks by colour we decided to group the bricks by the remainder given by the number of the brick upon division by $4$, thus $a\approx b$ if $a$ and $b$ leave the same remainder upon division by $4$. Clearly $\approx$ is also an equivalence relation. In this case bricks with numbers in $\{4, 8\}$ belong to the ``$0$'' class; bricks with numbers in $\{1, 5, 9\}$ belong to the ``$1$'' class; bricks with numbers in $\{2, 4, 10\}$ belong to the ``$2$'' class; and bricks with numbers in $\{3, 7\}$ belong to the ``$3$'' class. Notice on the same set we constructed two different partitions, and that classes need not have the same number of elements. \begin{thm} Let ${\mathscr S} \neq \varnothing$ be a set. Any equivalence relation on ${\mathscr S}$ induces a partition of ${\mathscr S}$. Conversely, given a partition of ${\mathscr S}$ into disjoint, non-empty subsets, we can define an equivalence relation on ${\mathscr S}$ whose equivalence classes are precisely these subsets. \label{thm:equiv_relation_yields_partition}\end{thm} \begin{pf} By Lemma \ref{lem:equiv_classes}, if $\sim$ is an equivalence relation on ${\mathscr S}$ then $$ {\mathscr S} = \bigcup _{a\in S} [a],$$ and $[a]\cap [b] = \varnothing$ if $a\nsim b$. This proves the first half of the theorem. \bigskip Conversely, let $$ {\mathscr S} = \bigcup _{\alpha} S_\alpha, \ \ S_\alpha \cap S_\beta = \varnothing\ \ {\rm if}\ \alpha \neq \beta,$$ be a partition of ${\mathscr S}$. We define the relation $\approx$ on ${\mathscr S}$ by letting $a\approx b$ if and only if they belong to the same $S_\alpha$. Since the $S_\alpha$ are mutually disjoint, it is clear that $\approx$ is an equivalence relation on ${\mathscr S}$ and that for $a\in S_\alpha,$ we have $[a] = S_\alpha$. \end{pf} \section{Functions} \begin{df} By a {\em function}\index{function} $f:\dom{f}\rightarrow\target{f}$ we mean the collection of the following ingredients: \begin{dingautolist}{202} \item a {\em name} for the function. Usually we use the letter $f$. \item a set of inputs called the {\em domain} of the function. The domain of $f$ is denoted by $\dom{f}$. \item an {\em input parameter }, also called {\em independent variable} or {\em dummy variable}. We usually denote a typical input by the letter $x$.\index{function!domain} \item a set of possible outputs of the function, called the {\em target set} of the function. The target set of $f$ is denoted by $\target{f}$.\index{function!target set} \item an {\em assignment rule} or {\em formula}, assigning to {\bf every input} a {\bf unique} output. This assignment rule for $f$ is usually denoted by $x\mapsto f(x)$. The output of $x$ under $f$ is also referred to as the {\em image of $x$ under $f$}, \index{function!image} and is denoted by $f(x)$. \index{function!assingment rule} \end{dingautolist} \end{df} \vspace{1cm} \begin{figure}[h] $$ \psset{unit=.7cm}\rput(-2,0){ \pscircle(-2,0){2} \psellipse[fillcolor=yellow, fillstyle=solid](6.5,0)(5,2.2) \pscircle[fillcolor=white, fillstyle=solid](6,0){2} \psline[linewidth=.7pt, labels=none, showpoints=true]{*->>}(-1.8,0)(5.9,0) \psline[linewidth=.7pt, labels=none, showpoints=true]{*->>}(-1.8,.5)(5.9,.5) \psline[linewidth=.7pt, labels=none, showpoints=true]{*->>}(-1.8,-.5)(5.9,-.5) \rput(-2, -1){{\rm domain\ }}% \rput(6,1){{\rm image\ }}% \rput(1,1){{\rm rule\ } }% \rput(10, 0){{\rm target\ set\ }}% \psdots*[linewidth=.5pt](-2,0)(-2, .5)(-2, -.5)(6,0)(6,.5)(6, -.5)(8.3,1)(8.3,.5)} $$ \vspace{2cm} \footnotesize\hangcaption{The main ingredients of a function.} \label{df:function} \end{figure} The notation\footnote{Notice the difference in the arrows. The straight arrow $\longrightarrow$ is used to mean that a certain set is associated with another set, whereas the arrow $\mapsto$ (read ``maps to'') is used to denote that an input becomes a certain output.} $$\fun{f}{x}{f(x)}{\dom{f}}{\target{f}} $$ read ``the function $f$, with domain $\dom{f}$, target set $\target{f}$, and assignment rule $f$ mapping $x$ to $f(x)$'' conveys all the above ingredients. See figure \ref{df:function}. \begin{df} The {\em image} $\im{f}$ of a function $f$ is its set of actual outputs. In other words, $$\im{f} = \{f(a): a\in\dom{f}\}.$$ Observe that we always have $\im{f} \subseteq \target{f}$. \end{df} It must be emphasised that the uniqueness of the image of an element of the domain is crucial. For example, the diagram in figure \ref{mult_ima} {\em does not} represent a function. The element $1$ in the domain is assigned to more than one element of the target set. Also important in the definition of a function is the fact that {\em all the elements} of the domain must be operated on. For example, the diagram in \ref{non-exhau} {\em does not} represent a function. The element $3$ in the domain is not assigned to any element of the target set. \vspace{1cm} \begin{figure}[h] %NOTE: Beware of leaving blank spaces whenever you are in the PSTRICKS %environment. It does not tolerate blank horizontal lines and it will %give you an error in your LaTeX run \centering \begin{minipage}{7cm}$$ \psset{unit=1.7pc}\rput(-1,-.5){ \rput(0, -.5){3} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,0)(2.9,-.5) \rput(3, -.5){8} \rput(0,0){1} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,0)(2.9,0) \rput(3,0){2} \rput(0, .5){2} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,.5)(2.9,.5) \rput(3,.5){4} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(0.2,-.5)(2.9,-1) \psellipse(1,2) \psellipse(3,0)(1,2) \rput(3, -1){16}} $$\vspace{1.5cm} \footnotesize\hangcaption{Not a function.}\label{mult_ima}\end{minipage} \begin{minipage}{7cm} $$\psset{unit=1.7pc}\rput(-1,-.5){\rput(0,0){1} \rput(0,.5){0} \rput(0, -.5){3} \rput(3,.5){4} \rput(3, -.5){8} \psellipse(1,2) \psellipse(3,0)(1,2) \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(0.2,0)(2.9,-.5) \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(0.2,.5)(2.9,.5)} $$ \vspace{1.5cm} \footnotesize\hangcaption{Not a function.} \label{non-exhau} \end{minipage} \end{figure} \begin{exa}\label{exa:three_ways_function} Consider the sets $A = \{1, 2, 3\}$, $B = \{1,4,9\}$, and the rule $f$ given by $f(x) = x^2$, which means that $f$ takes an input and squares it. Figures \ref{fig:three_ways_function1} through \ref{fig:three_ways_function2} give three ways of representing the function $f:A\rightarrow B$. \end{exa} \vspace{1cm} \begin{figure}[h] \begin{minipage}{4cm} $$\fun{f}{x}{x^2}{\{1,2,3\}}{\{1,4, 9\}} $$ \vspace{.6cm} \footnotesize\hangcaption{Example \ref{exa:three_ways_function}.}\label{fig:three_ways_function1} \end{minipage} \hfill \begin{minipage}{4cm} $$ f: \begin{pmatrix} 1 & 2 & 3 \cr 1 & 4 & 9 \end{pmatrix} $$ \vspace{1cm} \footnotesize\hangcaption{Example \ref{exa:three_ways_function}.}\label{fig:three_ways_function2} \end{minipage} \hfill \begin{minipage}{4cm}$$ \psset{unit=2pc} \rput(-1,-.5){\rput(0, -.5){3} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,-.5)(2.9,-.5) \rput(3, -.5){9} \rput(0,0){2} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,0)(2.9,0) \rput(3,0){4} \rput(0, .5){1} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,.5)(2.9,.5) \rput(3,.5){1} \psellipse(1,2) \psellipse(3,0)(1,2)}$$\vspace{2cm} \footnotesize\hangcaption{Example \ref{exa:three_ways_function}.}\label{fig:three_ways_functio3}\end{minipage} \end{figure} \begin{exa}Find all functions with domain $\{a, b\}$ and target set $\{c, d\}$. \end{exa} Solution: There are $2^2 = 4$ such functions, namely: \begin{dingautolist}{202} \item $f_1$ given by $f_1(a) = f_1(b) = c.$ Observe that $\im{f_1} = \{c\}$. \item $f_2$ given by $f_2(a) = f_2(b) = d.$ Observe that $\im{f_2} = \{d\}$. \item $f_3$ given by $f_3(a) = c, f_3(b) = d.$ Observe that $\im{f_3} = \{c, d\}$. \item $f_4$ given by $f_4(a) = d, f_4(b) = c.$ Observe that $\im{f_4} = \{c, d\}$. \end{dingautolist} \begin{df} A function is {\em injective} or {\em one-to-one}\index{function!injective} whenever two different values of its domain generate two different values in its image. A function is {\em surjective} or {\em onto} if every element of its target set is hit, that is, the target set is the same as the image of the function. A function is {\em bijective} if it is both injective and surjective. \end{df} \vspace{1cm} \begin{figure}[h] \begin{minipage}{3cm} \centering $$ \psset{unit=1.7pc} \rput(-1,-.5){\rput(1.5, .8){\alpha} \rput(0, .5){1} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,.5)(2.9,.5) \rput(3,.5){2} \rput(0,0){2} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,0)(2.9,0) \rput(3,0){8} \rput(0, -.5){3} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(0.2,-.5)(2.9,-.5) \rput(3,-.5){4} \psellipse(1,2) \psellipse(3,0)(1,2)} $$ \vspace{1cm}\footnotesize \hangcaption{An injection.} \label{injection} \end{minipage} \hfill \begin{minipage}{3cm}$$ \psset{unit=1.7pc} \rput(-1,-.5){\rput(1.5, .8){\beta} \psellipse(1,2) \psellipse(3,0)(1,2) \rput(0,0){2} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,0)(2.9,0) \rput(3,0){2} \rput(0, .5){1} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,.5)(2.9,.5) \rput(3,.5){4} \rput(0, -.5){3} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(0.2,-.5)(2.9,.5)} $$ \vspace{1cm} \footnotesize\hangcaption{Not an injection} \label{not_injection} \end{minipage} \hfill \begin{minipage}{3cm} $$ \psset{unit=1.7pc} \rput(-1,-.5){\rput(0,0){2} \rput(0, .5){1} \rput(0, -.5){3} \rput(3,0){2} \rput(3,.5){4} \rput(1.5, .8){\gamma} \psellipse(1,2) \psellipse(3,0)(1,2) \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,0)(2.9,0) \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,.5)(2.9,.5) \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(0.2,-.5)(2.9,.5)} $$\vspace{1cm} \footnotesize\hangcaption{A surjection} \label{surjection} \end{minipage}\hfill \begin{minipage}{3cm} $$ \psset{unit=1.7pc} \rput(-1,-.5){\rput(3, -1){8} \rput(1.5, .8){\delta} \psellipse(1,2) \psellipse(3,0)(1,2) \rput(0,0){2} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,0)(2.9,0) \rput(3,0){2} \rput(0, .5){1} \psline[linewidth=.4pt, labels=none, showpoints=true]{*->>}(.2,.5)(2.9,.5) \rput(3,.5){4}} $$\vspace{1cm} \footnotesize\hangcaption{Not a surjection} \label{not_surjection} \end{minipage} \end{figure} \begin{exa} The function $\alpha$ in the diagram \ref{injection} is an injective function. The function represented by the diagram \ref{not_injection}, however is not injective, since $\beta (3) = \beta (1) = 4$, but $3 \neq 1$. The function $\gamma$ represented by diagram \ref{surjection} is surjective. The function $\delta$ represented by diagram \ref{not_surjection} is not surjective since $8$ is part of the target set but not of the image of the function. \end{exa} \begin{thm}\label{thm:size_domain_image_injections_surjections} Let $f:A\rightarrow B$ be a function, and let $A$ and $B$ be finite. If $f$ is injective, then $\card{A} \leq \card{B}$. If $f$ is surjective then $\card{B}\leq \card{A}$. If $f$ is bijective, then $\card{A} = \card{B}$. \end{thm} \begin{pf} Put $n = \card{A}$, $A = \{x_1,x_2, \ldots ,x_n\}$ and $m = \card{B}$, $B = \{y_1,y_2, \ldots ,y_m\}$. \bigskip If $f$ were injective then $f(x_1), f(x_2), \ldots , f(x_n)$ are all distinct, and among the $y_k$. Hence $n \leq m$. \bigskip If $f$ were surjective then each $y_k$ is hit, and for each, there is an $x_i$ with $f(x_i) = y_k$. Thus there are at least $m$ different images, and so $n \geq m$. \end{pf} \begin{df} A {\em permutation} is a function from a finite set to itself which reorders the elements of the set. \end{df} \begin{rem} By necessity then, permutations are bijective. \end{rem} \begin{exa} The following are permutations of $\{a, b, c\}$: $$ f_1:\begin{pmatrix} a & b & c \cr a & b & c \end{pmatrix} \qquad f_2:\begin{pmatrix} a & b & c \cr b & c & a \end{pmatrix}. $$ The following are {\em not} permutations of $\{a, b, c\}$: $$ f_3:\begin{pmatrix} a & b & c \cr a & a & c \end{pmatrix} \qquad f_4:\begin{pmatrix} a & b & c \cr b & b & a \end{pmatrix}. $$ \end{exa} \begin{thm}\label{thm:number_of_functions_and_injections}Let $A$, $B$ be finite sets with $\card{A} = n$ and $\card{B} = m$. Then \begin{itemize} \item the number of functions from $A$ to $B$ is $m^n$. \item if $n \leq m$, the number of injective functions from $A$ to $B$ is $m(m-1)(m-2)\cdots (m-n+1)$. If $n>m$ there are no injective functions from $A$ to $B$. \end{itemize} \end{thm} \begin{pf} Each of the $n$ elements of $A$ must be assigned an element of $B$, and hence there are $\underbrace{m\cdot m \cdots m}_{n\ \mathrm{factors}} = m^n$ possibilities, and thus $m^n$ functions.If a function from $A$ to $B$ is injective then we must have $n \leq m$ in view of Theorem \ref{thm:size_domain_image_injections_surjections}. If to different inputs we must assign different outputs then to the first element of $A$ we may assign any of the $m$ elements of $B$, to the second any of the $m-1$ remaining ones, to the third any of the $m-2$ remaining ones, etc., and so we have $m(m-1)\cdots (m-n+1)$ injective functions. \end{pf} \begin{exa} Let $A = \{a, b, c\}$ and $B = \{1,2, 3, 4\}$. Then according to Theorem \ref{thm:number_of_functions_and_injections}, there are $4^3 = 64$ functions from $A$ to $B$ and of these, $4\cdot 3 \cdot 2 = 24$ are injective. Similarly, there are $3^4 = 81$ functions from $B$ to $A$, and none are injective. \end{exa} \begin{exa}\label{exa:number_of_surjections} Find the number of surjections from $A=\{a, b, c, d\}$ to $B=\{1,2,3\}$. \end{exa}Solution: The trick here is that we know how to count the number of functions from one finite set to the other (Theorem \ref{thm:number_of_functions_and_injections}). What we do is over count the number of functions, and then sieve out those which are not surjective by means of Inclusion-Exclusion. By Theorem \ref{thm:number_of_functions_and_injections}, there are $3^4=81$ functions from $A$ to $B$. There are $\binom{3}{1}2^4=48$ functions from $A$ to $B$ that miss one element from $B$. There are $\binom{3}{2}1^4 = 3$ functions from $A$ to $B$ that miss two elements from $B$. There are $\binom{3}{0}0^4=4$ functions from $A$ to $B$ that miss three elements from $B$. By Inclusion-Exclusion there are $$81-48+3 = 36 $$surjective functions from $A$ to $B$. \bigskip In analogy to example \ref{exa:number_of_surjections}, we may prove the following theorem, which complements Theorem \ref{thm:number_of_functions_and_injections} by finding the number of surjections from one set to another set. \begin{thm} Let $A$ and $B$ be two finite sets with $\card{A} = n$ and $\card{B} = m$. If $n< m$ then there are no surjections from $A$ to $B$. If $n \geq m$ then the number of surjective functions from $A$ to $B$ is $$m^n - \binom{m}{1}(m-1)^n + \binom{m}{2}(m-2)^n - \binom{m}{3}(m-3)^n + \cdots + (-1)^{m-1}\binom{m}{m-1}(1)^{n}. $$ \end{thm} \chapter{Number Theory} \Opensolutionfile{discans}[discansC4] \section{Division Algorithm} \begin{df} If $a \neq 0, b$ are integers, we say that $a$ {\em divides} $b$ if there is an integer $c$ such that $ac = b.$ We write this as $a|b.$ \end{df} If $a$ does not divide $b$ we write $a\not |b.$ \begin{exa} Since $20 = 4\cdot 5$ we have $4|20$. Also $-4|20$ since $20 = (-4)(-5)$. \end{exa} \begin{thm} Let $a, b, c$ be integers. \begin{dingautolist}{202} \item If $a|b$ then $a|kb$ for any $k\in\BBZ$. \item If $a|b$ and $b|a$, then $a= \pm b$. \item If $a|b$ and $b|c$ then $a|c$. \item If $c$ divides $a$ and $b$ then $c$ divides any linear combination of $a$ and $b$. That is, if $a, b, c, m, n$ are integers with $c|a, c|b$, then $c|(am + nb)$. \item For any $k\in\BBZ\setminus \{0\}$, $a|b \iff ka|kb$. \item If $a|b$ and $b \neq 0$ then $1 \leq |a| \leq |b|.$ \end{dingautolist} \end{thm} \begin{pf} We prove the assertions in the given order. \begin{dingautolist}{202} \item There is $u\in\BBZ$ such that $au=b$. Then $a(uk) = bk$ and so $a|bk$. \item Observe that by definition, neither $a\neq 0$ nor $b \neq 0$ if $a|b$ and $b|a$. There exist integers $u, u'$ with $au = b$ and $bu' = a$. Hence $auu' = bu' = a$, and so $uu'=1$. Since $u, u'$ are integers, then $u = \pm 1, u' = \mp 1$. Hence $a = \pm b$. \item There are integers $u, v$ with $au = b, bv = c.$ Hence $auv = c$, and so $a|c$. \item There are integers $s, t$ with $sc = a, tc = b$. Thus $$am + nb = c(sm + tn), $$giving $c|(am + bn).$ \item There exist an integer $u$ with $au = b$. Then $(ak)u = kb$, and so $a|b \implies ka|kb$. Since $k\neq 0$ we may cancel out the $k$'s and hence $(ak)u = kb \implies au = b \implies a|b$, proving the converse. \item Since $b\neq 0$ there exists an integer $u \neq 0$ with $au = b$. So $|u| \geq 1$ and thus $|a|\cdot 1 \leq |a|\cdot |u| = |au| = |b|$. $|a| \geq 1$ trivially. \end{dingautolist} \end{pf} \begin{thm}[Division Algorithm] Let $n > 0$ be an integer. Then for any integer $a$ there exist unique integers $q$ (called the {\em quotient}) and $r$ (called the {\em remainder}) such that $a = qn + r$ and $0 \leq r < q$. \label{thm:division_algorithm} \end{thm} \begin{pf} In the proof of this theorem, we use the following property of the integers, called the {\em well-ordering principle}: any non-empty set of non-negative integers has a smallest element. \bigskip Consider the set $S = \{ a -bn: b\in \BBZ$ and $a \geq bn\}$. Then $S$ is a collection of nonnegative integers and $S \neq \varnothing$ as $\pm a - 0\cdot n \in S$ and this is non-negative for one choice of sign. By the Well-Ordering Principle, $S $ has a least element, say $r$. Now, there must be some $q \in \BBZ$ such that $r = a - qn$ since $r \in S $. By construction, $r \geq 0.$ Let us prove that $r < n$. For assume that $r \geq n.$ Then $r > r - n = a - qn - n = a - (q + 1)n \geq 0$, since $r - n \geq 0.$ But then $a - (q + 1)n \in S $ and $a - (q + 1)n < r$ which contradicts the fact that $r$ is the smallest member of $S $. Thus we must have $0 \leq r < n.$ To prove that $r$ and $q$ are unique, assume that $q_1n + r_1 = a = q_2n + r_2$, $0 \leq r_1 < n$, $0 \leq r_2 < n. $ Then $r_2 - r_1 = n(q_1 - q_2)$, that is, $n$ divides $(r_2 - r_1)$. But $|r_2 - r_1| < n,$ whence $r_2 = r_1$. From this it also follows that $q_1 = q_2.$ This completes the proof. \end{pf} \begin{exa} If $n = 5$ the Division Algorithm says that we can arrange all the integers in five columns as follows: $$\begin{array}{rrrrr} \vdots & \vdots & \vdots & \vdots & \vdots \\ -10 & -9 & -8 & -7 & -6 \\ -5 & -4 & -3 & -2 & -1 \\ 0 & 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 & 9 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \end{array}$$ The arrangement above shews that any integer comes in one of $5$ flavours: those leaving remainder $0$ upon division by $5$, those leaving remainder $1$ upon division by $5$, etc. We let $$5\BBZ = \{\ldots, -15, -10, -5, 0 , 5, 10, 15, \ldots\} = \overline{0},$$ $$5\BBZ + 1 = \{\ldots, -14, -9, -4, 1 , 6, 11, 16, \ldots\} = \overline{1},$$ $$5\BBZ + 2= \{\ldots, -13, -8, -3, 2 , 7, 12, 17, \ldots\} = \overline{2},$$ $$5\BBZ + 3= \{\ldots, -12, -7, -2, 3 , 8, 13, 18, \ldots\}=\overline{3},$$ $$5\BBZ + 4 = \{\ldots, -11, -6, -1, 4 , 9, 14, 19, \ldots\}=\overline{4},$$ and $$\BBZ_5 = \{\overline{0}, \overline{1}, \overline{2}, \overline{3}, \overline{4} \}.$$ \end{exa} \begin{exa} Shew that $n^2 + 23$ is divisible by $24$ for infinitely many values of $n$. \end{exa} Solution: Observe that $n^2 + 23 = n^2 - 1 + 24 = (n - 1)(n + 1) + 24$. Therefore the families of integers $n = 24m \pm 1, m = 0, \pm 1, \pm 2, \pm 3, \ldots$ produce infinitely many values such that $n^2 + 23$ is divisible by 24. \begin{exa} Shew that the square of any prime greater than $3$ leaves remainder $1$ upon division by $12.$\end{exa} Solution: If $p > 3$ is prime, then $p$ is of one of the forms $6k \pm 1$. Now, $$(6k \pm 1)^2 = 12(3k^2 \pm k) + 1,$$ proving the assertion. \begin{exa} Prove that if $p$ is a prime, then one of $8p - 1$ and $8p + 1$ is a prime and the other is composite. \end{exa} Solution: If $p = 3, \ 8p - 1 = 23$ and $8p + 1 = 25,$ then the assertion is true for $p = 3$. If $p > 3$, then either $p = 3k + 1$ or $p = 3k + 2.$ If $p = 3k + 1, \ 8p - 1 = 24k - 7$ and $8p + 1 = 24k - 6,$ which is divisible by 6 and hence not prime. If $p = 3k + 2, \ 8p - 1 = 24k - 15$ is not a prime, . \begin{exa}[AHSME 1976] Let $r$ be the common remainder when $1059, 1417$ and $2312$ are divided by $d > 1.$ Find $d - r$. \end{exa} Solution: By the division algorithm there are integers $q_1, q_2, q_3$ with $1059 = dq_1 + r, 1417 = dq_2 + r$ and $2312 = dq_3 + r$. Subtracting we get $1253 = d(q_3 - q_1), 895 = d(q_3 - q_2)$ and $358 = d(q_2 - q_1)$. Notice that $d$ is a common divisor of $1253, 895,$ and $358$. As $1253 = 7\cdot 179,\ $ $895 = 5 \cdot 179,$ and $358 = 2\cdot 179$, we see that 179 is the common divisor greater than 1 of all three quantities, and so $d = 179.$ Since $1059 = 179q_1 + r,$ and $1059 = 5\cdot 179 + 164,$ we deduce that $r = 164.$ Finally, $d - r = 15.$ \begin{exa} Shew that if $3n + 1$ is a square, then $n + 1$ is the sum of three squares. \end{exa} Solution: Clearly $3n + 1$ is not a multiple of 3, and so $3n + 1 = (3k \pm 1)^2$. Therefore $$n + 1 = \frac{(3k \pm 1)^2 - 1}{3} + 1 = 3k^2 \pm 2k + 1 = k^2 + k^2 + (k \pm 1)^2,$$ as we wanted to shew. \section{Greatest Common Divisor} \begin{df} Let $a$, $b$ be integers with one of them different from $0$. The greatest common divisor $d$ of $a, b$, denoted by $d = \gcd(a, b)$ is the largest positive integer that divides both $a$ and $b$. \end{df} \begin{thm}[Bachet-Bezout Theorem] The greatest common divisor of any two integers $a, b$ can be written as a linear combination of $a$ and $b$, i.e., there are integers $x, y$ with $$ \gcd(a, b) = ax + by.$$ \index{greatest common divisor} \label{thm:bachet_bezout} \index{theorem!Bachet-Bezout} \end{thm} \begin{pf} Let $A = \{ ax + by| ax + by > 0, x, y \in \BBZ\}$. Clearly one of $\pm a, \pm b$ is in $A$, as both $a, b$ are not zero. By the Well Ordering Principle, $A$ has a smallest element, say $d$. Therefore, there are $x_0, y_0$ such that $d = ax_0 + by_0.$ We prove that $d = \gcd(a, b).$ To do this we prove that $d$ divides $a$ and $b$ and that if $t$ divides $a$ and $b$, then $t$ must also divide then $d$. \bigskip We first prove that $d$ divides $a.$ By the Division Algorithm, we can find integers $q, r, 0 \leq r < d$ such that $a = dq + r.$ Then $$ r = a - dq = a(1 - qx_0) - by_0.$$If $r > 0,$ then $r \in A$ is smaller than the smaller element of $A$, namely $d,$ a contradiction. Thus $r = 0.$ This entails $dq = a,$ i.e. $d$ divides $a.$ We can similarly prove that $d$ divides $b.$ \bigskip Assume that $t$ divides $a$ and $b$. Then $a = tm, b = tn$ for integers $m, n.$ Hence $d = ax_0 + bx_0 = t(mx_0 + ny_0),$ that is, $t$ divides $d.$ The theorem is thus proved. \end{pf} Let $a, b$ be positive integers. After using the Division Algorithm repeatedly, we find the sequence of equalities \begin{equation} \begin{array}{lcll} a & = & bq_1 + r_2, & 0 < r_2 < b, \\ b & = & r_2q_2 + r_3 & 0 < r_3 < r_2, \\ r_2 & = & r_3q_3 + r_4 & 0 < r_4 < r_3, \\ \vdots & \vdots & \vdots & \vdots \\ r_{n - 2} & = & r_{n - 1}q_{n - 1} + r_n & 0 < r_n < r_{n - 1}, \\ r_{n - 1} & = & r_nq_n. & \\ \end{array} \label{eq:remainders_euclid}\end{equation} The sequence of remainders will eventually reach a $r_{n + 1}$ which will be zero, since $b, r_2 , r_3, \ldots$ is a monotonically decreasing sequence of integers, and cannot contain more than $b$ positive terms. The Euclidean Algorithm rests on the fact, to be proved below, that $\gcd(a, b) = \gcd(b, r_2) = \gcd(r_2, r_3) = \cdots = \gcd(r_{n - 1}, r_n) = r_n.$ \begin{thm} If $r_n$ is the last non-zero remainder found in the process of the Euclidean Algorithm, then $$ r_n = \gcd(a, b).$$\end{thm} \begin{pf} From equations \ref{eq:remainders_euclid} $$ \begin{array}{lcl} r_2 & = & a - bq_1 \\ r_3 & = & b - r_2q_2 \\ r_4 & = & r_2 - r_3q_3 \\ \vdots & \vdots & \vdots \\ r_{n} & = & r_{n - 2} - r_{n - 1}q_{n - 1} \\ \end{array}$$ Let $r = \gcd(a, b)$. From the first equation, $r|r_2.$ From the second equation, $r|r_3.$ Upon iterating the process, we see that $r|r_n.$ But starting at the last equation \ref{eq:remainders_euclid} and working up, we see that $r_n|r_{n - 1}, r_n|r_{n - 2}, \ldots r_n|r_2, r_n|b, r_n|a$. Thus $r_n$ is a common divisor of $a$ and $b$ and so $r_n|\gcd(a, b).$ This gives the desired result. \end{pf} \begin{exa} Write pseudocode describing the Euclidean Algorithm. \end{exa} Solution: Here is one iterative way of doing this. \bcp[Ovalbox]{EuclideanAlgorithm}{x,y} \IF x<0 \THEN x \GETS -x \\ \IF y<0 \THEN y \GETS -y \\ \WHILE y>0 \DO \BEGIN r \GETS x \mod y \\ x \GETS y \\ y \GETS r \END \ecp \begin{exa} Find $\gcd(23, 29)$ by means of the Euclidean Algorithm.\end{exa} Solution: We have $$ 29 = 1\cdot 23 + 6,$$ $$ 23 = 3\cdot 6 + 5,$$ $$ 6 = 1\cdot 5 + 1,$$ $$ 5 = 5\cdot 1. $$The last non-zero remainder is 1, thus $\gcd(23, 29) = 1.$ \bigskip An equation which requires integer solutions is called a {\em diophantine equation}. By the Bachet-Bezout Theorem \ref{thm:bachet_bezout}, we see that the linear diophantine equation $$ ax + by = c$$has a solution in integers if and only if $\gcd(a, b)|c.$ The Euclidean Algorithm is an efficient means to find a solution to this equation. \begin{exa}\label{exa:line_dio_1} Find integers $x, y$ that satisfy the linear diophantine equation $$ 23x + 29y = 1.$$ \end{exa} Solution: We work upwards, starting from the penultimate equality in the preceding problem: $$ 1 = 6 - 1\cdot 5,$$ $$ 5 = 23 - 3 \cdot 6,$$ $$ 6 = 29\cdot 1 - 23.$$ Hence, $$ \begin{array}{lcl} 1 & = & 6 - 1\cdot 5 \\ & = & 6 - 1\cdot (23 - 3\cdot 6) \\ & = & 4\cdot 6 - 1\cdot 23 \\ & = & 4(29\cdot 1 - 23) - 1\cdot 23 \\ & = & 4\cdot 29 - 5\cdot 23. \end{array}$$This solves the equation, with $x = - 5, y = 4.$ \begin{exa} Find integer solutions to $$23x + 29y = 7.$$\end{exa} Solution: From the preceding example, $23(-5) + 29(4) = 1$. Multiplying both sides of this equality by 7, $$ 23(-35) + 29(28) = 7,$$which solves the problem. \begin{exa} Find infinitely many integer solutions to $$ 23x + 29y = 1.$$ \end{exa} Solution: By example \ref{exa:line_dio_1}, the pair $x_0 = -5, y_0 = 4$ is a solution. We can find a family of solutions by letting $$ x = -5 + 29t, \ y = 4 - 23t, \ \ t \in \BBZ.$$ \begin{exa} Can you find integers x, y such that $3456x + 246y = 73$?\end{exa} Solution: No. $(3456, 246) = 2$ and $2\not |73.$ \section{Non-decimal Scales} The fact that most people have ten fingers has fixed our scale of notation to the decimal. Given any positive integer $r > 1$, we can, however, express any number $x$ in base $r$. If $n$ is a positive integer, and $r > 1$ is an integer, then $n$ has the base-$r$ representation $$n = a_0 + a_1r + a_2r^2 + \cdots + a_kr^k, \ 0 \leq a_t \leq r - 1, \ a_k \neq 0, \ r^k \leq n < r^{k + 1}.$$ We use the convention that we shall refer to a decimal number without referring to its base, and to a base-$r$ number by using the subindex $_r$. \begin{exa} Express the decimal number $5213$ in base-seven. \end{exa} Solution: Observe that $5213 < 7^5.$ We thus want to find $0 \leq a_0, \ldots , a_4 \leq 6, a_4 \neq 0$ such that $$5213 = a_47^4 + a_37^3 + a_27^2 + a_17 + a_0.$$Dividing by $7^4$, we obtain $2 + $ proper fraction $= a_4 + $ proper fraction. This means that $a_4 = 2.$ Thus $5213 = 2\cdot7^4 + a_37^3 + a_27^2 + a_17 + a_0$ or $411 = 5213 = a_37^3 + a_27^2 + a_17 + a_0$. Dividing by $7^3$ this last equality we obtain $1 + $ proper fraction $= a_3 + $ proper fraction, and so $a_3 = 1.$ Continuing in this way we deduce that $5213 = 21125_7.$ The method of successive divisions used in the preceding problem can be conveniently displayed as \begin{center} \begin{tabular}{l|l|l} 7 & 5212 & 5 \\ \hline 7 & 744 & 2 \\ \hline 7 & 106 & 1 \\ \hline 7 & 15 & 1 \\ \hline 7 & 2 & 2 \\ \end{tabular} \end{center} The central column contains the successive quotients and the rightmost column contains the corresponding remainders. Reading from the last remainder up, we recover $5213 = 21125_7.$ \begin{exa} Write $562_7$ in base-five. \end{exa} Solution: $562_7 = 5\cdot 7^2 + 6\cdot 7 + 2 = $ in decimal scale, so the problem reduces to convert $289$ to base-five. Doing successive divisions, \begin{center} \begin{tabular}{l|l|l} 5 & 289 & 4 \\ \hline 5 & 57 & 2 \\ \hline 5 & 11 & 1 \\ \hline 5 & 2 & 2 \\ \end{tabular} \end{center} Thus $562_7 = 289 = 2124_5.$ \begin{exa} Express the fraction $\dis{\frac{13}{16}}$ in base-six. \end{exa} Solution: Write $$\frac{13}{16} = \frac{a_1}{6} + \frac{a_2}{6^2} + \frac{a_3}{6^3} + \frac{a_4}{6^4} + \cdots $$ Multiplying by 6, we obtain $4 + $ proper fraction $ = a_1 + $ proper fraction, so $a_1 = 4.$ Hence $$\frac{13}{16} - \frac{4}{6} = \frac{7}{48} = \frac{a_2}{6^2} + \frac{a_3}{6^3} + \frac{a_4}{6^4} + \cdots $$ Multiply by $6^2$ we obtain $5 + $ proper fraction $= a_2 + $ proper fraction, and so $a_2 = 5.$ Continuing in this fashion $$\frac{13}{16} = \frac{4}{6} + \frac{5}{6^2} + \frac{1}{6^3} + \frac{3}{6^4} = 0.4513_6.$$ We may simplify this procedure of successive multiplications by recurring to the following display: \renewcommand{\arraystretch}{2} $$ \begin{array}{l|l|l} 6 & \frac{13}{16} & 4 \\ \hline 6 & \frac{7}{8} & 5 \\ \hline 6 & \frac{1}{4} & 1 \\ \hline 6 & \frac{1}{2} & 3 \\ \end{array} $$ The third column contains the integral part of the products of the first column and the second column. Each term of the second column from the second on is the fractional part of the product obtained in the preceding row. Thus $6\cdot\frac{13}{16} - 4 = \frac{7}{8}$, $6\cdot\frac{7}{8} - 5 = \frac{1}{4}$, etc.. \begin{exa} Prove that $4.41_r$ is a perfect square in any scale of notation. \end{exa} Solution: $$4.41_r = 4 + \frac{4}{r} + \frac{4}{r^2} = \left(2 + \frac{1}{r}\right)^2$$ \begin{exa}[AIME 1986] The increasing sequence $$1, 3, 4, 9, 10, 12, 13, \ldots$$consists of all those positive integers which are powers of $3$ or sums of distinct powers or $3$. Find the hundredth term of the sequence. \end{exa} Solution: If the terms of the sequence are written in base-three, they comprise the positive integers which do not contain the digit 2. Thus the terms of the sequence in ascending order are $$1_3, 10_3, 11_3, 100_3, 101_3, 110_3, 111_3, \ldots$$In the {\em binary} scale these numbers are, of course, the ascending natural numbers $1, 2, 3, 4, \ldots$. Therefore to obtain the 100th term of the sequence we write 100 in binary and then translate this into ternary: $100 = 1100100_2$ and $1100100_3 = 3^6 + 3^5 + 3^2 = 981.$ \section{Congruences} \begin{df} Let $n > 0$ be an integer. We say that ``$a$ is congruent to $b$ modulo $n$'' written $a \equiv b\mod n$ if $a$ and $b$ leave the same remainder upon division by $n$. \end{df} \begin{exa} $$-8 \equiv 6 \mod 7,$$ $$ -8 \equiv 13 \mod 7.$$ \end{exa} \bigskip By the division algorithm any integer $a$ can be written as $a = qn + r$ with $0 \leq r < n$. By letting $q$ vary over the integers we obtain the arithmetic progression $$, \ldots, r-3n , r -2n, r - n, r, r + n, r + 2n , r + 3n, \ldots, $$and so all the numbers in this sequence are congruent to $a$ modulo $n$. \begin{thm} Let $n >0$ be an integer. Then $a \equiv b \mod n \iff n|(a-b)$. \end{thm} \begin{pf} Assume $a\neq b$, otherwise the result is clear. By the Euclidean Algorithm there are integers $q_1 \neq q_2$ such that $a = q_1n+ r$ and $b = q_2n + r$, as $a$ and $b$ leave the same remainder when divided by $n$. Thus $a-b = q_1n - q_2n = (q_1 - q_2)n$. This implies that $n|(a-b)$. \bigskip Conversely if $n|(a-b)$ then there is an integer $t$ such that $nt = a - b$. Assume that $a = m_1n+ r_1$ and $b = m_2n + r_2$ with $0 \leq r_1, r_2 < n$. Then $$nt = a-b = (m_1-m_2)n + r_1-r_2 \implies n(t - m_1+m_2) = r_1 -r_2 \implies n|(r_1-r_2). $$ Since $|r_1-r_2|0$, for if $n<0$ we simply apply the result to $-n>0$. Since $10^k \equiv 0 \mod 5$ for integral $k \geq 1$, we have $$n = a_s10^s + a_{s-1}10^{s-1} + \cdots + a_110 + a_0 \equiv a_0 \mod 5, $$Thus divisibility of $n$ by $5$ depends on whether $a_0$ is divisible by $5$, which happens only when $a_0 = 0$ or $a_0 = 5$. \end{pf} \begin{thm} Let $k$ be a positive integer. An integer $n$ is divisible by $2^k$ if and only if the number formed by the last $k$ digits of $n$ is divisible by $2^k$. \end{thm} \begin{pf} If $n = 0$ there is nothing to prove. If we prove the result for $n > 0$ then we can deduce the result for $n < 0$ by applying it to $-n = (-1)n > 0$. So assume that $n\in\BBZ$, $n > 0$ and let its decimal expansion be $$n = a_s10^s + a_{s-1}10^{s-1} + \cdots + a_110 + a_0, $$where $0 \leq a_i \leq 9, \ a_s \neq 0$. Now, each of $10^t = 2^t5^t\equiv 0 \mod 2^t$ for $t \geq k$. Hence $$\begin{array}{lll}n & = & a_s10^s + a_{s-1}10^{s-1} + \cdots + a_110 + a_0\\ & \equiv & a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + \cdots + a_110 + a_0 \mod 2^k, \end{array}$$ so $n$ is divisible by $2^k$ if and only if the number formed by the last $k$ digits of $n$ is divisible by $2^k$. \end{pf} \begin{exa} The number $987654888$ is divisible by $2^3 = 8$ because the number formed by its last three digits, $888$ is divisible by $8$. \end{exa} \begin{exa} The number $191919191919193216$ is divisible by $2^4 = 16$ because the number formed by its last four digits, $3216$ is divisible by $16$. \end{exa} \begin{exa} By what digits may one replace $A$ so that the integer $231A2$ be divisible by $4$? \end{exa} Solution: The number $231A2$ is divisible by $4$ if and only if $A2$ is divisible by $4$. This happens when $A = 1$ ($A2 = 12$), $A = 3$ ($A2 = 32$), $A = 5$ ($A2 = 52$), $A = 7$ ($A2 = 72$), and $A = 9$ ($A2 = 92$). Thus the five numbers $$23112, 23132, 23152 23172, 23192, $$are all divisible by $4$. \begin{exa} Determine digits $a, b$ so that $235ab$ be divisible by $40$. \end{exa} Solution: $235ab$ will be divisible by $40$ if and only if it is divisible by $8$ and by $5$. If $235ab$ is divisible by $8$ then, {\em a fortiori}, it is even and since we also require it to be divisible by $5$ we must have $b = 0$. Thus we need a digit $a$ so that $5a0$ be divisible by $8$. Since $0 \leq a \leq 9$, a quick trial an error gives that the desired integers are $$23500, 23520, 23540, 23560, 23580. $$ \begin{thm}[Casting-out $9$'s] \label{thm:casting_out_9s}An integer $n$ is divisible by $9$ if and only if the sum of its digits is divisible by $9$. \end{thm} \begin{pf} If $n = 0$ there is nothing to prove. If we prove the result for $n > 0$ then we can deduce the result for $n < 0$ by applying it to $-n = (-1)n > 0$. So assume that $n\in\BBZ$, $n > 0$ and let its decimal expansion be $$n = a_s10^s + a_{s-1}10^{s-1} + \cdots + a_110 + a_0, $$where $0 \leq a_i \leq 9, \ a_s \neq 0$. Observe that $10 \equiv 1 \mod 9$ and so $10^t \equiv 1^t \equiv 1 \mod 9$. Now $$\begin{array}{lll}n & = & a_s10^s + a_{s-1}10^{s-1} + \cdots + a_110 + a_0\\ & \equiv & a_{s} + \cdots + a_1+a_0 \mod 9, \end{array}$$from where the result follows. \end{pf} \begin{rem} Since $10\equiv 1 \mod 3$ we can also deduce that integer $n$ is divisible by $3$ if and only if the sum of it digits is divisible by $3$. \end{rem} \begin{exa} What values should the digit $d$ take so that the number $32d5$ be divisible by $9$? \end{exa} Solution: The number $32d5$ is divisible by $9$ if and only $3+2+d+5 = d + 10$ is divisible by $9$. Now, $$0 \leq d \leq 9 \implies 10 \leq d + 10 \leq 19.$$The only number in the range $10$ to $19$ divisible by $9$ is $18$, thus $d=8$. One can easily verify that $3285$ is divisible by $9$. \begin{exa} Is there a digit $d$ so that $125d$ be divisible by $45$? \end{exa} Solution: If $125d$ were divisible by $45$, it must be divisible by $9$ and by $5$. If it were divisible by $5$, then $d = 0$ or $d = 5$. If $d = 0$, the digital sum is $1 +2 +5 + 0 = 8$, which is not divisible by $9$. Similarly, if $d = 5$, the digital sum is $1 +2 +5 + 5 = 13$, which is neither divisible by $9$. So $125d$ is never divisible by $45$. \begin{df} If the positive integer $n$ has decimal expansion $$n = a_s10^s + a_{s-1}10^{s-1} + \cdots + a_110 + a_0, $$the {\em alternating digital sum} of $n$ is $$a_s - a_{s-1} +a_{s-2}-a_{s-3}+ \cdots + (-1)^{s-1}a_0 $$ \end{df} \begin{exa} The alternating digital sum of $135456$ is $$1-3+5-4+5-6=-2. $$ \end{exa} \begin{thm} An integer $n$ is divisible by $11$ if and only if its alternating digital sum is divisible by $11$. \end{thm} \begin{pf} We may assume that $n>0$. Let $$n = a_s10^s + a_{s-1}10^{s-1} + \cdots + a_110 + a_0, $$where $0 \leq a_i \leq 9, \ a_s \neq 0$. Observe that $10 \equiv -1 \mod 11$and so $10^t \equiv (-1) \mod 11$. Hence $$\begin{array}{lll}n & = & a_s10^s + a_{s-1}10^{s-1} + \cdots + a_110 + a_0\\ & \equiv & a_s(-1)^s + a_{s-1}(-1)^{s-1} + a_{s-2}(-1)^{s-2} +\cdots + -a_1 + a_0 \mod 11 \end{array}$$and the result follows from this. \end{pf} \begin{exa} $912282219$ has alternating digital sum $9 - 1 + 2 - 2 + 8 - 2 + 2 - 1 + 9 = 24 $ and so $912282219$ is not divisible by $11$, whereas $8924310064539$ has alternating digital sum $ 8 - 9 + 2 - 4 + 3 - 1 + 0 - 0 + 6 - 4 + 4 - 3 + 9 = 11$, and so $8924310064539$ is divisible by $11$. \end{exa} \section*{Homework}\addcontentsline{toc}{section}{Homework}\markright{Homework} \begin{pro} Prove that there are infinitely many integers $n$ such that $4n^2 + 1$ is simultaneously divisible by $13$ and $5$. \begin{answer4} We have $4n^2+1 = 4n^2-64 + 65 = 4(n-4)(n+4) + 65$ so it is enough to take $n = 65k \pm 4$. \end{answer4} \end{pro} \begin{pro} Find the least positive integer solution of the equation $436x - 393y = 5$. \begin{answer4} Using the Euclidean Algorithm, $$\begin{array}{lll} 436 & = & 1\cdot 393 + 43 \\ 393 & = & 9\cdot 43 + 6\\ 43 & = & 7\cdot 6 + 1 \end{array}$$ Hence $$ \begin{array}{lll} 1 & = & 43 - 7\cdot 6 \\ & = & 43 - 7\cdot (393 - 9 \cdot 43)\\ & = & -7\cdot 393 +64 \cdot 43\\ & = & -7\cdot 393 +64 \cdot (436 - 393) \\ & = & -71\cdot 393 + 64 \cdot 436,\\ \end{array}$$ and so $5 = 320\cdot 436 -355\cdot 393 $. An infinite set of solutions can be achieved by putting $x = 320 + 393t$, $y = 355 + 436t$. \end{answer4} \end{pro} \begin{pro} Two rods of equal length are divided into $250$ and $243$ equal parts, respectively. If their ends be coincident, find the divisions which are the nearest together. \begin{answer4} Observe that $\gcd(243, 250) = 1$, and so the divisions will be nearest together when they differ by the least amount, that is, we seek solutions of $243x - 250y = \pm 1$. By using the Euclidean Algorithm we find $243\cdot 107 - 250\cdot 104 = 1$ and also $243\cdot (250-107) - 250\cdot (243-104) = -1$ and so the values of $x$ are $107$ and $143$ and those of $y$ are $104$ and $139$. \end{answer4} \end{pro} \begin{pro} Prove that any integer $n > 11$ is the sum of two positive composite numbers. \begin{answer4} If $n> 11$ is even then $n - 6$ is even and at least $12-4 = 8$ and thus it is composite. Hence $n = (n-6) + 6$ is the sum of two even composite numbers. If $n > 11$ is odd then $n - 9$ is even at least $13-9 = 4$, and hence composite. Therefore $n = (n-9) + 9$ of an even and an odd composite number. \end{answer4} \end{pro} \begin{pro} Let $n>1$ be an integer. \begin{enumerate} \item Prove, using induction or otherwise, that if $a \neq 1$ then $$1 + a + a^2 + \cdots a^{n-1} = \dfrac{1 - a^{n}}{1 -a}. $$ \item By making the substitution $a = \frac{x}{y}$ prove that $$x^n - y^n = (x-y)(x^{n-1} + x^{n-2}y + \cdots + xy^{n-2} + y^{n-1}). $$ \item Deduce that if $x\neq y$ are integers then $(x-y)|x^n - y^n$. \item Shew that $$ 2903^n - 803^n - 464^n + 261^n$$ is divisible by $1897$ for all natural numbers $n$. \item Prove that if $2^n-1$ is prime, then $n$ must be prime. \item Deduce that if $x\neq y$ are integers, and $n$ is odd, then $(x+y)|x^n + y^n$. \item Prove that if $2^n + 1$ is prime, then $n = 2^k$ for some integer $k$. \end{enumerate} \begin{answer4} \begin{enumerate} \item Put $S = 1 + a + a^2 + \cdots + a^{n-1}.$ Then $aS = a + a^2 + \cdots + a^{n-1} + a^n.$ Thus $S - aS = (1 + a + a^2 + \cdots +a^{n-1}) - (a + a^2 + \cdots + a^{n-1} + a^n) = 1 - a^n,$ and from $(1-a)S = S-aS=1 - a^n $ we obtain the result. \item From $$1 + \frac{x}{y} + \left(\frac{x}{y}\right)^2 + \cdots + \left(\frac{x}{y}\right)^{n-1} = \dfrac{1- \left(\frac{x}{y}\right)^n}{1-\frac{x}{y}} $$ we obtain $$\left(1-\frac{x}{y}\right)\left(1 + \frac{x}{y} + \left(\frac{x}{y}\right)^2 + \cdots + \left(\frac{x}{y}\right)^{n-1}\right) = 1- \left(\frac{x}{y}\right)^n, $$and multiplying by $y^n$ both sides gives the result. \item This is immediate from the above result. \item By the preceding part, $2903^n - 803^n$ is divisible by $2903 - 803 = 2100 = 7\cdot 300 = $, and $261^n - 464^n$ is divisible by $261 - 464 = -203 = 7\cdot (-29)$. Thus the expression $2903^n - 803^n - 464^n + 261^n$ is divisible by $7$. Also, $2903^n - 464^n$ is divisible by $2903 - 464 = 9\cdot 271$ and $261^n - 803^n$ is divisible by $-542 = (-2)271$. Thus the expression is also divisible by $271$. Since $7$ and $271$ have no prime factors in common, we can conclude that the expression is divisible by $7\cdot 271 = 1897.$ \item We have $$2^n - 1 = 2^{ab} - 1 = (2 ^a - 1)((2^a)^{b - 1} + (2^a)^{b - 2} + \cdots + (2^a)^1 + 1).$$Since $a > 1, 2^a - 1 > 1.$ Since $b > 1$, $$(2^a)^{b - 1} + (2^a)^{b - 2} + \cdots (2^a)^1 + 1) \geq 2^a + 1 > 1.$$ We have decomposed a prime number (the left hand side) into the product of two factors, each greater than 1, a contradiction. Thus $n$ must be a prime. Primes of this form are called {\em Mersenne primes.} \item For every $n$ we have that $x - y$ divides $x^n - y^n$. By changing $y$ into $-y$ we deduce that $x - (-y)$ divides $x^n - (-y)^n$, that is $x + y$ divides $x^n - (-y)^n$. If $n$ is odd then $-(-y)^n = y^n$, which gives the result. \item We have $$2^n + 1 = 2^{2^km} + 1 = (2 ^{2^k} + 1)((2^{2^k})^{m - 1} - (2^{2^k})^{m - 2} + \cdots - (2^{2^k})^1 + 1).$$Clearly, $2 ^{2^k} + 1 > 1.$ Also if $m \geq 3$ $$(2^{2^k})^{m - 1} - (2^{2^k})^{m - 2} + \cdots - (2^{2^k})^1 + 1 \geq (2^{2^k})^2 - (2^{2^k})^1 + 1 > 1,$$and so, we have produced two factors each greater than 1 for the prime $2^n + 1$, which is nonsense. Primes of this form are called {\em Fermat primes.} \end{enumerate} \end{answer4} \end{pro} \begin{pro} Use the preceding problem to find the prime factor $p > 250000$ of the integer $$1002004008016032.$$ \begin{answer4} If $a = 10^3 , b = 2$ then $$ 1002004008016032 = a^5 + a^4 b + a^3 b^2 + a^2 b^3 + ab^4 + b^5 = \dfrac{ a^6 - b^6 }{ a - b }. $$ This last expression factorises as $$ {\everymath{\displaystyle} \begin{array}{lcl}\dfrac{a^6 - b^6}{a - b} & = & (a + b)(a^2 + ab + b^2)(a^2 - ab + b^2 ) \\ & = & 1002\cdot 1002004\cdot 998004 \\ & = & 4\cdot 4\cdot 1002\cdot 250501 \cdot k,\end{array} }$$where $k < 250000$. Therefore $p = 250501$. \end{answer4} \end{pro} \begin{pro} Write an algorithm that finds integer solutions $x, y$ to the equation $$\gcd(a, b) = ax + by.$$ Assume that at least one of $a$ or $b$ is different from $0$.\begin{answer4} Here a possible approach. I have put semicolons instead of writing the algorithm strictly vertically in order to save space. \bcp[Ovalbox]{LinearDiophantine}{a,b} m \GETS a; \hfill n \GETS b; \hfill p \GETS 1; \hfill q \GETS 0; \hfill r \GETS 0; \hfill s \GETS 1; \\ \WHILE \neg ((m=0) \vee (n=0)) \\ \BEGIN \IF m \geq n \THEN \BEGIN m \GETS m -n; \hfill p \GETS p - r; \hfill q \GETS q - s;\\ \END \ELSE \BEGIN n \GETS n -m; \hfill r \GETS r - p; \hfill s \GETS s - q;\\ \END \END \\ \IF m=0 \THEN \BEGIN k \GETS n; \hfill x \GETS r; \hfill y \GETS s; \\ \END \ELSE \BEGIN k \GETS m; \hfill x \GETS p; \hfill y \GETS q; \\ \END \ecp \end{answer4} \end{pro} \begin{pro} Let $A$ be a positive integer, and $A'$ be a number written with the aid of the same digits with are arranged in some other order. Prove that if $A + A' = 10^{10}$, then $A$ is divisible by $10$. \begin{answer4} Clearly $A$ and $A'$ must have ten digits. Let $A = a_{10}a_9\ldots a_1$ be the consecutive digits of $A$ and $A' = a_{10}'a' _9 \ldots a_1 '.$ Now, $A + A' = 10^{10}$ if and only if there is a $j, 0 \leq j \leq 9$ for which $a_1 + a_1' = a_2 + a_2' = \cdots = a_j + a_j' = 0, a_{j + 1} + a_{j + 1}' = 10, a_{j + 2} + a_{j + 2}' = a_{j + 3} + a_{j + 3}' = \cdots = a_{10} + a_{10}' = 9.$ Notice that $j = 0$ implies that there are no sums of the form $a_{j + k} + a_{j + k}', k \geq 2,$ and $j = 9$ implies that there are no sums of the form $a_l + a_l', 1\leq l \leq j.$ On adding all these sums, we gather $$ a_1 + a_1' + a_2 + a_2' + \cdots + a_{10} + a_{10}' = 10 + 9(9 - j).$$Since the $a_s'$ are a permutation of the $a_s$, we see that the sinistral side of the above equality is the even number $2(a_1 + a_2 + \cdots + a_{10}).$ This implies that $j$ must be odd. But this implies that $a_1 + a_1' = 0$, which gives the result. \end{answer4} \end{pro} \begin{pro} A grocer sells a 1-gallon container of milk for 79 cents (comment: those were the days!) and a half gallon container of milk for 41 cents. At the end of the day he sold \$63.58 worth of milk. How many $1$ gallon and half gallon containers did he sell? \begin{answer4}We want non-negative integer solutions to the equation $$ .79x + .41y = 63.58 \implies 79x + 41y = 6358. $$ Using the Euclidean Algorithm we find, successively $$79 = 1\cdot 41 + 38;\ \ \ 41 = 1\cdot 38 + 3;\ \ \ 38 = 3\cdot 12 + 2;\ \ \ 3 = 1\cdot 2 + 1. $$ Hence $$\begin{array}{lll} 1 & = & 3 - 2 \\ & = & 3 - (38 - 3\cdot 12) \\ & = & -38 + 3\cdot 13 \\ & = & -38 + (41- 38)\cdot 13 \\ & = & 38\cdot (-14) + 41 \cdot 13 \\ & = & (79 - 41)(-14) + 41\cdot 13 \\ & = & 79(-14) + 41(27) \end{array}$$ A solution to $79x + 41y = 1$ is thus $(x, y) = (-14, 27).$ Thus $79(-89012) + 41(171666) = 6358$ and the parametrisation $79(-89012 + 41t) + 41(171666 - 79t) = 1$ provides infinitely many solutions. We need non-negative solutions so we need, simultaneously $$ -89012 + 41t \geq 0 \implies t \geq 2172 \ \ \ \wedge \ \ \ 171666 - 79t \geq 0 \implies t \leq 2172.$$Thus taking $t = 2172$ we obtain $x = -89012 + 41(2172) = 40$ and $y = 171666 - 79(2172) = 78$, and indeed $.79(40) + .41(78) = 63.58$. \end{answer4} \end{pro} \begin{pro} Using congruences, find the last two digits of $3^{100}$. Hint: $3^{40} \equiv 1 \mod 100$. \\ \begin{answer4} Since $3^{100} \equiv (3^{40})^23^{20} \equiv 3^{20} \mod 100$, we only need to concern ourselves with the last quantity. Now (all congruences $\mod 100$) $$ 3^4 \equiv 81 \implies 3^8 \equiv 81^2 \equiv 61 \implies 3^{16} \equiv 61^2 \equiv 21. $$We deduce, as $20 = 16 + 4$, that $$ 3^{20} \equiv 3^{16}3^4 \equiv (21)(81) \equiv 1 \mod 100, $$and the last two digits are $01$. \end{answer4} \end{pro} \Closesolutionfile{discans} \section*{Answers}\addcontentsline{toc}{section}{Answers}\markright{Answers} {\small\input{discansC4}} \chapter{Enumeration} \Opensolutionfile{discans}[{discansCXenum}] \section{The Multiplication and Sum Rules} We begin our study of combinatorial methods with the following two fundamental principles. \begin{df}[Cardinality of a Set]\index{set!cardinality} If $S$ is a set, then its {\em cardinality} is the number of elements it has. We denote the cardinality of $S$ by $\card{S}$. \end{df} \begin{rul}[Sum Rule: Disjunctive Form] \label{rul:sum}Let $E_1, E_2, \ldots, E_k$, be pairwise finite disjoint sets. Then $$\card{E_1 \cup E_2 \cup \cdots \cup E_k} = \card{E_1} + \card{E_2} + \cdots + \card{E_k}. $$ \end{rul} \begin{rul}[Product Rule]\label{rul:product} Let $E_1, E_2, \ldots, E_k$, be finite sets. Then $$\card{E_1 \times E_2 \times \cdots \times E_k} = \card{E_1} \cdot \card{E_2} \cdots \card{E_k}. $$ \end{rul} \begin{exa} How many ordered pairs of integers $(x, y)$ are there such that $0< |xy| \leq 5$? \end{exa} Solution: Put $E_k = \{(x, y) \in \BBZ^2: |xy| = k\}$ for $k = 1, \ldots , 5$. Then the desired number is $$\card{E_1} + \card{E_2} + \cdots + \card{E_{5}}. $$ Then $$\begin{array}{lll}E_1 & = & \{(-1,-1), (-1, 1), (1, -1), (1,1)\} \\ E_2 & = & \{(-2,-1), (-2, 1), (-1,-2), (-1, 2), (1, -2), (1,2), (2,-1), (2,1)\} \\ E_3 & = & \{(-3,-1), (-3, 1), (-1,-3), (-1, 3), (1, -3), (1,3), (3,-1), (3,1)\} \\ E_4 & = & \{(-4,-1), (-4, 1), (-2, -2), (-2, 2), (-1,-4), (-1, 4), (1, -4), (1,4), (2,-2),(2,2), (4,-1), (4,1)\} \\ E_5 & = & \{(-5,-1), (-5, 1), (-1,-5), (-1, 5), (1, -5), (1,5), (5,-1), (5,1)\} \\ \end{array}$$ The desired number is therefore $4+ 8 + 8 + 12 + 8 = 40$. \begin{exa}\label{exa:positive_divisors} The positive divisors of $400$ are written in increasing order $$1,2,4,5,8, \ldots, 200, 400. $$How many integers are there in this sequence. How many of the divisors of $400$ are perfect squares? \end{exa} Solution: Since $400 = 2^4 \cdot 5^2$, any positive divisor of $400$ has the form $2^a5^b$ where $0 \leq a \leq 4$ and $0\leq b \leq 2$. Thus there are $5$ choices for $a$ and $3$ choices for $b$ for a total of $5\cdot 3 = 15$ positive divisors. \bigskip To be a perfect square, a positive divisor of $400$ must be of the form $2^\alpha 5^\beta$ with $\alpha \in \{0, 2, 4\}$ and $\beta \in \{0, 2\}$. Thus there are $3\cdot 2 = 6$ divisors of $400$ which are also perfect squares. \bigskip By arguing as in example \ref{exa:positive_divisors}, we obtain the following theorem. \begin{thm}\label{thm:positive_divisors} Let the positive integer $n$ have the prime factorisation $$n = p_1 ^{a_1}p_2 ^{a_2}\cdots p_k ^{a_k}, $$where the $p_i$ are different primes, and the $a_i$ are integers $\geq 1$. If $d(n)$ denotes the number of positive divisors of $n$, then $$d(n) = (a_1 + 1)(a_2 + 1)\cdots (a_k + 1). $$ \end{thm} \begin{exa}[AHSME 1977] \label{pro:paths}How many paths consisting of a sequence of horizontal and/or vertical line segments, each segment connecting a pair of adjacent letters in figure \ref{fig:paths} spell $CONTEST$? \end{exa} \begin{figure}[h]\begin{minipage}{5cm}$$ \begin{array}{ccccccccccccc} & & & & & & C & & & & & & \\ & & & & & C & O & C & & & & & \\ & & & & C & O & N & O & C & & & & \\ & & & C & O & N & T & N & O & C & & & \\ & & C& O & N & T & E & T & N & O & C & & \\ & C & O& N & T & E & S & E & T & N & O & C & \\ C & O & N& T & E & S & T & S & T & E & N & O & C \\ \end{array} $$ \footnotesize\hangcaption{Problem \ref{pro:paths}.}\label{fig:paths} \end{minipage} \hfill \begin{minipage}{5cm} $$ \begin{array}{ccccccc} & & & & & & C \\ & & & & & C & O \\ & & & & C & O & N \\ & & & C & O & N & T \\ & & C& O & N & T& E \\ & C & O& N & T & E & S \\ C & O & N& T & E & S & T \\ \end{array} $$ \footnotesize\hangcaption{Problem \ref{pro:paths}.}\label{fig:paths2} \end{minipage} \end{figure} Solution: Split the diagram, as in figure \ref{fig:paths2}. Since every required path must use the bottom right $T$, we count paths starting from this $T$ and reaching up to a $C$. Since there are six more rows that we can travel to, and since at each stage we can go either up or left, we have $2^6 = 64$ paths. The other half of the figure will provide $64$ more paths. Since the middle column is shared by both halves, we have a total of $64 + 64 - 1 = 127$ paths. \begin{exa} The integers from $1$ to $1000$ are written in succession. Find the sum of all the digits.\end{exa} Solution: When writing the integers from $000$ to $999$ (with three digits), $3\times 1000 = 3000$ digits are used. Each of the $10$ digits is used an equal number of times, so each digit is used $300$ times. The the sum of the digits in the interval $000$ to $999$ is thus $$(0 + 1 + 2 + 3+ 4 + 5+ 6+ 7 + 8 + 9)(300) = 13500. $$Therefore, the sum of the digits when writing the integers from $1$ to $1000$ is $13500 + 1 = 13501$. \bigskip \flushleft{\em Aliter:} Pair up the integers from $0$ to $999$ as $$ (0, 999), \ (1, 998), \ (2, 997), \ (3, 996), \ \ldots , (499, 500). $$Each pair has sum of digits $27$ and there are $500$ such pairs. Adding $1$ for the sum of digits of $1000$, the required total is $$27\cdot 500 + 1 = 13501. $$ \begin{exa} The strictly positive integers are written in succession $$ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,\ldots $$Which digit occupies the $3000$-th position? \end{exa} Solution: Upon using \begin{center}\begin{tabular}{ll}$9\cdot 1 = 9$ & $1$-digit integers, \\ $90\cdot 2 = 180$ & $2$-digit integers, \\ $900\cdot 3 = 2700$ & $3$-digit integers, \\ \end{tabular}\end{center}a total of $9 + 180 + 2700 = 2889$ digits have been used, so the $3000$-th digit must belong to a $4$-digit integer. There remains to use $3000 - 2889 = 111$ digits, and $111 = 4\cdot 27 + 3$, so the $3000$-th digit is the third digit of the $28$-th $4$-digit integer, that is, the third digit of $4027$, namely $2$. \section{Combinatorial Methods} Most counting problems we will be dealing with can be classified into one of four categories. We explain such categories by means of an example. \begin{exa} Consider the set $\{a, b, c, d\}$. Suppose we ``select'' two letters from these four. Depending on our interpretation, we may obtain the following answers. \begin{dingautolist}{202} \item {\bf Permutations with repetitions.} The {\em order} of listing the letters is important, and {\em repetition is} allowed. In this case there are $4\cdot 4 = 16$ possible selections: $$\begin{array}{|l|l|l|l|}\hline aa & ab & ac & ad \\ \hline ba & bb & bc & bd \\ \hline ca & cb & cc & cd \\ \hline da & db & dc & dd \\ \hline\end{array} $$ \item {\bf Permutations without repetitions.} The {\em order} of listing the letters is important, and {\em repetition is not} allowed. In this case there are $4\cdot 3 = 12$ possible selections: $$\begin{array}{|l|l|l|l|}\hline & ab & ac & ad \\ \hline ba & & bc & bd \\ \hline ca & cb & & cd \\ \hline da & db & dc & \\ \hline \end{array} $$ \item {\bf Combinations with repetitions.} The {\em order} of listing the letters is {\bf not} important, and {\em repetition is } allowed. In this case there are $\dfrac{4\cdot 3}{2}+4 = 10$ possible selections: $$\begin{array}{|l|l|l|l|} \hline aa & ab & ac & ad \\ \hline & bb & bc & bd \\ \hline & & cc & cd \\ \hline & & & dd \\ \hline \end{array} $$ \item {\bf Combinations without repetitions.} The {\em order} of listing the letters is {\bf not} important, and {\em repetition is not} allowed. In this case there are $\dfrac{4\cdot 3}{2} = 6$ possible selections: $$\begin{array}{|l|l|l|l|}\hline \hspace{.35cm} & ab & ac & ad \\ \hline & & bc & bd \\ \hline & & & cd \\ \hline & & & \\ \hline \end{array} $$ \end{dingautolist} \end{exa} \bigskip We will now consider some examples of each situation. \subsection{Permutations without Repetitions} \begin{df} We define the symbol $!$ (factorial), as follows: $0! = 1$, and for integer $n \geq 1$, $$n! = 1\cdot 2 \cdot 3 \cdots n. $$ $n!$ is read $n$ {\em factorial}. \end{df} \begin{exa}We have $$\begin{array}{lll} 1! &=& 1, \\ 2! &=& 1\cdot 2 = 2, \\ 3! & = & 1\cdot 2\cdot 3 = 6, \\ 4!& = &1\cdot 2\cdot 3\cdot 4 = 24, \\ 5! & = & 1\cdot 2\cdot 3 \cdot 4 \cdot 5 = 120. \end{array}$$ \end{exa} \begin{exa} Write a code fragment to compute $n!$. \end{exa}Solution: The following is an iterative way of solving this problem. \bcp[Ovalbox]{Factorial}{n} \COMMENT \rm{returns}\ n! \\ m \GETS 1 \\ \WHILE n>1 \\ \BEGIN m \GETS n*m \\ n \GETS n-1 \\ \END \\ \RETURN{m}\ecp \begin{df} Let $x_1, x_2, \ldots , x_n$ be $n$ distinct objects. A {\em permutation} of these objects is simply a rearrangement of them. \end{df} \begin{exa} There are $24$ permutations of the letters in $MATH$, namely $$\begin{array}{llllll} MATH & MAHT & MTAH & MTHA & MHTA & MHAT\\ AMTH & AMHT & ATMH & ATHM & AHTM & AHMT\\ TAMH & TAHM & TMAH & TMHA & THMA & THAM\\ HATM & HAMT & HTAM & HTMA & HMTA & HMAT\\ \end{array} $$ \end{exa} \begin{thm}\label{thm:counting_permutations} Let $x_1, x_2, \ldots , x_n$ be $n$ distinct objects. Then there are $n!$ permutations of them. \end{thm} \begin{pf} The first position can be chosen in $n$ ways, the second object in $n - 1$ ways, the third in $n - 2$, etc. This gives $$n(n-1)(n-2) \cdots 2\cdot 1 = n!. $$ \end{pf} \begin{exa} Write a code fragment that prints all $n!$ of the set $\{1,2,\ldots , n\}$. \end{exa}Solution: The following programme prints them in lexicographical order. We use examples \ref{exa:swapping1} and \ref{exa:ReverseArray}. \bcp[Ovalbox]{Permutations}{n} k \GETS n -1 \\ \WHILE X[k]>X[k-1] \\ \BEGIN k \GETS k-1 \END \\ t \GETS k+1 \\ \WHILE ((t X[k])) \\ \BEGIN t\GETS t+1 \END \\ \COMMENT \rm{now\ }X[k+1]>\ldots > X[t]>X[k]>X[t+1]>\ldots > X[n]\\ \sc{Swap}(X[k], X[t]) \\ \COMMENT \rm{now\ }X[k+1]>\ldots > X[n]\\ \sc{ReverseArray}(X[k+1], \ldots , X[n]) \ecp \begin{exa} A bookshelf contains $5$ German books, $7$ Spanish books and $8$ French books. Each book is different from one another. \begin{multicols}{2}\columnseprule 1pt \columnsep 25pt\multicoltolerance=900\small \begin{dingautolist}{202} \item How many different arrangements can be done of these books? \item How many different arrangements can be done of these books if books of each language must be next to each other? \item How many different arrangements can be done of these books if all the French books must be next to each other? \item How many different arrangements can be done of these books if no two French books must be next to each other? \end{dingautolist} \end{multicols} \end{exa} Solution: \begin{multicols}{2}\columnseprule 1pt \columnsep 25pt\multicoltolerance=900\small \begin{dingautolist}{202} \item We are permuting $5 + 7 + 8 = 20$ objects. Thus the number of arrangements sought is $20! = 2432902008176640000$. \item ``Glue'' the books by language, this will assure that books of the same language are together. We permute the $3$ languages in $3!$ ways. We permute the German books in $5!$ ways, the Spanish books in $7!$ ways and the French books in $8!$ ways. Hence the total number of ways is $3!5!7!8! = 146313216000$. \item Align the German books and the Spanish books first. Putting these $5 + 7 = 12$ books creates $12 + 1 = 13$ spaces (we count the space before the first book, the spaces between books and the space after the last book). To assure that all the French books are next each other, we ``glue'' them together and put them in one of these spaces. Now, the French books can be permuted in $8!$ ways and the non-French books can be permuted in $12!$ ways. Thus the total number of permutations is $$ (13)8!12! = 251073478656000.$$ \item Align the German books and the Spanish books first. Putting these $5 + 7 = 12$ books creates $12 + 1 = 13$ spaces (we count the space before the first book, the spaces between books and the space after the last book). To assure that no two French books are next to each other, we put them into these spaces. The first French book can be put into any of $13$ spaces, the second into any of $12$, etc., the eighth French book can be put into any $6$ spaces. Now, the non-French books can be permuted in $12!$ ways. Thus the total number of permutations is $$ (13)(12)(11)(10)(9)(8)(7)(6)12!,$$which is $24856274386944000.$ \end{dingautolist} \end{multicols} \begin{exa}\label{exa:3_digit_no_0} Determine how many $3$-digit integers written in decimal notation do not have a $0$ in their decimal expansion. Also, find the sum of all these $3$-digit numbers. \end{exa} Solution: There are $9\cdot 9 \cdot 9 = 729$ $3$-digit integers not possessing a $0$ in their decimal expansion. If $100x + 10y + z$ is such an integer, then given for every fixed choice of a variable, there are $9 \cdot 9 = 81$ choices of the other two variables. Hence the required sum is $$81(1 + 2 + \cdot + 9)100 + 81(1 + 2 + \cdot + 9)10 + 81(1 + 2 + \cdot + 9)1 = 404595. $$ \begin{exa}\label{exa:3_digit_at_least_one_0} Determine how many $3$-digit integers written in decimal notation possess at least one $0$ in their decimal expansion. What is the sum of all these integers. \end{exa} Solution: Using example \ref{exa:3_digit_no_0}, there are $900 - 729 = 171$ such integers. The sum of {\em all} the three digit integers is $$100 + 101 + \cdots + 998 + 999. $$To obtain this sum, observe that there are $900$ terms, and that you obtain the same sum adding backwards as forwards: $$ \begin{array}{lcccccccc} S & = & 100 & + & 101 & + & \cdots & + & 999 \\ S & {=} & 999 & + & 998 & + & \cdots & + & 100 \\ 2S & = & 1099 & + & 1099 & + & \cdots & + & 1099 \\ & = & 900(1099), & & & & & \end{array}$$giving $S = \dfrac{900(1099)}{2} = 494550$. The required sum is $494550 - 404595 = 89955$. \subsection{Permutations with Repetitions} We now consider permutations with repeated objects. \begin{exa}\label{exa:permu_repetitions} In how many ways may the letters of the word $$MASSACHUSETTS$$ be permuted? \end{exa}Solution: We put subscripts on the repeats forming $$MA_1S_1S_2A_2CHUS_3ET_1T_2S_4.$$There are now $13$ distinguishable objects, which can be permuted in $13!$ different ways by Theorem \ref{thm:counting_permutations}. For each of these $13!$ permutations, $A_1A_2$ can be permuted in $2!$ ways, $S_1S_2S_3S_4$ can be permuted in $4!$ ways, and $T_1T_2$ can be permuted in $2!$ ways. Thus the over count $13!$ is corrected by the total actual count $$\frac{13!}{2!4!2!} = 64864800. $$ A reasoning analogous to the one of example \ref{exa:permu_repetitions}, we may prove \begin{thm} Let there be $k$ types of objects: $n_1$ of type $1$; $n_2$ of type $2$; etc. Then the number of ways in which these $n_1 + n_2 + \cdots +n_k$ objects can be rearranged is $$ \frac{(n_1 + n_2 + \cdots +n_k)!}{n_1!n_2! \cdots n_k!}. $$ \end{thm} \begin{exa} In how many ways may we permute the letters of the word $MASSACHUSETTS$ in such a way that $MASS$ is always together, in this order? \end{exa} Solution: The particle $MASS$ can be considered as one block and the $9$ letters $A,$ $C,$ $H,$ $U,$ $S,$ $E,$ $T,$ $T,$ $S$. In $A,$ $C,$ $H,$ $U,$ $S,$ $E,$ $T,$ $T,$ $S$ there are four $S$'s and two $T$'s and so the total number of permutations sought is $$\frac{10!}{2!2!} = 907200. $$ \begin{exa}\label{exa:summingto9} In how many ways may we write the number $9$ as the sum of three positive integer summands? Here order counts, so, for example, $1 + 7 + 1$ is to be regarded different from $7 + 1 + 1$. \end{exa} Solution: We first look for answers with $$a + b + c = 9, 1 \leq a \leq b \leq c \leq 7$$ and we find the permutations of each triplet. We have $$\begin{array}{|l|l|}\hline (a,b,c) & \mathrm{Number\ of\ permutations} \\ \hline (1,1,7) & \dfrac{3!}{2!} = 3 \\ \hline (1,2,6) & 3! = 6 \\ \hline (1,3,5) & 3! = 6 \\ \hline (1,4,4) & \dfrac{3!}{2!} = 3 \\ \hline (2,2,5) & \dfrac{3!}{2!} = 3 \\ \hline (2,3,4) & 3! = 6 \\ \hline (3,3,3) & \dfrac{3!}{3!} = 1 \\ \hline \end{array}$$ Thus the number desired is $$ 3 + 6 + 6 +3 + 3 + 6 + 1 = 28.$$ \begin{exa} In how many ways can the letters of the word {\bf MURMUR} be arranged without letting two letters which are alike come together? \end{exa} Solution: If we started with, say , {\bf MU} then the {\bf R} could be arranged as follows: $$\begin{array}{|c|c|c|c|c|c|}\hline {\bf M} & {\bf U} & {\bf R} & \hspace{.5cm} & {\bf R} & \hspace{.5cm} \\ \hline \end{array}\ , $$ $$\begin{array}{|c|c|c|c|c|c|}\hline {\bf M} & {\bf U} & {\bf R} & \hspace{.5cm} & \hspace{.5cm} & {\bf R} \\ \hline \end{array}\ , $$ $$\begin{array}{|c|c|c|c|c|c|}\hline {\bf M} & {\bf U} & \hspace{.5cm} & {\bf R} & \hspace{.5cm} & {\bf R} \\ \hline \end{array}\ . $$ In the first case there are $2! = 2$ of putting the remaining {\bf M} and {\bf U}, in the second there are $2!=2$ and in the third there is only $1!$. Thus starting the word with {\bf MU} gives $2 + 2 + 1 = 5$ possible arrangements. In the general case, we can choose the first letter of the word in $3$ ways, and the second in $2$ ways. Thus the number of ways sought is $3\cdot 2 \cdot 5 = 30$. \begin{exa} In how many ways can the letters of the word {\bf AFFECTION} be arranged, keeping the vowels in their natural order and not letting the two {\bf F}'s come together? \end{exa} Solution: There are $\dfrac{9!}{2!}$ ways of permuting the letters of {\bf AFFECTION}. The $4$ vowels can be permuted in $4!$ ways, and in only one of these will they be in their natural order. Thus there are $\dfrac{9!}{2!4!}$ ways of permuting the letters of {\bf AFFECTION} in which their vowels keep their natural order. \bigskip Now, put the $7$ letters of {\bf AFFECTION} which are not the two {\bf F}'s. This creates $8$ spaces in between them where we put the two {\bf F}'s. This means that there are $8\cdot 7!$ permutations of {\bf AFFECTION} that keep the two {\bf F}'s together. Hence there are $\dfrac{8\cdot 7!}{4!}$ permutations of {\bf AFFECTION} where the vowels occur in their natural order. \bigskip In conclusion, the number of permutations sought is $$ \dfrac{9!}{2!4!} - \dfrac{8\cdot 7!}{4!} = \dfrac{8!}{4!}\left(\dfrac{9}{2} -1\right) = \dfrac{8\cdot 7\cdot 6 \cdot 5 \cdot 4!}{4!}\cdot\dfrac{7}{2} = 5880 $$ \subsection{Combinations without Repetitions} \begin{df} Let $n, k$ be non-negative integers with $0\leq k \leq n$. The symbol $\dis{\binom{n}{k}}$ (read ``$n$ {\em choose} $k$'') is defined and denoted by $$\binom{n}{k} = \frac{n!}{k!(n - k)!} = \frac{n\cdot (n - 1) \cdot (n - 2) \cdots (n - k + 1)}{1\cdot 2 \cdot 3 \cdots k}. $$ \end{df} \begin{rem} Observe that in the last fraction, there are $k$ factors in both the numerator and denominator. Also, observe the boundary conditions $$\binom{n}{0} = \binom{n}{n} = 1,\ \ \ \ \binom{n}{1} = \binom{n}{n-1} = n. $$ \end{rem} \begin{exa}We have $$ \begin{array}{lll}\binom{6}{3} & = &\frac{6\cdot 5 \cdot 4}{1\cdot 2 \cdot 3} = 20, \\ \binom{11}{2} & = & \frac{11\cdot 10}{1\cdot 2 } = 55, \\ \binom{12}{7} & = & \frac{12\cdot 11 \cdot 10\cdot 9 \cdot 8 \cdot 7 \cdot 6}{1\cdot 2 \cdot 3\cdot 4\cdot 5 \cdot 6 \cdot 7} = 792, \\ \binom{110}{109} & = & 110, \\ \binom{110}{0} & = & 1. \end{array} $$ \end{exa} \begin{rem} Since $n - (n - k) = k $, we have for integer $n, k$, $0 \leq k \leq n$, the symmetry identity \begin{center}\fcolorbox{blue}{yellow}{$\dis{\binom{n}{k} = \frac{n!}{k!(n - k)!} = \frac{n!}{(n-k)!(n - (n-k))!} = \binom{n}{n - k}}$}. \end{center} This can be interpreted as follows: if there are $n$ different tickets in a hat, choosing $k$ of them out of the hat is the same as choosing $n - k$ of them to remain in the hat.\end{rem} \begin{exa} $$\binom{11}{9} = \binom{11}{2} = 55, $$ $$ \binom{12}{5} = \binom{12}{7} = 792. $$ \end{exa} \begin{df} Let there be $n$ distinguishable objects. A $k$-{\em combination} is a selection of $k$, ($0 \leq k \leq n$) objects from the $n$ made without regards to order. \end{df} \begin{exa} The 2-combinations from the list $\{X, Y, Z, W\}$ are $$XY, XZ, XW, YZ, YW, WZ. $$ \end{exa} \begin{exa} The 3-combinations from the list $\{X, Y, Z,W\}$ are $$XYZ, XYW, XZW, YWZ. $$ \end{exa} \begin{thm} Let there be $n$ distinguishable objects, and let $k$, $0 \leq k \leq n$. Then the numbers of $k$-combinations of these $n$ objects is $\dis{\binom{n}{k}}$. \end{thm} \begin{pf} Pick any of the $k$ objects. They can be ordered in $n(n - 1)(n - 2) \cdots (n - k + 1)$, since there are $n$ ways of choosing the {\em first}, $n - 1$ ways of choosing the {\em second}, etc. This particular choice of $k$ objects can be permuted in $k!$ ways. Hence the total number of $k$-combinations is $$ \frac{n(n - 1)(n - 2) \cdots (n - k + 1)}{k!}= \binom{n}{k}.$$ \end{pf} \begin{exa} From a group of $10$ people, we may choose a committee of $4$ in $\dis{\binom{10}{4} = 210} $ ways. \end{exa} \begin{exa} Three different integers are drawn from the set $\{1,2,\ldots , 20\}$. In how many ways may they be drawn so that their sum is divisible by $3$? \end{exa} Solution: In $\{1,2,\ldots , 20\}$ there are \begin{center} \begin{tabular}{ll} $6$ & numbers leaving remainder $0$ \\ $7$ & numbers leaving remainder $1$ \\ $7$ & numbers leaving remainder $2$ \\ \end{tabular} \end{center} The sum of three numbers will be divisible by $3$ when (a) the three numbers are divisible by $3$; (b) one of the numbers is divisible by $3$, one leaves remainder $1$ and the third leaves remainder $2$ upon division by $3$; (c) all three leave remainder $1$ upon division by $3$; (d) all three leave remainder $2$ upon division by $3$. Hence the number of ways is $$\binom{6}{3} + \binom{6}{1}\binom{7}{1}\binom{7}{1} + \binom{7}{3}+\binom{7}{3} = 384. $$ \vspace{2cm} \begin{figure}[h] \centering \begin{minipage}{5cm} $$\rput(-2,0){\psset{unit=2pc}\psset{gridwidth=1pt,gridlabels=0, subgriddiv=0}\psgrid(0,0)(0,0)(6,3) \psline[linewidth=2pt, linecolor=red](0,0)(4,0)(4,2)(6,2)(6,3) \uput[l](0,0){A} \uput[r](6,3){B} } $$ \vspace{1cm} \footnotesize\footnotesize\hangcaption{Example \ref{exa:routes}.} \label{fig:routes} \end{minipage} \hfill \begin{minipage}{5cm} $$\rput(-2,0){\psset{unit=2pc}\psset{gridwidth=1pt,gridlabels=0, subgriddiv=0}\psgrid(0,0)(0,0)(6,3) \psdots[dotstyle=*, dotscale=1](3,2)\psline[linewidth=2pt, linecolor=red](0,0)(3,0)(3,2)(6,2)(6,3) \uput[l](0,0){A}\uput[ur](3,2){O} \uput[r](6,3){B}} $$ \vspace{1cm} \footnotesize\footnotesize\hangcaption{Example \ref{exa:routes2}.} \label{fig:routes2} \end{minipage} \end{figure} \begin{exa}\label{exa:routes} To count the number of shortest routes from $A$ to $B$ in figure \ref{fig:routes} observe that any shortest path must consist of $6$ horizontal moves and $3$ vertical ones for a total of $6 + 3 = 9$ moves. Of these $9$ moves once we choose the $6$ horizontal ones the $3$ vertical ones are determined. Thus there are $\binom{9}{6} = 84$ paths. \end{exa} \begin{exa}\label{exa:routes2} To count the number of shortest routes from $A$ to $B$ in figure \ref{fig:routes2} that pass through point $O$ we count the number of paths from $A$ to $O$ (of which there are $\binom{5}{3} = 20$) and the number of paths from $O$ to $B$ (of which there are $\binom{4}{3} = 4$). Thus the desired number of paths is $\binom{5}{3}\binom{4}{3} = (20)(4) = 80$. \end{exa} \subsection{Combinations with Repetitions} \begin{thm}[De Moivre] Let $n$ be a positive integer. The number of positive integer solutions to $$x_1 + x_2 + \cdots + x_r = n$$is $$\binom{n - 1}{r - 1}.$$ \label{thm:distributions}\end{thm} \begin{pf} Write $n$ as $$n = 1 + 1 + \cdots + 1 + 1,$$where there are $n$ 1s and $n - 1$ $+$s. To decompose $n$ in $r$ summands we only need to choose $r - 1$ pluses from the $n - 1$, which proves the theorem. \end{pf} \begin{exa} In how many ways may we write the number $9$ as the sum of three positive integer summands? Here order counts, so, for example, $1 + 7 + 1$ is to be regarded different from $7 + 1 + 1$. \end{exa} Solution: Notice that this is example \ref{exa:summingto9}. We are seeking integral solutions to $$ a + b + c = 9, \ \ \ a>0, b>0, c>0. $$ By Theorem \ref{thm:distributions} this is $$\binom{9-1}{3-1} = \binom{8}{2} = 28. $$ \begin{exa} In how many ways can $100$ be written as the sum of four positive integer summands? \end{exa} Solution: We want the number of positive integer solutions to $$a + b + c + d = 100,$$ which by Theorem \ref{thm:distributions} is $$\binom{99}{3} = 156849.$$ \begin{cor}\label{cor:demoivre} Let $n$ be a positive integer. The number of non-negative integer solutions to $$y_1 + y_2 + \cdots + y_r = n$$is $$\binom{n + r - 1}{r - 1}.$$ \end{cor} \begin{pf} Put $x_r - 1 = y_r$. Then $x_r \geq 1$. The equation $$x_1 - 1 + x_2 - 1 + \cdots + x_r - 1 = n$$is equivalent to $$x_1 + x_2 + \cdots + x_r = n + r,$$which from Theorem \ref{thm:distributions}, has $$\binom{n + r - 1}{r - 1}$$solutions. \end{pf} \begin{exa}Find the number of quadruples $(a, b, c, d)$ of integers satisfying $$a + b + c + d = 100, \ a \geq 30, b > 21, c \geq 1, d \geq 1.$$\end{exa} Solution: Put $a' + 29 = a, b' + 20 = b.$ Then we want the number of positive integer solutions to $$a' + 29 + b' + 21 + c + d = 100,$$ or $$a' + b' + c + d = 50.$$ By Theorem \ref{thm:distributions} this number is $$\binom{49}{3} = 18424.$$ \begin{exa} In how many ways may $1024$ be written as the product of three positive integers? \end{exa} Solution: Observe that $1024=2^{10}$. We need a decomposition of the form $2^{10} = 2^a 2^b2^c$, that is, we need integers solutions to $$a+b+c=10, \quad a\geq 0, b\geq 0, c \geq 0. $$By Corollary \ref{cor:demoivre} there are $\binom{10+3-1}{3-1} = \binom{12}{2} = 66$ such solutions. \begin{exa}Find the number of quadruples $(a, b, c, d)$ of non-negative integers which satisfy the inequality $$a + b + c + d \leq 2001.$$\end{exa} Solution: The number of non-negative solutions to $$a + b + c + d \leq 2001$$ equals the number of solutions to $$a + b + c + d + f = 2001$$where $f$ is a non-negative integer. This number is the same as the number of positive integer solutions to $$a_1 - 1 + b_1 - 1 + c_1 - 1 + d_1 - 1 + f_1 - 1 = 2001,$$ which is easily seen to be $\binom{2005}{4}$. \section{Inclusion-Exclusion} The Sum Rule \ref{rul:sum} gives us the cardinality for unions of finite sets that are mutually disjoint. In this section we will drop the disjointness requirement and obtain a formula for the cardinality of unions of general finite sets. \bigskip The Principle of Inclusion-Exclusion is attributed to both Sylvester and to Poincar\'{e}. \begin{thm}[Two set Inclusion-Exclusion] \label{thm:two_set_incl_excl} $$\card{A \cup B} = \card{A} + \card{B} - \card{A \cap B} $$\end{thm} \begin{pf} In the Venn diagram \ref{fig:2_set_incl_excl}, we mark by $R_1$ the number of elements which are simultaneously in both sets (i.e., in $A \cap B$), by $R_2$ the number of elements which are in $A$ but not in $B$ (i.e., in $A \setminus B$), and by $R_3$ the number of elements which are $B$ but not in $A$ (i.e., in $B \setminus A$). We have $R_1 + R_2 + R_3 = \card{A \cup B}$, which proves the theorem. \end{pf} \begin{exa} Of $40$ people, $28$ smoke and $16$ chew tobacco. It is also known that $10$ both smoke and chew. How many among the $40$ neither smoke nor chew? \label{exa:incl_excl_1}\end{exa} Solution: Let $A$ denote the set of smokers and $B$ the set of chewers. Then $$\card{A \cup B} = \card{A} + \card{B} - \card{A \cap B} = 28 + 16 - 10 = 34,$$ meaning that there are 34 people that either smoke or chew (or possibly both). Therefore the number of people that neither smoke nor chew is $40 - 34 = 6.$ \\ {\em Aliter}: We fill up the Venn diagram in figure \ref{fig:incl_excl_1} as follows. Since $|A \cap B| = 8$, we put an 10 in the intersection. Then we put a $28 - 10 = 18$ in the part that $A$ does not overlap $B$ and a $16 - 10 = 6$ in the part of $B$ that does not overlap $A$. We have accounted for $10 + 18 + 6 = 34$ people that are in at least one of the set. The remaining $40 - 34 = 6$ are outside the sets. \vspace{2cm} \begin{figure}[h] \begin{minipage}{7cm}$$ \psset{unit=1pc} \pscircle(-1,0){2} \pscircle(1,0){2} \rput(0,0){\tiny R_1} \rput(-2, 0){\tiny R_2} \rput(2, 0){\tiny R_3} \rput(-3, 1.5){\tiny A} \rput(3, 1.5){\tiny B} $$ \vspace{1cm} \footnotesize\hangcaption{Two-set Inclusion-Exclusion} \label{fig:2_set_incl_excl} \end{minipage} \begin{minipage}{7cm} $$ \psset{unit=1pc} \pscircle(-1,0){2} \pscircle(1,0){2} \rput(0,0){\tiny 8} \rput(-2, 0){\tiny 18} \rput(2, 0){\tiny 6} \rput(2.5, 2.5){\tiny 6} \rput(-3, 1.5){\tiny A} \rput(3, 1.5){\tiny B}$$ \vspace{1cm} \footnotesize\hangcaption{Example \ref{exa:incl_excl_1}.}\label{fig:incl_excl_1}\end{minipage}\ \end{figure} \begin{exa} Consider the set $$A = \{2,4,6, \ldots , 114\} . $$ \begin{dingautolist}{202} \item How many elements are there in $A$?\item How many are divisible by $3$? \item How many are divisible by $5$? \item How many are divisible by $15$? \item How many are divisible by either $3$, $5$ or both? \item How many are neither divisible by $3$ nor $5$? \item How many are divisible by exactly one of $3$ or $5$? \end{dingautolist} \end{exa}Solution: Let $A_3 \subset A$ be the set of those integers divisible by $3$ and $A_5 \subset A$ be the set of those integers divisible by $5$. \begin{dingautolist}{202} \item Notice that the elements are $2 = 2(1)$, $4 = 2(2)$, \ldots , $114 = 2(57)$. Thus $\card{A} = 57.$ \item There are $\lfloor \frac{57}{3}\rfloor = 19$ integers in $A$ divisible by $3$. They are $$\{6, 12, 18, \ldots , 114\}.$$ Notice that $114 = 6(19)$. Thus $\card{A_3} = 19$. \item There are $\lfloor \frac{57}{5}\rfloor = 11$ integers in $A$ divisible by $5$. They are $$\{10, 20, 30, \ldots , 110\}.$$ Notice that $110 = 10(11)$. Thus $\card{A_{5}} = 11$\item There are $\lfloor \frac{57}{15}\rfloor = 3$ integers in $A$ divisible by $15$. They are $\{30, 60, 90\}.$ Notice that $90 = 30(3)$. Thus $\card{A_{15}} = 3 $, and observe that by Theorem \ref{thm:intersection_of_ideals} we have $\card{A_{15}} = \card{A_3 \cap A_5}$.\item We want $\card{A_3 \cup A_5} = 19 + 11 = 30.$ \item We want $$\card{A \setminus (A_3 \cup A_5)} = \card{A} - \card{A_3 \cup A_5} = 57 - 30 = 27.$$ \item We want $$\begin{array}{lll}\card{(A_3 \cup A_5) \setminus (A_3 \cap A_5)} & = & \card{(A_3 \cup A_5)} - \card{A_3 \cap A_5}\\ & = & 30 - 3 \\ & = & 27.\end{array}$$ \end{dingautolist} \begin{exa} How many integers between $1$ and $1000$ inclusive, do not share a common factor with $1000$, that is, are relatively prime to $1000$? \end{exa} Solution: Observe that $1000 = 2^35^3$, and thus from the $1000$ integers we must weed out those that have a factor of $2$ or of $5$ in their prime factorisation. If $A_2$ denotes the set of those integers divisible by 2 in the interval $[1; 1000]$ then clearly $\dis{ \card{A_2} = \lfloor \frac{1000}{2} \rfloor} = 500$. Similarly, if $A_5$ denotes the set of those integers divisible by $5$ then $\dis{ \card{A_5} = \lfloor \frac{1000}{5} \rfloor} = 200$. Also $\dis{ \card{A_2 \cap A_5} = \lfloor \frac{1000}{10} \rfloor} = 100$. This means that there are $\card{A_2 \cup A_5} = 500 + 200 - 100 = 600$ integers in the interval $[1; 1000]$ sharing at least a factor with $1000$, thus there are $1000 - 600 = 400$ integers in $[1; 1000]$ that do not share a factor prime factor with $1000$. \bigskip We now derive a three-set version of the Principle of Inclusion-Exclusion. \vspace{2cm} \begin{figure}[h] $$ \psset{unit=1pc} \pscircle(-1,0){2} \pscircle(1,0){2} \pscircle(0,1.41421356){2} \rput(2,0){\tiny R_1} \rput(-2, 0){\tiny R_2} \rput(0,0.707106781){\tiny R_3} \rput(0, 2.3){\tiny R_4} \rput(0,-0.72){\tiny R_5} \rput(-1.43,1.43){\tiny R_6} \rput(1.43,1.43){\tiny R_7} \rput(-4.5, 0){\tiny A} \rput(4.5, 0){\tiny B} \rput(0, 4.2){\tiny C} $$ \vspace{1cm} \footnotesize\footnotesize\hangcaption{Three-set Inclusion-Exclusion} \label{fig:3set_incl_excl}\end{figure} \begin{thm}[Three set Inclusion-Exclusion]\label{thm:three_set_incl_excl} $$ \begin{array}{lll} \card{A \cup B \cup C} & = & \card{A} + \card{B} + \card{C}\\ & & - \card{A \cap B} - \card{B \cap C } - \card{C \cap A} \\ & & + \card{A \cap B \cap C} \end{array} $$ \end{thm} \begin{pf} Using the associativity and distributivity of unions of sets, we see that $$ \begin{array}{lll} \card{A \cup B \cup C} & = & \card{A \cup (B \cup C)} \\ & = & \card{A} + \card{B \cup C} - \card{A \cap (B \cup C)} \\ & = & \card{A} + \card{B \cup C} - \card{(A \cap B) \cup (A \cap C)} \\ & = & \card{A} + \card{B} + \card{C} - \card{B \cap C} \\ & & - \card{A \cap B} - \card{A \cap C}\\ & & + \card{(A\cap B) \cap (A \cap C)} \\ & = & \card{A} + \card{B} + \card{C} - \card{B \cap C} \\ & & - \left( \card{A \cap B} + \card{A \cap C} - \card{A\cap B \cap C}\right) \\ & = & \card{A} + \card{B} + \card{C} \\ & & \quad - \card{A \cap B} - \card{B \cap C } - \card{C \cap A}\\ & & \quad + \card{A \cap B \cap C} .\ \end{array} $$ This gives the Inclusion-Exclusion Formula for three sets. See also figure \ref{fig:3set_incl_excl}. \end{pf} Observe that in the Venn diagram in figure \ref{fig:3set_incl_excl} there are $8$ disjoint regions (the 7 that form $A \cup B \cup C$ and the outside region, devoid of any element belonging to $A \cup B \cup C$). \begin{exa} How many integers between $1$ and $600$ inclusive are not divisible by neither $3,$ nor $5$, nor $7$? \end{exa} Solution: Let $A_k$ denote the numbers in $[1; 600]$ which are divisible by $k = 3, 5, 7.$ Then \renewcommand{\arraystretch}{2} $$ \begin{array}{lllll} \card{A_3} & = & \lfloor\frac{600}{3}\rfloor & = & 200, \\ \card{A_5} & = & \lfloor\frac{600}{5}\rfloor & = & 120, \\ \card{A_7} & = & \lfloor \frac{600}{7}\rfloor & = & 85, \\ \card{A_{15}} & = & \lfloor \frac{600}{15}\rfloor & = & 40 \\ \card{A_{21}} & = & \lfloor \frac{600}{21}\rfloor & = & 28\\ \card{A_{35}} & = & \lfloor \frac{600}{35}\rfloor & = & 17 \\ \card{A_{105}} & = &\lfloor \frac{600}{105}\rfloor & = & 5\\ \end{array} $$ By Inclusion-Exclusion there are $200 + 120 + 85 - 40 - 28 - 17 + 5 = 325$ integers in $[1; 600]$ divisible by at least one of 3, 5, or 7. Those not divisible by these numbers are a total of $600 - 325 = 275.$ \vspace{2cm} \begin{figure}[h] \begin{minipage}{7cm} $$\psset{unit=1.5pc} \pscircle(-1,0){2} \pscircle(1,0){2} \pscircle(0,1.41421356){2} \rput(2,0){\tiny 3} \rput(-2, 0){\tiny 1} \rput(0,0.707106781){\tiny 3} \rput(0, 2.3){\tiny 1} \rput(0,-0.72){\tiny 2} \rput(-1.43,1.43){\tiny 2} \rput(1.43,1.43){\tiny 4} \rput(-3.8, 0){\tiny A} \rput(3.8, 0){\tiny B} \rput(0, 3.8){\tiny C}$$ \vspace{1cm}\footnotesize\footnotesize\hangcaption{Example \ref{exa:3set_incl_excl}.} \label{fig:3set_incl_excl_exa} \end{minipage} \begin{minipage}{7cm} $$ \psset{unit=1.5pc} \pscircle(-1,0){2} \pscircle(1,0){2} \pscircle(0,1.41421356){2}{\tiny \rput(2,0){9550} \rput(-2, 0){9550} \rput(0,0.707106781){14406} \rput(0, 2.3){9550} \rput(0,-0.72){14266} \rput(-1.43,1.43){14266} \rput(1.43,1.43){14266} \uput[dl](-1, -2){\mathrm{without\ a}\ 7} \uput[dr](1, -2){\mathrm{without\ an}\ 8} \uput[u](0, 3.5){\mathrm{without\ a}\ 9}} $$\vspace{1cm}\footnotesize\hangcaption{Example \ref{exa:5digit_inclusion-exclusion}.}\label{fig:5digit_inclusion-exclusion} \end{minipage} \end{figure} \begin{exa} In a group of $30$ people, $8$ speak English, $12$ speak Spanish and $10$ speak French. It is known that $5$ speak English and Spanish, $5$ Spanish and French, and $7$ English and French. The number of people speaking all three languages is $3$. How many do not speak any of these languages? \label{exa:3set_incl_excl}\end{exa} Solution: Let $A$ be the set of all English speakers, $B$ the set of Spanish speakers and $C$ the set of French speakers in our group. We fill-up the Venn diagram in figure \ref{fig:3set_incl_excl_exa} successively. In the intersection of all three we put 8. In the region common to $A$ and $B$ which is not filled up we put $5 - 2 = 3$. In the region common to $A$ and $C$ which is not already filled up we put $5 - 3 = 2$. In the region common to $B$ and $C$ which is not already filled up, we put $7 - 3 = 4.$ In the remaining part of $A$ we put $8 - 2 - 3 - 2 = 1,$ in the remaining part of $B$ we put $12 - 4 - 3 - 2 = 3$, and in the remaining part of $C$ we put $10 - 2 - 3 - 4 = 1$. Each of the mutually disjoint regions comprise a total of $1 + 2 + 3 + 4 + 1 + 2 + 3 = 16$ persons. Those outside these three sets are then $30 - 16 = 14.$ \begin{exa}\label{exa:5digit_inclusion-exclusion} Consider the set of $5$-digit positive integers written in decimal notation. \begin{multicols}{2}\columnseprule 1pt \columnsep 25pt\multicoltolerance=900\small \begin{enumerate} \item How many are there? \item How many do not have a $9$ in their decimal representation? \item How many have at least one $9$ in their decimal representation? \item How many have exactly one $9$? \item How many have exactly two $9$'s? \item How many have exactly three $9$'s? \item How many have exactly four $9$'s? \item How many have exactly five $9$'s? \item How many have neither an $8$ nor a $9$ in their decimal representation? \item How many have neither a $7$, nor an $8$, nor a $9$ in their decimal representation? \item How many have either a $7$, an $8$, or a $9$ in their decimal representation? \end{enumerate} \end{multicols} \end{exa} Solution: \begin{multicols}{2}\columnseprule 1pt \columnsep 25pt\multicoltolerance=900\small \begin{enumerate} \item There are $9$ possible choices for the first digit and $10$ possible choices for the remaining digits. The number of choices is thus $9\cdot10^4 = 90000$. \item There are $8$ possible choices for the first digit and $9$ possible choices for the remaining digits. The number of choices is thus $8\cdot 9^4 = 52488$. \item The difference $90000 - 52488 = 37512.$ \item We condition on the first digit. If the first digit is a $9$ then the other four remaining digits must be different from $9$, giving $9^4 = 6561$ such numbers. If the first digit is not a $9$, then there are $8$ choices for this first digit. Also, we have $\binom{4}{1} = 4$ ways of choosing where the $9$ will be, and we have $9^3$ ways of filling the $3$ remaining spots. Thus in this case there are $8\cdot 4 \cdot 9^3 = 23328$ such numbers. In total there are $6561+23328 = 29889$ five-digit positive integers with exactly one $9$ in their decimal representation. \item We condition on the first digit. If the first digit is a $9$ then one of the remaining four must be a $9$, and the choice of place can be accomplished in $\binom{4}{1} = 4$ ways. The other three remaining digits must be different from $9$, giving $4\cdot 9^3 = 2916$ such numbers. If the first digit is not a $9$, then there are $8$ choices for this first digit. Also, we have $\binom{4}{2} = 6$ ways of choosing where the two $9$'s will be, and we have $9^2$ ways of filling the two remaining spots. Thus in this case there are $8\cdot 6 \cdot 9^2 = 3888$ such numbers. Altogether there are $2916 + 3888 = 6804$ five-digit positive integers with exactly two $9$'s in their decimal representation. \item Again we condition on the first digit. If the first digit is a $9$ then two of the remaining four must be $9$'s, and the choice of place can be accomplished in $\binom{4}{2} = 6$ ways. The other two remaining digits must be different from $9$, giving $6\cdot 9^2 = 486$ such numbers. If the first digit is not a $9$, then there are $8$ choices for this first digit. Also, we have $\binom{4}{3} = 4$ ways of choosing where the three $9$'s will be, and we have $9$ ways of filling the remaining spot. Thus in this case there are $8\cdot 4 \cdot 9 = 288$ such numbers. Altogether there are $486 + 288 = 774$ five-digit positive integers with exactly three $9$'s in their decimal representation. \item If the first digit is a $9$ then three of the remaining four must be $9$'s, and the choice of place can be accomplished in $\binom{4}{3} = 4$ ways. The other remaining digit must be different from $9$, giving $4\cdot 9 = 36$ such numbers. If the first digit is not a $9$, then there are $8$ choices for this first digit. Also, we have $\binom{4}{4} = 4$ ways of choosing where the four $9$'s will be, thus filling all the spots. Thus in this case there are $8\cdot 1 = 8$ such numbers. Altogether there are $36 + 8 = 44$ five-digit positive integers with exactly three $9$'s in their decimal representation. \item There is obviously only $1$ such positive integer. \begin{rem}Observe that $37512 = 29889 + 6804 + 774 + 44 + 1$.\end{rem} \item We have $7$ choices for the first digit and $8$ choices for the remaining $4$ digits, giving $7\cdot 8^4 = 28672$ such integers. \item We have $6$ choices for the first digit and $7$ choices for the remaining $4$ digits, giving $6\cdot 7^4 = 14406$ such integers. \item We use inclusion-exclusion. From figure \ref{fig:5digit_inclusion-exclusion}, the numbers inside the circles add up to $85854$. Thus the desired number is $90000-85854=4146.$ \end{enumerate} \end{multicols} \begin{exa}\item How many integral solutions to the equation $$a + b + c + d = 100,$$are there given the following constraints: $$1 \leq a \leq 10,\ b \geq 0, \ c \geq 2, 20 \leq d \leq 30 ?$$ \end{exa}Solution: We use Inclusion-Exclusion. There are $\binom{80}{3} =82160$ integral solutions to $$a + b + c + d = 100, \ \ a \geq 1, b \geq 0, c \geq 2, d \geq 20.$$ Let $A$ be the set of solutions with $$ a \geq 11, b \geq 0, c \geq 2, d \geq 20$$ and $B$ be the set of solutions with $$ a \geq 1, b \geq 0, c \geq 2, d \geq 31.$$ Then $\card{A} = \binom{70}{3}$, $\card{B} = \binom{69}{3}$, $\card{A \cap B} = \binom{59}{3}$ and so $$\card{A \cup B} = \binom{70}{3} + \binom{69}{3} - \binom{59}{3} = 74625.$$ The total number of solutions to $$a + b + c + d = 100$$with $$1 \leq a \leq 10,\ b \geq 0, \ c \geq 2, 20 \leq d \leq 30 $$ is thus $$\binom{80}{3} - \binom{70}{3} - \binom{69}{3} + \binom{59}{3} = 7535.$$ \section*{Homework}\addcontentsline{toc}{section}{Homework}\markright{Homework} \begin{pro} Telephone numbers in {\em Land of the Flying Camels} have $7$ digits, and the only digits available are $\{0,1, 2,3,4,5, 7, 8\}$. No telephone number may begin in $0$, $1$ or $5$. Find the number of telephone numbers possible that meet the following criteria: \begin{dingautolist}{202} \item You may repeat all digits. \item You may not repeat any of the digits. \item You may repeat the digits, but the phone number must be even. \item You may repeat the digits, but the phone number must be odd. \item You may not repeat the digits and the phone numbers must be odd. \end{dingautolist} \begin{answerXenum}We have \begin{dingautolist}{202} \item This is $ 5\cdot 8^6 = 1310720$. \item This is $5\cdot 7\cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 = 25200 $. \item This is $5\cdot 8^5 \cdot 4 = 655360 $.\item This is $5\cdot 8^5 \cdot 4 = 655360 $. \item We condition on the last digit. If the last digit were $1$ or $5$ then we would have $5$ choices for the first digit, and so we would have $$5\cdot 6 \cdot 5\cdot 4 \cdot 3\cdot 2 \cdot 2 = 7200 $$ phone numbers. If the last digit were either $3$ or $7$, then we would have $4$ choices for the last digit and so we would have$$4\cdot 6\cdot 5 \cdot 4 \cdot 3\cdot 2 \cdot 2 = 5760 $$ phone numbers. Thus the total number of phone numbers is $$7200 + 5760 = 12960. $$ \end{dingautolist} \end{answerXenum} \end{pro} \begin{pro} The number $3$ can be expressed as a sum of one or more positive integers in four ways, namely, as $3$, $1+2$, $2+1$, and $1+1+1$. Shew that any positive integer $n$ can be so expressed in $2^{n-1}$ ways. \begin{answerXenum} $n = \underbrace{1 + 1 + \cdots + 1}_{n-1 \ +\mathrm{'s}}$. One either erases or keeps a plus sign.\end{answerXenum} \end{pro} \begin{pro} Let $n = 2^{31}3^{19}$. How many positive integer divisors of $n^2$ are less than $n$ but do not divide $n$? \begin{answerXenum} There are $589$ such values. The easiest way to see this is to observe that there is a bijection between the divisors of $n^2$ which are $> n$ and those $< n$. For if $n^2 = ab,$ with $a > n$, then $b < n$, because otherwise $n^2 = ab > n\cdot n = n^2$, a contradiction. Also, there is exactly one decomposition $n^2 = n\cdot n.$ Thus the desired number is $$\llfloor\frac{d(n^2)}{2}\rrfloor + 1 - d(n) = \llfloor\frac{(63)(39)}{2}\rrfloor + 1 - (32)(20) = 589.$$ \end{answerXenum} \end{pro} \begin{pro} In how many ways can one decompose the set $$\{1, 2, 3, \ldots , 100\}$$ into subsets $A, B, C$ satisfying $$ A \cup B \cup C = \{1, 2, 3, \ldots , 100\} \ \ \ {\rm and} \ \ \ A \cap B \cap C = \varnothing ?$$ \begin{answerXenum} The conditions of the problem stipulate that both the region outside the circles in diagram \ref{fig:3set_incl_excl} and $R_3$ will be empty. We are thus left with $6$ regions to distribute $100$ numbers. To each of the $100$ numbers we may thus assign one of $6$ labels. The number of sets thus required is $6^{100}$. \end{answerXenum} \end{pro} \begin{pro} How many two or three letter initials for people are available if at least one of the letters must be a D and one allows repetitions? \begin{answerXenum} $(26^2 - 25^2) + (26^3 - 25^3) = 2002$\end{answerXenum} \end{pro} \begin{pro} How many strictly positive integers have all their digits distinct? \begin{answerXenum}$$\begin{array}{l}9 + 9\cdot 9 \\ \qquad +9\cdot9\cdot 8 +9\cdot9\cdot8\cdot7 \\ \qquad +9\cdot9\cdot8\cdot7\cdot6+9\cdot9\cdot8\cdot7\cdot6\cdot 5 \\ \qquad + 9\cdot9\cdot8\cdot7\cdot6\cdot5\cdot 4 +9\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot 3 \\ \qquad + 9\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot 2 \\ \qquad + 9\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot 1 \\ \qquad = 8877690 \end{array} $$ \end{answerXenum} \end{pro} \begin{pro} To write a book $1890$ digits were utilised. How many pages does the book have? \begin{answerXenum} A total of $$1\cdot 9 + 2\cdot 90 = 189$$digits are used to write pages $1$ to $99$, inclusive. We have of $1890 - 189 = 1701$ digits at our disposition which is enough for $1701/3 = 567$ extra pages (starting from page $100$). The book has $99 + 567 = 666$ pages. \end{answerXenum} \end{pro} \begin{pro} The sequence of palindromes, starting with $1$ is written in ascending order $$1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, \ldots $$ Find the $1984$-th positive palindrome. \begin{answerXenum} It is easy to see that there are $9$ palindromes of $1$-digit, $9$ palindromes with $2$-digits, $90$ with $3$-digits, $9$0 with $4$-digits, $900$ with $5$-digits and $900$ with $6$-digits. The last palindrome with $6$ digits, $999999$, constitutes the $9 + 9 + 90 + 90 + 900 + 900 = 1998$th palindrome. Hence, the $1997$th palindrome is $998899$, the $1996$th palindrome is $997799$, the $1995$th palindrome is $996699$, the $1994$th is $995599$, etc., until we find the $1984$th palindrome to be $985589$. \end{answerXenum} \end{pro} \begin{pro}[AIME 1994] Given a positive integer $n$, let $p(n)$ be the product of the non-zero digits of $n$. (If $n$ has only one digit, then $p(n)$ is equal to that digit.) Let $$ S = p(1) + p(2) + \cdots + p(999).$$ Find $S$. \begin{answerXenum} If $x = 0$, put $m(x) = 1$, otherwise put $m(x) = x.$ We use three digits to label all the integers, from 000 to 999 If $a, b, c$ are digits, then clearly $p(100a + 10b + c) = m(a)m(b)m(c).$ Thus $$ p(000) + \cdots + p(999) = m(0)m(0)m(0) +\cdots + m(9)m(9)m(9), $$ which in turn $$ \begin{array}{ll} = & (m(0) + m(1) + \cdots + m(9))^3 \\ = & (1 + 1 + 2 + \cdots + 9)^3 \\ = & 46^3 \\ = & 97336. \\ \end{array} $$ Hence$$ \begin{array}{lll} S & = & p(001) + p(002) + \cdots + p(999)\\ & = & 97336 - p(000)\\ & = & 97336 - m(0)m(0)m(0)\\ & = & 97335.\\ \end{array}$$ \end{answerXenum} \end{pro} \begin{pro} In each of the $6$-digit numbers $$333333, 225522, 118818, 707099,$$each digit in the number appears at least twice. Find the number of such $6$-digit natural numbers. \begin{answerXenum} The numbers belong to the following categories: (I) all six digits are identical; (II) there are exactly two different digits used, three of one kind, three of the other; (III) there are exactly two different digits used, two of one kind, four of the other; (IV) there are exactly three different digits used, two of each kind. \bigskip There are clearly $9$ numbers belonging to category (I). To count the numbers in the remaining categories, we must consider the cases when the digit $0$ is used or not. If $0$ is not used, then there are $\binom{9}{2}\cdot\dfrac{6!}{3!3!} = 720$ integers in category (II); $\binom{9}{1}\binom{8}{1}\cdot\dfrac{6!}{2!4!} = 1080$ integers in category (III); and $\binom{9}{3}\cdot\dfrac{6!}{2!2!2!} = 7560$ integers in category (IV). If $0$ is used, then the integers may not start with $0$. There are $\binom{9}{1}\cdot \dfrac{5!}{2!3!} = 90$ in category (II) ; $\binom{9}{1}\cdot (\dfrac{5!}{1!4!} + \dfrac{5!}{3!2!}) = 135$ in category (III) ; and $\binom{9}{2}\cdot 2\cdot \dfrac{5!}{1!2!2!} = 3240$ in category (IV). Thus there are altogether $$9 + 720 + 1080 + 7560 + 90 + 135 + 3240 = 12834 $$ such integers. \end{answerXenum} \end{pro} \begin{pro} In each of the $7$-digit numbers $$1001011, 5550000, 3838383, 7777777,$$each digit in the number appears at least thrice. Find the number of such $7$-digit natural numbers. \begin{answerXenum} The numbers belong to the following categories: (I) all seven digits are identical; (II) there are exactly two different digits used, three of one kind, four of the other. \bigskip There are clearly $9$ numbers belonging to category (I). To count the numbers in the remaining category (II), we must consider the cases when the digit $0$ is used or not. If $0$ is not used, then there are $\binom{9}{1}\binom{8}{1}\cdot\dfrac{7!}{3!4!} = 2520$ integers in category (II). If $0$ is used, then the integers may not start with $0$. There are $\binom{9}{1}\cdot \dfrac{6!}{2!4!} + \binom{9}{1}\cdot\dfrac{6!}{3!3!} = 315$ in category (II). Thus there are altogether $2520 + 315 +9= 2844$ such integers. \end{answerXenum} \end{pro} \begin{pro} Would you believe a market investigator that reports that of $1000$ people, $816$ like candy, $723$ like ice cream, $645$ cake, while $562$ like both candy and ice cream, $463$ like both candy and cake, $470$ both ice cream and cake, while $310$ like all three? State your reasons! \begin{answerXenum} Let $C$ denote the set of people who like candy, $I$ the set of people who like ice cream, and $K$ denote the set of people who like cake. We are given that $\card{C} = 816$, $\card{I} = 723$, $\card{K} = 645$, $\card{C\cap I} = 562$, $\card{C\cap K} = 463$, $\card{I\cap K} = 470$, and $\card{C\cap I\cap K} = 310$. By Inclusion-Exclusion we have $$\begin{array}{lll} \card{C \cup I \cup K} & = & \card{C} + \card{I} + \card{K} \\ & & - \card{C \cap I} - \card{C \cap K } - \card{I \cap C} \\ & & + \card{C \cap I \cap K} \\ & = & 816 + 723 + 645 - 562 - 463 - 470 + 310 \\ & = & 999. \end{array}$$ The investigator miscounted, or probably did not report one person who may not have liked any of the three things. \end{answerXenum} \end{pro} \begin{pro} \label{pro:inclusion_exclusion} A survey shews that $90\%$ of high-schoolers in Philadelphia like at least one of the following activities: going to the movies, playing sports, or reading. It is known that $45\%$ like the movies, $48\%$ like sports, and $35\%$ like reading. Also, it is known that $12\%$ like both the movies and reading, $20\%$ like only the movies, and $15\%$ only reading. What percent of high-schoolers like all three activities? \begin{answerXenum} We make the Venn diagram in as in figure \ref{fig:inclusion_exclusion}. From it we gather the following system of equations $$\begin{array}{ccccccccccccccc}x & + & y & + &z & & & & & & & + &20 & = & 45 \\ x & & & + &z &+ &t &+ &u & & & & & = & 48 \\ x & + & y & & &+ &t & & &+ &15 & & & = & 35 \\ x & + & y & & & & & & & & & & & = & 12 \\ x & + & y & + &z &+ &t &+ &u &+ &15 &+ &20& = & 90 \\ \end{array}$$ The solution of this system is seen to be $x = 5,$ $y = 7$, $z = 13$, $t = 8$, $u = 22$. Thus the percent wanted is $5\%$. \end{answerXenum} \end{pro} \begin{pro} An auto insurance company has $10,000$ policyholders. Each policy holder is classified as \begin{center} \begin{itemize}\item young or old, \item male or female, and \item married or single. \end{itemize}\end{center} Of these policyholders, 3000 are young, 4600 are male, and 7000 are married. The policyholders can also be classified as 1320 young males, 3010 married males, and 1400 young married persons. Finally, 600 of the policyholders are young married males. \bigskip How many of the company's policyholders are young, female, and single? \begin{answerXenum}Let $Y, F, S, M$ stand for young, female, single, male, respectively, and let $Ma$ stand for married. We have $$\begin{array}{lll}\card{Y\cap F \cap S} & = & \card{Y\cap F} - \card{Y\cap F \cap Ma} \\ & = &\card{Y} - \card{Y\cap M} \\ & & \qquad - (\card{Y\cap Ma} - \card{Y\cap Ma \cap M}) \\ & = & 3000 - 1320 - (1400 - 600) \\ & = & 880. \end{array} $$ \end{answerXenum} \end{pro} \begin{pro} In {\em Medieval High} there are forty students. Amongst them, fourteen like Mathematics, sixteen like theology, and eleven like alchemy. It is also known that seven like Mathematics and theology, eight like theology and alchemy and five like Mathematics and alchemy. All three subjects are favoured by four students. How many students like neither Mathematics, nor theology, nor alchemy? \begin{answerXenum} Let $A$ be the set of students liking Mathematics, $B$ the set of students liking theology, and $C$ be the set of students liking alchemy. We are given that $$ \card{A} = 14, \card{B} = 16, \card{C} = 11, \card{A\cap B} = 7, \card{B\cap C} = 8, \card{A\cap C} = 5,$$ and $$ \card{A\cap B\cap C} = 4.$$By the Principle of Inclusion-Exclusion, $$ \card{\complement A \cap \complement B \cap \complement C} = 40 - \card{A} - \card{B} - \card{C} + \card{A\cap B} + \card{A\cap C} + \card{B\cap C} - \card{A\cap B \cap C} $$ Substituting the numerical values of these cardinalities $$ 40 - 14 - 16 - 11 + 7 + 5 + 8 - 4 = 15. $$ \end{answerXenum} \end{pro} \begin{pro}[AHSME 1991] For a set $S$, let $n(S)$ denote the number of subsets of $S$. If $A, B, C$, are sets for which $$ n(A) + n(B) + n(C) = n(A\cup B\cup C) \, \, \, {\rm and \,\,} \card{A} = \card{B} = 100,$$ then what is the minimum possible value of $\card{A\cap B\cap C}$? \begin{answerXenum} A set with $k$ elements has $2^k$ different subsets. We are given $$ 2^{100} + 2^{100} + 2^{\card{C}} = 2^{\card{A\cup B\cup C}}.$$ This forces $\card{C} = 101$, as $1 + 2^{\card{C} - 101}$ is larger than $1$ and a power of $2$. Hence $\card{A\cup B \cup C} = 102$. Using the Principle Inclusion-Exclusion, since $\card{A} + \card{B} + \card{C} - \card{A \cup B \cup C} = 199,$ $$ \begin{array}{lcl}\card{A\cap B \cap C} & = & \card{A\cap B} + \card{A\cap C} + \card{B \cap C} - 199 \\ & = & (\card{A} + \card{B} - \card{A\cup B}) + (\card{A} + \card{C} - \card{A\cup C}) \\ & & \quad + (\card{B} + \card{C} - \card{B\cup C}) - 199 \\ & = & 403 - \card{A\cup B} - \card{A \cup C} - \card{B\cup C}.\end{array}$$As $A\cup B, A\cup C, B\cup C \subseteq A\cup B \cup C,$ the cardinalities of all these sets are $\leq 102.$ Thus $$ \card{A\cap B \cap C} = 403 - \card{A\cup B} - \card{A\cup C} - \card{B \cup C} \geq 403 - 3\cdot 102 = 97.$$ The example $$A = \{ 1, 2, \ldots , 100\} , B = \{ 3, 4, \ldots , 102\} ,$$ and $$C = \{ 1, 2, 3, 4, 5, 6, \ldots, 101, 102\}$$ shews that $\card{A\cap B \cap C} = \card{\{ 4, 5, 6, \ldots , 100\}} = 97$ is attainable. \end{answerXenum} \end{pro} \begin{pro}[Lewis Carroll in {\em A Tangled Tale.}] In a very hotly fought battle, at least $70\%$ of the combatants lost an eye, at least $75\%$ an ear, at least $80\%$ an arm, and at least $85\%$ a leg. What can be said about the percentage who lost all four members? \begin{answerXenum} Let $A$ denote the set of those who lost an eye, $B$ denote those who lost an ear, $C$ denote those who lost an arm and $D$ denote those losing a leg. Suppose there are $n$ combatants. Then $$\begin{array}{lll}n & \geq & \card{ A \cup B} \\ & = & \card{ A} + \card{ B} - \card{ A \cap B} \\ & = & .7n + .75n - \card{ A\cap B}, \end{array}$$ $$\begin{array}{lll}n &\geq & \card{ C \cup D} \\ & = & \card{ C} + \card{ D} - \card{ C \cap D} \\ & = & .8n + .85n - \card{ C\cap D}. \end{array}$$This gives $$\card{ A \cap B} \geq .45n,$$ $$\card{ C \cap D} \geq .65n.$$This means that $$\begin{array}{lll}n &\geq & \card{ (A\cap B) \cup (C \cap D)} \\ & = & \card{ A \cap B} + \card{ C \cap D} - \card{ A \cap B \cap C \cap D}\\ & \geq & .45n + .65n - \card{ A \cap B \cap C \cap D},\end{array}$$ whence $$\card{ A \cap B \cap C \cap D} \geq .45 + .65n - n = .1n.$$This means that at least $10\%$ of the combatants lost all four members. \end{answerXenum} \end{pro} \Closesolutionfile{discans} \section*{Answers}\addcontentsline{toc}{section}{Answers}\markright{Answers} {\small\input{discansCXenum}} \vspace{3cm} \begin{figure}[h] $$\psset{unit=1.5pc} \pscircle(-1,0){2} \pscircle(1,0){2} \pscircle(0,1.41421356){2} \rput(2.1,-0.1){\tiny 15 } \rput(-2.1, -0.1){\tiny 20 } \rput(0,0.707106781){\tiny x} \rput(0, 2.3){\tiny u} \rput(0,-1){\tiny y} \rput(-1.43,1.43){\tiny z} \rput(1.43,1.43){\tiny t} \uput[l](-3.8, 0){\mathrm{Movies}} \uput[r](4, 0){\tiny \mathrm{Reading}} \uput[r](0, 3.8){\tiny \mathrm{Sports}}$$ \vspace{1cm}\footnotesize\footnotesize\hangcaption{Problem \ref{pro:inclusion_exclusion}.} \label{fig:inclusion_exclusion} \end{figure} \chapter{Sums and Recursions} \Opensolutionfile{discans}[discansC5] \section{Famous Sums} To obtain a closed form for $$1 + 2 + \cdots + n = \frac{n(n + 1)}{2} $$ we utilise Gauss' trick: If $$ A_n = 1 + 2 + 3 + \cdots + n $$ then$$ A_n = n + (n - 1) + \cdots + 1.$$Adding these two quantities, $$ \begin{array}{lcccccccc} A_n & = & 1 & + & 2 & + & \cdots & + & n \\ {A_n} & {=} & n & + & (n - 1) & + & \cdots & + & 1 \\ 2A_n & = & (n + 1) & + & (n + 1) & + & \cdots & + & (n + 1) \\ & = & n(n + 1), & & & & & \end{array}$$since there are $n$ summands. This gives $A_n = \dis{\frac{n(n + 1)}{2}}$, that is, \begin{equation} 1 + 2 + \cdots + n = \frac{n(n + 1)}{2}.\end{equation} Applying Gauss's trick to the general arithmetic sum $$ (a) + (a + d) + (a + 2d) + \cdots + (a + (n - 1)d) $$we obtain \begin{equation} (a) + (a + d) + (a + 2d) + \cdots + (a + (n - 1)d) = \frac{n(2a + (n - 1)d)}{2} \end{equation} \begin{exa} Each element of the set $\{10, 11, 12, \ldots , 19, 20\}$ is multiplied by each element of the set $\{21, 22, 23, \ldots , 29, 30\}$. If all these products are added, what is the resulting sum? \end{exa} Solution: This is asking for the product $(10 + 11 + \cdots + 20)(21 + 22 + \cdots + 30)$ after all the terms are multiplied. But $$10 + 11 + \cdots + 20 = \frac{(20 + 10)(11)}{2} = 165$$ and $$21 + 22 + \cdots + 30 = \frac{(30 + 21)(10)}{2} = 255.$$ The required total is $(165)(255) = 42075$. \begin{exa} Find the sum of all integers between $1$ and $100$ that leave remainder $2$ upon division by $6$. \end{exa} Solution: We want the sum of the integers of the form $6r + 2, r = 0, 1, \ldots , 16.$ But this is $$\sum _{r = 0} ^{16}(6r + 2) = 6\sum _{r = 0} ^{16} r + \sum _{r = 0} ^{16}2 = 6\frac{16(17)}{2} + 2(17) = 850.$$ \bigskip A {\em geometric progression} is one of the form $$a, ar, ar^2, ar^3, \ldots, ar^{n - 1}, \ldots, $$ \begin{exa} Find the following geometric sum: $$ 1 + 2 + 4 + \cdots + 1024.$$\end{exa} Solution: Let $$S = 1 + 2 + 4 + \cdots + 1024.$$ Then $$2S = 2 + 4 + 8 + \cdots + 1024 + 2048.$$Hence $$S = 2S - S = (2 + 4 + 8 \cdots + 2048) - (1 + 2 + 4 + \cdots + 1024) = 2048 - 1 = 2047.$$ \begin{exa} Find the geometric sum $$x = \frac{1}{3} + \frac{1}{3^2} + \frac{1}{3^3} + \cdots + \frac{1}{3^{99}}.$$\end{exa} Solution: We have $$ \frac{1}{3}x = \frac{1}{3^2} + \frac{1}{3^3} + \cdots + \frac{1}{3^{99}} + \frac{1}{3^{100}}.$$ Then $$\begin{array}{lcl} \frac{2}{3}x & = & x - \frac{1}{3}x \\ & = & (\frac{1}{3} + \frac{1}{3^2} + \frac{1}{3^3} + \cdots + \frac{1}{3^{99}}) \\ & & \qquad - (\frac{1}{3^2} + \frac{1}{3^3} + \cdots + \frac{1}{3^{99}} + \frac{1}{3^{100}}) \\ & = & \frac{1}{3} - \frac{1}{3^{100}}.\end{array}$$From which we gather $$ x = \frac{1}{2} - \frac{1}{2\cdot 3^{99}}.$$ \bigskip Let us sum now the geometric series $$S = a + ar + ar^2 + \cdots + ar^{n - 1}.$$ Plainly, if $r = 1$ then $S = na$, so we may assume that $r \neq 1$. We have $$rS = ar + ar^2 + \cdots + ar^n.$$ Hence $$S - rS = a + ar + ar^2 + \cdots + ar^{n - 1} - ar - ar^2 - \cdots - ar^n = a - ar^n.$$ From this we deduce that $$S = \frac{a - ar^n}{1 - r},$$that is, \begin{equation} a + ar + \cdots + ar^{n - 1} = \frac{a - ar^n}{1 - r} \end{equation} If $|r| < 1$ then $r^n \rightarrow 0$ as $n \rightarrow \infty$. \\ For $|r| < 1$, we obtain the sum of the infinite geometric series \begin{equation} a + ar + ar^2 + \cdots = \frac{a}{1 - r} \end{equation} \begin{exa} A fly starts at the origin and goes $1$ unit up, $1/2$ unit right, $1/4$ unit down, $1/8$ unit left, $1/16$ unit up, etc., {\em ad infinitum.} In what coordinates does it end up?\end{exa} Solution: Its $x$ coordinate is $$\frac{1}{2} - \frac{1}{8} + \frac{1}{32} - \cdots = \frac{\frac{1}{2}}{1 - \frac{-1}{4}} = \frac{2}{5}.$$ Its $y$ coordinate is $$1 - \frac{1}{4} + \frac{1}{16} - \cdots = \frac{1}{1 - \frac{-1}{4}} = \frac{4}{5}.$$Therefore, the fly ends up in $(\frac{2}{5}, \frac{4}{5}).$ \bigskip We now sum again of the first $n$ positive integers, which we have already computed using Gauss' trick. \begin{exa} Find a closed formula for $$A_n = 1 + 2 + \cdots + n.$$ \end{exa} Solution: Observe that $$ k^2 - (k - 1)^2 = 2k - 1.$$ From this $$ \begin{array}{lcl} 1^2 - 0^2 & = & 2\cdot 1 - 1 \\ 2^2 - 1^2 & = & 2\cdot 2 - 1 \\ 3^2 - 2^2 & = & 2\cdot 3 - 1 \\ \vdots & \vdots & \vdots \\ n^2 - (n - 1)^2 & = & 2\cdot n - 1 \end{array} $$ Adding both columns, $$n^2 - 0^2 = 2(1 + 2 + 3 + \cdots + n) - n.$$ Solving for the sum, $$1 + 2 + 3 + \cdots + n = n^2/2 + {n}/{2} = \frac{n(n + 1)}{2}.$$ \begin{exa} Find the sum $$1^2 + 2^2 + 3^2 + \cdots + n^2.$$ \end{exa} Solution: Observe that $$ k^3 - (k - 1)^3 = 3k^2 - 3k + 1.$$ Hence $$ \begin{array}{lcl} 1^3 - 0^3 & = & 3\cdot 1^2 - 3\cdot 1 + 1 \\ 2^3 - 1^3 & = & 3\cdot 2^2 - 3\cdot 2 + 1 \\ 3^3 - 2^3 & = & 3\cdot 3^2 - 3\cdot 3 + 1 \\ \vdots & \vdots & \vdots \\ n^3 - (n - 1)^3 & = & 3\cdot n^2 - 3\cdot n + 1 \end{array} $$ Adding both columns, $$n^3 - 0^3 = 3(1^2 + 2^2 + 3^2 + \cdots + n^2) - 3(1 + 2 + 3 + \cdots + n) + n.$$ From the preceding example $1 + 2 + 3 + \cdots + n = \cdot n^2/2 + {n}/{2} = \frac{n(n + 1)}{2}$ so $$n^3 - 0^3 = 3(1^2 + 2^2 + 3^2 + \cdots + n^2) - \frac{3}{2}\cdot n(n + 1) + n.$$ Solving for the sum, $$1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n^3}{3} + \frac{1}{2}\cdot n(n + 1) - \frac{n}{3}.$$ After simplifying we obtain \begin{equation} 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6} \end{equation} \begin{exa} Add the series $$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3\cdot 4} + \cdots + \frac{1}{99\cdot 100} .$$ \end{exa} Solution: Observe that $$ \frac{1}{k(k + 1)} = \frac{1}{k} - \frac{1}{k + 1}.$$Thus $$ \begin{array}{lcl} \frac{1}{1\cdot 2} & = &\frac{1}{1} - \frac{1}{2} \\ \frac{1}{2\cdot 3} & = &\frac{1}{2} - \frac{1}{3} \\ \frac{1}{3\cdot 4} & = &\frac{1}{3} - \frac{1}{4} \\ \vdots & \vdots & \vdots \\ \frac{1}{99\cdot 100} & = &\frac{1}{99} - \frac{1}{100} \end{array} $$ Adding both columns, $$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3\cdot 4} + \cdots + \frac{1}{99\cdot 100} = 1 - \frac{1}{100} = \frac{99}{100}.$$ \begin{exa} Add $$ \frac{1}{1\cdot 4} + \frac{1}{4\cdot 7} + \frac{1}{7\cdot 10} + \cdots + \frac{1}{31\cdot 34}.$$ \end{exa} Solution: Observe that $$ \frac{1}{(3n + 1)\cdot (3n + 4)} = \frac{1}{3}\cdot \frac{1}{3n + 1} - \frac{1}{3}\cdot\frac{1}{3n + 4}.$$ Thus $$ \begin{array}{lcl} \frac{1}{1\cdot 4} & = & \frac{1}{3} - \frac{1}{12} \\ \frac{1}{4\cdot 7} & = &\frac{1}{12} - \frac{1}{21} \\ \frac{1}{7\cdot 10} & = &\frac{1}{21} - \frac{1}{30} \\ \frac{1}{10\cdot 13} & = &\frac{1}{30} - \frac{1}{39} \\ \vdots & \vdots & \vdots \\ \frac{1}{34\cdot 37} & = &\frac{1}{102} - \frac{1}{111} \end{array} $$ Summing both columns, $$\frac{1}{1\cdot 4} + \frac{1}{4\cdot 7} + \frac{1}{7\cdot 10} + \cdots + \frac{1}{31\cdot 34} = \frac{1}{3} - \frac{1}{111} = \frac{12}{37} .$$ \begin{exa} Sum $$ \frac{1}{1\cdot 4\cdot 7} + \frac{1}{4\cdot 7\cdot 10} + \frac{1}{7\cdot 10 \cdot 13} + \cdots + \frac{1}{25\cdot 28\cdot 31}.$$ \end{exa} Solution: Observe that $$ \frac{1}{(3n + 1)\cdot (3n + 4)\cdot (3n + 7)} = \frac{1}{6}\cdot \frac{1}{(3n + 1)(3n + 4)} - \frac{1}{6}\cdot\frac{1}{(3n + 4)(3n + 7)}.$$ Therefore $$ \begin{array}{lcl} \frac{1}{1\cdot 4\cdot 7} & = & \frac{1}{6\cdot 1\cdot 4} - \frac{1}{6\cdot 4\cdot 7} \\ \frac{1}{4\cdot 7\cdot 10} & = &\frac{1}{6\cdot 4\cdot 7} - \frac{1}{6\cdot 7\cdot 10} \\ \frac{1}{7\cdot 10\cdot 13} & = &\frac{1}{6\cdot 7\cdot 10} - \frac{1}{6\cdot 10\cdot 13} \\ \vdots & \vdots & \vdots \\ \frac{1}{25\cdot 28\cdot 31} & = &\frac{1}{6\cdot 25\cdot 28} - \frac{1}{6\cdot 28\cdot 31} \end{array} $$ Adding each column, $$ \frac{1}{1\cdot 4\cdot 7} + \frac{1}{4\cdot 7\cdot 10} + \frac{1}{7\cdot 10 \cdot 13} + \cdots + \frac{1}{25\cdot 28\cdot 31} = \frac{1}{6\cdot 1\cdot 4} - \frac{1}{6\cdot 28\cdot 31} = \frac{9}{217}.$$ \begin{exa} Find the sum $$ 1\cdot 2 + 2\cdot 3 + 3\cdot 4 + \cdots + 99\cdot 100.$$ \end{exa} Solution: Observe that $$ k(k + 1) = \frac{1}{3}(k)(k + 1)(k + 2) - \frac{1}{3}(k - 1)(k)(k + 1).$$Therefore $$ \begin{array}{lcl} 1\cdot 2 & = & \frac{1}{3}\cdot 1\cdot 2 \cdot 3 - \frac{1}{3}\cdot 0\cdot 1\cdot 2 \\ 2\cdot 3 & = & \frac{1}{3}\cdot 2\cdot 3 \cdot 4 - \frac{1}{3}\cdot 1\cdot 2\cdot 3 \\ 3\cdot 4 & = & \frac{1}{3}\cdot 3\cdot 4\cdot 5 - \frac{1}{3}\cdot 2\cdot 3\cdot 4 \\ \vdots & \vdots & \vdots \\ 99\cdot 100 & = & \frac{1}{3}\cdot 99\cdot 100 \cdot 101 - \frac{1}{3}\cdot 98\cdot 99\cdot 100 \end{array} $$ Adding each column, $$1\cdot 2 + 2\cdot 3 + 3\cdot 4 + \cdots + 99\cdot 100 = \frac{1}{3}\cdot 99\cdot 100\cdot 101 - \frac{1}{3}\cdot 0\cdot 1\cdot 2 = 333300.$$ \section{First Order Recursions} The {\em order} of the recurrence is the difference between the highest and the lowest subscripts. For example $$u_{n + 2} - u_{n + 1} = 2$$ is of the first order, and $$u_{n + 4} + 9u^2 _n = n^5$$is of the fourth order. \bigskip A recurrence is {\em linear} if the subscripted letters appear only to the first power. For example $$u_{n + 2} - u_{n + 1} = 2$$ is a linear recurrence and $$x ^2 _n + nx_{n - 1} = 1 \ \ {\rm and } \ \ x_n + 2^{x_{n - 1}} = 3 $$are not linear recurrences. \bigskip A recursion is {\em homogeneous} if all its terms contain the subscripted variable to the same power. Thus $$x_{m + 3} + 8x_{m + 2} - 9x_m = 0$$ is homogeneous. The equation $$x_{m + 3} + 8x_{m + 2} - 9x_m = m^2 - 3$$is not homogeneous. \bigskip A {\em closed form} of a recurrence is a formula that permits us to find the $n$-th term of the recurrence without having to know a priori the terms preceding it. \bigskip We outline a method for solving first order linear recurrence relations of the form $$x_n = ax_{n - 1} + f(n), a \neq 1,$$ where $f$ is a polynomial. \\ \begin{enumerate} \item First solve the homogeneous recurrence $x_n = ax_{n - 1}$ by ``raising the subscripts'' in the form $x^n = ax^{n - 1}$. This we call the {\em characteristic equation}. Cancelling this gives $x = a.$ The solution to the homogeneous equation $x_n = ax_{n - 1}$ will be of the form $x_n = Aa^n$, where $A$ is a constant to be determined. \item Test a solution of the form $x_n = Aa^n + g(n),$ where $g$ is a polynomial of the same degree as $f$. \end{enumerate} \begin{exa} Let $x_0 = 7$ and $x_n = 2x_{n - 1}, n \geq 1.$ Find a closed form for $x_n.$\end{exa} Solution: Raising subscripts we have the characteristic equation $x^n = 2x^{n - 1}$. Cancelling, $x = 2$. Thus we try a solution of the form $x_n = A2^n$, were $A$ is a constant. But $7 = x_0 = A2^0$ and so $A = 7.$ The solution is thus $x_n = 7(2)^n$. \\ {\em Aliter:} We have $$ \begin{array}{lcl} x_0 & = & 7 \\ x_1 & = & 2x_0 \\ x_2 & = & 2x_1 \\ x_3 & = & 2x_2 \\ \vdots & \vdots & \vdots \\ x_n & = & 2x_{n-1} \\ \end{array} $$ Multiplying both columns, $$x_0x_1\cdots x_n = 7\cdot 2^nx_0x_1x_2\cdots x_{n - 1}.$$Cancelling the common factors on both sides of the equality, $$x_n = 7\cdot 2^n.$$ \begin{exa} Let $x_0 = 7$ and $x_n = 2x_{n - 1} + 1, n \geq 1.$ Find a closed form for $x_n.$ \end{exa} Solution: By raising the subscripts in the homogeneous equation we obtain $x^n = 2x^{n - 1}$ or $x = 2$. A solution to the homogeneous equation will be of the form $x_n = A(2)^n$. Now $f(n) = 1$ is a polynomial of degree 0 (a constant) and so we test a particular constant solution $C$. The general solution will have the form $x_n = A2^n + B$. Now, $7 = x_0 = A2^0 + B = A + B$. Also, $x_1 = 2x_0 + 7 = 15$ and so $15 = x_1 = 2A + B$. Solving the simultaneous equations $$A + B = 7,$$ $$2A + B = 15,$$we find $A = 8, B = -1.$ So the solution is $x_n = 8(2^n) - 1 = 2^{n + 3} - 1.$ \\ {\em Aliter:} We have: $$ \begin{array}{lcl} x_0 & = & 7 \\ x_1 & = & 2x_0 + 1\\ x_2 & = & 2x_1 + 1\\ x_3 & = & 2x_2 + 1\\ \vdots & \vdots & \vdots \\ x_{n - 1} & = & 2x_{n - 2} + 1 \\ x_n & = & 2x_{n-1} + 1\\ \end{array} $$ Multiply the $k$th row by $2^{n - k}$. We obtain $$ \begin{array}{lcl} 2^nx_0 & = & 2^n\cdot 7 \\ 2^{n - 1}x_1 & = & 2^nx_0 + 2^{n - 1}\\ 2^{n - 2}x_2 & = & 2^{n - 1}x_1 + 2^{n - 2}\\ 2^{n - 3}x_3 & = & 2^{n - 2}x_2 + 2^{n - 3}\\ \vdots & \vdots & \vdots \\ 2^2x_{n - 2} & = & 2^3x_{n - 3} + 2^2 \\ 2x_{n - 1} & = & 2^2x_{n - 2} + 2 \\ x_n & = & 2x_{n-1} + 1\\ \end{array} $$Adding both columns, cancelling, and adding the geometric sum, $$x_n = 7\cdot 2^n + (1 + 2 + 2^2 + \cdots + 2^{n - 1}) = 7\cdot 2^n + 2^n - 1 = 2^{n + 3} - 1.$$ {\em Aliter:} Let $u_n = x_n + 1 = 2x_{n - 1} + 2 = 2(x_{n - 1} + 1) = 2u_{n - 1}.$ We solve the recursion $u_n = 2u_{n - 1}$ as we did on our first example: $u_n = 2^nu_0 = 2^n(x_0 + 1) = 2^n\cdot 8 = 2^{n + 3}. $ Finally, $x_n = u_n - 1 = 2^{n + 3} - 1.$ \begin{exa} Let $x_0 = 2, x_n = 9x_{n - 1} - 56n + 63$. Find a closed form for this recursion. \end{exa} Solution: By raising the subscripts in the homogeneous equation we obtain the characteristic equation $x^n = 9x^{n - 1}$ or $x = 9$. A solution to the homogeneous equation will be of the form $x_n = A(9)^n$. Now $f(n) = -56n + 63$ is a polynomial of degree 1 and so we test a particular solution of the form $Bn + C$. The general solution will have the form $x_n = A9^n + Bn + C$. Now $x_0 = 2, x_1 = 9(2) - 56 + 63 = 25, x_2 = 9(25) - 56(2) + 63 = 176$. We thus solve the system $$2 = A + C,$$ $$25 = 9A + B + C,$$ $$176 = 81A + 2B + C.$$ We find $A = 2, B = 7, C = 0.$ The general solution is $x_n = 2(9^n) + 7n.$ \begin{exa} Let $x_0 = 1, x_n = 3x_{n - 1} - 2n^2 + 6n - 3$. Find a closed form for this recursion. \end{exa} Solution: By raising the subscripts in the homogeneous equation we obtain the characteristic equation $x^n = 3x^{n - 1}$ or $x = 9$. A solution to the homogeneous equation will be of the form $x_n = A(3)^n$. Now $f(n) = - 2n^2 + 6n - 3$ is a polynomial of degree 2 and so we test a particular solution of the form $Bn^2 + Cn + D$. The general solution will have the form $x_n = A3^n + Bn^2 + Cn + D$. Now $x_0 = 1, x_1 = 3(1) - 2 + 6 - 3 = 4, x_2 = 3(4) - 2(2)^2 + 6(2) - 3 = 13, x_3 = 3(13) - 2(3)^2 + 6(3) - 3 = 36$. We thus solve the system $$1 = A + D,$$ $$4 = 3A + B + C + D,$$ $$13 = 9A + 4B + 2C + D,$$ $$36 = 27A + 9B + 3C + D.$$ We find $A = B = 1, C = D = 0.$ The general solution is $x_n = 3^n + n^2.$ \begin{exa} Find a closed form for $x_{n} = 2x_{n - 1} + 3^{n - 1}, x_0 = 2.$ \end{exa} Solution: We test a solution of the form $x_n = A2^n + B3^n$. Then $x_0 = 2, x_1 = 2(2) + 3^0 = 5.$ We solve the system $$2 = A + B,$$ $$7 = 2A + 3B.$$We find $A = 1, B = 1.$ The general solution is $x_n = 2^n + 3^n.$ \bigskip We now tackle the case when $a = 1.$ In this case, we simply consider a polynomial $g$ of degree 1 higher than the degree of $f$. \begin{exa} Let $x_0 = 7$ and $x_n = x_{n - 1} + n, n \geq 1.$ Find a closed formula for $x_n.$ \end{exa} Solution: By raising the subscripts in the homogeneous equation we obtain the characteristic equation $x^n = x^{n - 1}$ or $x = 1$. A solution to the homogeneous equation will be of the form $x_n = A(1)^n = A$, a constant. Now $f(n) = n$ is a polynomial of degree 1 and so we test a particular solution of the form $Bn^2 + Cn + D$, one more degree than that of $f$. The general solution will have the form $x_n = A + Bn^2 + Cn + D$. Since $A$ and $D$ are constants, we may combine them to obtain $x_n = Bn^2 + Cn + E.$ Now, $x_0 = 7, x_1 = 7 + 1 = 8, x_2 = 8 + 2 = 10.$ So we solve the system $$7 = E,$$ $$8 = B + C + E,$$ $$10 = 4B + 2C + E.$$ We find $\dis{B = C = \frac{1}{2}, E = 7}$. The general solution is $\dis{x_n = \frac{n^2}{2} + \frac{n}{2} + 7}$. \\ {\em Aliter:} We have $$ \begin{array}{lcl} x_0 & = & 7 \\ x_1 & = & x_0 + 1 \\ x_2 & = & x_1 + 2\\ x_3 & = & x_2 + 3\\ \vdots & \vdots & \vdots \\ x_n & = & x_{n-1} + n \\ \end{array} $$ Adding both columns, $$x_0 + x_1 + x_2 + \cdots + x_n = 7 + x_0 + x_2 + \cdots + x_{n - 1} + (1 + 2 + 3 + \cdots + n).$$ Cancelling and using the fact that $\dis{1 + 2 + \cdots + n = \frac{n(n + 1)}{2}}$, $$x_n = 7 + \frac{n(n + 1)}{2}.$$ \bigskip Some non-linear first order recursions maybe reduced to a linear first order recursion by a suitable transformation. \begin{exa} A recursion satisfies $u_0 = 3, u_{n + 1} ^2 = u_{n}, n \geq 1.$ Find a closed form for this recursion. \end{exa} Solution: Let $v_n = \log u_n.$ Then $v_{n } = \log u_{n } = \log u_{n - 1} ^{1/2} = \frac{1}{2} \log u_{n - 1} = \frac{v_{n - 1}}{2}.$ As $v_n = v_{n - 1}/2,$ we have $v_n = v_0/2^n$, that is, $\log u_n = (\log u_0)/2^n$. Therefore, $u_n = 3^{1/2^n}.$ \begin{exa}[Putnam 1985] Let $d$ be a real number. For each integer $m \geq 0$, define a sequence ${a_m (j)}, j = 0, 1, 2, \cdots$ by $a_m(0) = \frac{d}{2^m},$ and $a_m(j + 1) = (a_m(j + 1))^2 + 2a_m(j), j \geq 0.$ Evaluate $$\lim _{n \rightarrow \infty} a_n(n).$$ \end{exa} Solution: Observe that $a_m(j + 1) + 1 = (a_m(j))^2 + 2a_m(j) + 1 = (a_m(j) + 1)^2.$ Put $v_j = a_m(j) + 1.$ Then $v_{j + 1} = v^2_j,$ and $\ln v_{j + 1} = 2\ln v_j$; Put $y_j = \ln v_j .$ Then $y_{j + 1} = 2y_j;$ and hence $2^ny_0 = y_n$ or $ 2^n \ln v_0 = \ln v_n$ or $v_n = (v_0)^{2^n} = (1 + \frac{d}{2^m})^{2^n}$ or $a_m(n) + 1 = (1 + \frac{d}{2^m})^{2^n}.$ Thus $a_n(n) = (\frac{d}{2^n} + 1)^{2^n} - 1 \rightarrow e^d - 1$ as $n \rightarrow \infty.$ \section{Second Order Recursions} All the recursions that we have so far examined are first order recursions, that is, we find the next term of the sequence given the preceding one. Let us now briefly examine how to solve some second order recursions. \bigskip We now outline a method for solving second order homogeneous linear recurrence relations of the form $$x_n = ax_{n - 1} + bx_{n - 2}.$$ \\ \begin{enumerate} \item Find the characteristic equation by ``raising the subscripts'' in the form $x^n = ax^{n - 1} + bx^{n - 2}$. Cancelling this gives $x^2 - ax - b = 0.$ This equation has two roots $r_1$ and $r_2.$ \item If the roots are different, the solution will be of the form $x_n = A(r_1)^n + B(r_2)^n$, where $A, B$ are constants. \item If the roots are identical, the solution will be of the form $x_n = A(r_1)^n + Bn(r_1)^n$. \end{enumerate} \begin{exa} Let $x_0 = 1, x_1 = -1, x_{n + 2} + 5x_{n + 1} + 6x_n = 0$. \end{exa} Solution: The characteristic equation is $x^2 + 5x + 6 = (x + 3)(x + 2) = 0$. Thus we test a solution of the form $x_n = A(-2)^n + B(-3)^n.$ Since $1 = x_0 = A + B, -1 = -2A - 3B$, we quickly find $A = 2, B = -1.$ Thus the solution is $x_{n} = 2(-2)^n -(-3)^n.$ \begin{exa} Find a closed form for the Fibonacci recursion $f_0 = 0, f_1 = 1, f_n = f_{n - 1} + f_{n - 2}$. \end{exa} Solution: The characteristic equation is $f^2 - f - 1 = 0$, whence a solution will have the form $${f_n = A\left(\frac{1 + \sqrt{5}}{2}\right)^n + B\left(\frac{1 - \sqrt{5}}{2}\right)^n}.$$ The initial conditions give $$0 = A + B,$$ $$1 = A\left(\frac{1 + \sqrt{5}}{2}\right) + B\left(\frac{1 - \sqrt{5}}{2}\right) = \frac{1}{2}\left(A + B\right) + \frac{\sqrt{5}}{2}\left(A - B\right) = \frac{\sqrt{5}}{2}\left(A - B\right)$$ This gives $\dis{A = \frac{1}{\sqrt{5}}, B = -\frac{1}{\sqrt{5}}}$. We thus have the {\em Cauchy-Binet Formula:} \begin{equation} f_n = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n \end{equation} \begin{exa} Solve the recursion $x_0 = 1, x_1 = 4, x_n = 4x_{n - 1} - 4x_{n - 2} = 0.$ \end{exa} Solution: The characteristic equation is $x^2 - 4x + 4 = (x - 2)^2 = 0$. There is a multiple root and so we must test a solution of the form $x_n = A2^n + Bn2^n.$ The initial conditions give $$1 = A,$$ $$4 = 2A + 2B.$$ This solves to $A = 1, B = 1.$ The solution is thus $x_n = 2^n + n2^n$. \section{Applications of Recursions} \begin{exa} Find the recurrence relation for the number of $n$ digit binary sequences with no pair of consecutive $1$'s. \end{exa} Solution: It is quite easy to see that $a_1 = 2, a_2 = 3.$ To form $a_n, n \geq 3,$ we condition on the last digit. If it is 0, the number of sequences sought is $a_{n - 1}$. If it is 1, the penultimate digit must be 0, and the number of sequences sought is $a_{n - 2}$. Thus $$ a_n = a_{n - 1} + a_{n - 2}, \vspace{5mm} a_1 = 2, \ a_2 = 3.$$ \begin{exa} Let there be drawn $n$ ovals on the plane. If an oval intersects each of the other ovals at exactly two points and no three ovals intersect at the same point, find a recurrence relation for the number of regions into which the plane is divided. \end{exa} Solution: Let this number be $a_n$. Plainly $a_1 = 2$. After the $n - 1$th stage, the $n$th oval intersects the previous ovals at $2(n - 1)$ points, i.e. the $n$th oval is divided into $2(n - 1)$ arcs. This adds $2(n - 1)$ regions to the $a_{n - 1}$ previously existing. Thus $$ a_n = a_{n - 1} + 2(n -1), \ a_1 = 2.$$ \begin{exa} Find a recurrence relation for the number of regions into which the plane is divided by $n$ straight lines if every pair of lines intersect, but no three lines intersect. \end{exa} Solution: Let $a_n$ be this number. Clearly $a_1 = 2.$ The $n$th line is cut by he previous $n - 1$ lines at $n - 1$ points, adding $n$ new regions to the previously existing $a_{n -1}.$ Hence $$ a_n = a_{n - 1} + n, \ a_1 = 2 .$$ \begin{exa} {\em (Derangements)} An absent-minded secretary is filling $n$ envelopes with $n$ letters. Find a recursion for the number $D_n$ of ways in which she never stuffs the right letter into the right envelope.\end{exa} Solution: Number the envelopes $1, 2, 3, \cdots , n$. We condition on the last envelope. Two events might happen. Either $n$ and $r (1 \leq r \leq n - 1)$ trade places or they do not. In the first case, the two letters $r$ and $n$ are misplaced. Our task is just to misplace the other $n - 2$ letters, $(1, 2, \cdots , r - 1, r + 1, \cdots , n - 1)$ in the slots $(1, 2, \cdots , r - 1, r + 1, \cdots , n - 1).$ This can be done in $D_{n - 2}$ ways. Since $r$ can be chosen in $n - 1$ ways, the first case can happen in $(n - 1)D_{n - 2}$ ways.\\ In the second case, let us say that letter $r$, $(1 \leq r \leq n - 1)$ moves to the $n$-th position but $n$ moves not to the $r$-th position. Since $r$ has been misplaced, we can just ignore it. Since $n$ is not going to the $r$-th position, we may relabel $n$ as $r$. We now have $n - 1$ numbers to misplace, and this can be done in $D_{n - 1}$ ways.\\ As $r$ can be chosen in $n - 1$ ways, the total number of ways for the second case is $(n - 1)D_{n - 1}.$ Thus $D_n = (n - 1)D_{n - 2} + (n - 1)D_{n - 1}.$ \begin{exa} There are two urns, one is full of water and the other is empty. On the first stage, half of the contains of urn I is passed into urn II. On the second stage 1/3 of the contains of urn II is passed into urn I. On stage three, 1/4 of the contains of urn I is passed into urn II. On stage four 1/5 of the contains of urn II is passed into urn I, and so on. What fraction of water remains in urn I after the 1978th stage? \end{exa} Solution: Let $x_n, y_n, n = 0, 1, 2, \ldots$ denote the fraction of water in urns I and II respectively at stage $n$. Observe that $x_n + y_n = 1$ and that \renewcommand{\arraystretch}{2} $$ \begin{array}{ll} x_0 = 1; y_0 = 0 & \\ & x_1 = x_0 - \frac{1}{2}x_0 = \frac{1}{2}; y_1 = y_1 + \frac{1}{2}x_0 = \frac{1}{2}\\ & x_2 = x_1 + \frac{1}{3}y_1 = \frac{2}{3}; y_2 = y_1 - \frac{1}{3}y_1 = \frac{1}{3} \\ & x_3 = x_2 - \frac{1}{4}x_2 = \frac{1}{2}; y_1 = y_1 + \frac{1}{4}x_2 = \frac{1}{2} \\ & x_4 = x_3 + \frac{1}{5}y_3 = \frac{3}{5}; y_1 = y_1 - \frac{1}{5}y_3 = \frac{2}{5} \\ & x_5 = x_4 - \frac{1}{6}x_4 = \frac{1}{2}; y_1 = y_1 + \frac{1}{6}x_4 = \frac{1}{2} \\ & x_6 = x_5 + \frac{1}{7}y_5 = \frac{4}{7}; y_1 = y_1 - \frac{1}{7}y_5 = \frac{3}{7} \\ & x_7 = x_6 - \frac{1}{8}x_6 = \frac{1}{2}; y_1 = y_1 + \frac{1}{8}x_6 = \frac{1}{2} \\ & x_8 = x_7 + \frac{1}{9}y_7 = \frac{5}{9}; y_1 = y_1 - \frac{1}{9}y_7 = \frac{4}{9} \\ \end{array} $$ A pattern emerges (which may be proved by induction) that at each odd stage $n$ we have $x_n = y_n = \frac{1}{2}$ and that at each even stage we have (if $n = 2k$) $x_{2k} = \frac{k + 1}{2k + 1}, y_{2k} = \frac{k}{2k + 1}$. Since $\frac{1978}{2} = 989$ we have $x_{1978} = \frac{990}{1979}$. \section*{Homework}\addcontentsline{toc}{section}{Homework}\markright{Homework} \begin{pro} Find the sum of all the integers from $1$ to $1000$ inclusive, which are not multiples of $3$ or $5$. \begin{answer5} We compute the sum of all integers from $1$ to $1000$ and weed out the sum of the multiples of $3$ and the sum of the multiples of $5$, but put back the multiples of $15$, which we have counted twice. Put $$A_n = 1 + 2 + 3 + \cdots + n,$$ $$B = 3 + 6 + 9 + \cdots + 999 = 3A_{333},$$ $$C = 5 + 10 + 15 + \cdots + 1000 = 5A_{200},$$ $$D= 15 + 30 + 45 + \cdots + 990 = 15A_{66}.$$ The desired sum is $$ \begin{array}{lll} A_{1000} - B - C + D & = & A_{1000} - 3A_{333} - 5A_{200} + 15A_{66} \\ & = & 500500 - 3\cdot 55611 - 5\cdot 20100 + 15\cdot 2211 \\ & = & 266332. \end{array}$$ \end{answer5} \end{pro} \begin{pro} The sum of a certain number of consecutive positive integers is $1000$. Find these integers. (There is more than one solution. You must find them all.) \\ \begin{answer5} Let the the sum of integers be $S = (l + 1) + (l + 2) + (l + n)$. Using Gauss' trick we obtain $S = \dis{\frac{n(2l + n + 1)}{2}}$. As $S = 1000,$ $2000 = n(2l + n + 1)$. Now $2000 = n^2 + 2ln + n > n^2$, whence $n \leq \lfloor\sqrt{2000}\rfloor = 44$. Moreover, $n$ and $2l + n + 1$ are divisors of $2000$ and are of opposite parity. Since $2000 = 2^45^3$, the odd factors of $2000$ are $1$, $5$, $25$, and $125$. We then see that the problem has the following solutions: $$n = 1, \ l = 999,$$ $$n = 5, \ l = 197,$$ $$n = 16, \ l = 54,$$ $$n = 25, \ l = 27.$$ \end{answer5} \end{pro} \begin{pro} Use the identity $$n^5 - (n-1)^5 = 5n^4 - 10n^3 + 10n^2 - 5n + 1. $$ and the sums $$s_1 = 1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}, $$ $$s_2 = 1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}, $$ $$s_3 = 1^3 + 2^3 + \cdots + n^3 = \left(\dfrac{n(n+1)}{2}\right)^2, $$ in order to find $$s_4 = 1^4 + 2^4 + \cdots + n^4. $$ \begin{answer5} Using the identity for $n = 1$ to $n$: $$n^5 = 5s_4 - 10s_3 + 10s_2 - 5s_1 + n, $$ whence $$\begin{array}{lll}s_4 & = & \dfrac{n^5}{5} +2s_3 - 2s_2 + s_1 - \dfrac{n}{5} \\ & = & \dfrac{n^5}{5} + \dfrac{n^2(n + 1)^2}{2} - \dfrac{n(n+1)(2n+1)}{3} + \dfrac{n(n+1)}{2} - \dfrac{n}{5}\\ & = & \dfrac{n^5}{5}+\dfrac{n^4}{2}+\dfrac{n^3}{3}-\dfrac{n}{30}. \end{array}$$ \end{answer5} \end{pro} \begin{pro} Find the exact value of $$ \dfrac{1}{1\cdot 3 \cdot 5} + \dfrac{1}{3\cdot 5 \cdot 7} + \cdots + \dfrac{1}{997\cdot 999 \cdot 1001 }. $$ \begin{answer5} Observe that $$ \dfrac{1}{(2n-1)(2n+1)} - \dfrac{1}{(2n+1)(2n+3)} = \dfrac{4}{(2n-1)(2n+1)(2n+3)}. $$ Letting $n = 1$ to $n = 499$ we deduce that $$ \dfrac{4}{1\cdot 3 \cdot 5} + \dfrac{4}{3\cdot 5 \cdot 7} + \cdots + \dfrac{4}{997\cdot 999 \cdot 1001 } = \dfrac{1}{1\cdot 3} - \dfrac{1}{999\cdot 1001}, $$ whence the desired sum is $$\dfrac{1}{4\cdot 1\cdot 3} - \dfrac{1}{4\cdot 999\cdot 1001} = \dfrac{83333}{999999}. $$ \end{answer5} \end{pro} \Closesolutionfile{discans} \section*{Answers}\addcontentsline{toc}{section}{Answers}\markright{Answers} {\small\input{discansC5}} \chapter{Graph Theory} \Opensolutionfile{discans}[discansC7] \section{Simple Graphs} \begin{df}A {\em simple graph (network)}\index{graph!simple} $G = (V, E)$ consists of a non-empty set $V$ (called the {\em vertex (node)} set) and a set $E$ (possibly empty) of unordered pairs of elements (called the {\em edges} or {\em arcs}) of $V$. \end{df} Vertices are usually represented by means of dots on the plane, and the edges by means of lines connecting these dots. See figures \ref{fig:k_1} through \ref{fig:k_4'} for some examples of graphs. \begin{df} If $v$ and $v'$ are vertices of a graph $G$ which are joined by an edge $e$, we say that $v$ is {\em adjacent} to $v'$ and that $v$ and $v'$ are {\em neighbours}, and we write $e = vv'$. We say that vertex $v$ is {\em incident} with an edge $e$ if $v$ is an endpoint of $e$. In this case we also say that $e$ is incident with $v$. \end{df} \vspace{2cm} \begin{figure}[h] \begin{minipage}{3cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(0,0) \autonodetext{A}[s]{$v_1$} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{A graph with $\card{V} =1$ and $\card{E}=0$.}\label{fig:k_1} \end{minipage} \hfill \begin{minipage}{3cm} \rput(2,0){\begin{graph}(1,1) \roundnode{B}(-1,0) \autonodetext{B}[s]{$v_2$} \roundnode{A}(1,0) \autonodetext{A}[s]{$v_1$} \edge{A}{B} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{A graph with $\card{V} =2$ and $\card{E}=1$.}\label{fig:k_2} \end{minipage} \hfill \begin{minipage}{3cm} \rput(2,0){\begin{graph}(1,1) \roundnode{B}(-1,0) \autonodetext{B}[s]{$v_2$} \roundnode{A}(1,0) \autonodetext{A}[s]{$v_1$} \roundnode{C}(0,1.732) \autonodetext{C}[n]{$v_3$} \edge{C}{A} \edge{B}{C}\edge{A}{B} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{A graph with $\card{V} =3$ and $\card{E}=3$.}\label{fig:k_3} \end{minipage} \hfill \begin{minipage}{3cm} \rput(2,0){\begin{graph}(1,1) \roundnode{B}(-1,1) \autonodetext{B}[n]{$v_2$} \roundnode{A}(1,1) \autonodetext{A}[n]{$v_1$} \roundnode{D}(1,-1) \autonodetext{D}[s]{$v_4$} \roundnode{C}(-1,-1) \autonodetext{C}[s]{$v_3$} \edge{D}{C} \edge{D}{A} \edge{A}{C}\edge{B}{D} \edge{B}{C} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{A graph with $\card{V} =3$ and $\card{E}=5$.}\label{fig:k_4'} \end{minipage} \end{figure} \begin{df} The {\em degree} of a vertex is the number of edges incident to it. \end{df} Depending on whether $\card{V}$ is finite or not, the graph is finite or infinite. In these notes we will only consider finite graphs. \bigskip Our definition of a graph does not allow that two vertices be joined by more than one edge. If this were allowed we would obtain a {\em multigraph}. \index{multigraph} Neither does it allow {\em loops} \index{loop}, which are edges incident to only one vertex. A graph with loops is a {\em pseudograph}. \index{pseudograph} \begin{df} The complete graph with $n$ vertices $K_n$ is the graph where any two vertices are adjacent. Thus $K_n$ has $\binom{n}{2}$ edges. \end{df} Figure \ref{fig:k_1} shews $K_1$, figure \ref{fig:k_2} shews $K_2$, figure \ref{fig:k_3} shews $K_3$, and figure \ref{fig:k_4} shews $K_4$, figure \ref{fig:k_5} shews $K_5$. \begin{df} Let $G=(V,E)$ be a graph. A subset $S\subseteq V$ is an {\em independent set} of vertices if $uv\not\in E$ for all $u, v$ in $S$ ($S$ may be empty). A {\em bipartite graph} with bipartition $X, Y$ is a graph such that $V = X\cup Y$, $X\cap Y = \varnothing$, and $X$ and $Y$ are independent sets. $X$ and $Y$ are called the {\em parts} of the bipartition. \end{df} \begin{df} $K_{m,n}$ denotes the {\em complete bipartite graph} with $m+n$ vertices. One part, with $m$ vertices, is connected to every other vertex of the other part, with $n$ vertices. \end{df} \begin{df} A $u-v$ {\em walk} \index{walk} in a graph $G = (V, E)$ is an alternating sequence of vertices and edges in $G$ with starting vertex $u$ and ending vertex $v$ such that every edge joins the vertices immediately preceding it and immediately following it. \end{df} \begin{df} A $u-v$ {\em trail} \index{trail} in a graph $G = (V, E)$ is a $u-v$ walk that does not repeat an edge, while a $u-v$ {\em path} \index{path} is a walk that which does not repeat any vertex. \end{df} \begin{df} $P_n$ denotes a {\em path} of length $n$. It is a graph with $n$ edges, and $n+1$ vertices $v_0v_1\cdots v_n$, where $v_i$ is adjacent to $v_{i+1}$ for $n= 0, 1, \ldots , n-1$. \end{df} \begin{df} $C_n$ denotes a {\em cycle} of length $n$. It is a graph with $n$ edges, and $n$ vertices $v_1\cdots v_n$, where $v_i$ is adjacent to $v_{i+1}$ for $n= 1, \ldots , n-1$, and $v_1$ is adjacent to $v_n$. \end{df} \begin{df} $Q_n$ denotes the {\em $n$-dimensional cube}. It is a simple graph with $2^n$ vertices, which we label with $n$-tuples of $0$'s and $1$'s. Vertices of $Q_n$ are connected by an edge if and only if they differ by exactly one coordinate. Observe that $Q_n$ has $n2^{n-1}$ edges. \end{df} Figure \ref{fig:k3,3} shews $K_{3,3}$, figure \ref{fig:p3} shews $P_3$, figure \ref{fig:c5} shews $C_5$, figure \ref{fig:q2} shews $Q_2$, and figure \ref{fig:q3} shews $Q_3$. \begin{df} A {\em subgraph} $G_1 = (V_1, E_1)$ of a graph $G = (V,E)$ is a graph with $V_1 \subseteq V$ and $E_1 \subseteq E$. \end{df} \vspace{2cm} \begin{figure}[h] \begin{minipage}{4cm} \rput(2,0){\begin{graph}(1,1) \roundnode{B}(-1,1) \autonodetext{B}[n]{$v_2$} \roundnode{A}(1,1) \autonodetext{A}[n]{$v_1$} \roundnode{D}(1,-1) \autonodetext{D}[s]{$v_4$} \roundnode{C}(-1,-1) \autonodetext{C}[s]{$v_3$} \edge{D}{C} \edge{D}{A} \edge{A}{C}\edge{B}{D} \edge{B}{C} \edge{A}{B} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{$K_4$.}\label{fig:k_4} \end{minipage} \hfill \begin{minipage}{4cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(1,0) \roundnode{B}(.309,.951) %cos72,sin72 \roundnode{C}(-.809,.587) %cos144,sin144 \roundnode{D}(-.809,-.587) %cos216,sin216 \roundnode{E}(.309,-.951) %cos288,sin288 \autonodetext{A}[e]{A} \autonodetext{B}[n]{B} \autonodetext{C}[w]{C} \autonodetext{D}[s]{D} \autonodetext{E}[e]{E} \edge{A}{B} \edge{A}{C} \edge{A}{D} \edge{A}{E} \edge{B}{C} \edge{B}{D} \edge{B}{E} \edge{C}{D} \edge{C}{E} \edge{D}{E} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{$K_5$.}\label{fig:k_5} \end{minipage} \hfill \begin{minipage}{4cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(-1,1) \roundnode{B}(0,1) \roundnode{C}(1,1) \roundnode{D}(-1,-1) \roundnode{E}(0,-1) \roundnode{F}(1,-1) \autonodetext{A}[n]{$A$} \autonodetext{B}[n]{$B$} \autonodetext{C}[n]{$C$} \autonodetext{D}[s]{$D$} \autonodetext{E}[s]{$E$} \autonodetext{F}[s]{$F$} \edge{A}{D} \edge{A}{E}\edge{A}{F} \edge{B}{D} \edge{B}{E}\edge{B}{F} \edge{C}{D} \edge{C}{E}\edge{C}{F} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{$K_{3,3}$.}\label{fig:k3,3} \end{minipage} \hfill \begin{minipage}{4cm} \rput(2,0){\begin{graph}(1,1) \roundnode{B}(-1,1) \autonodetext{B}[n]{$v_2$} \roundnode{A}(1,1) \autonodetext{A}[n]{$v_1$} \roundnode{D}(1,-1) \autonodetext{D}[s]{$v_4$} \roundnode{C}(-1,-1) \autonodetext{C}[s]{$v_3$} \edge{C}{D} \edge{B}{C} \edge{A}{B} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{$P_3$.}\label{fig:p3} \end{minipage} \end{figure} \begin{figure}[h] \begin{minipage}{4cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(1,0) \roundnode{B}(.309,.951) %cos72,sin72 \roundnode{C}(-.809,.587) %cos144,sin144 \roundnode{D}(-.809,-.587) %cos216,sin216 \roundnode{E}(.309,-.951) %cos288,sin288 \autonodetext{A}[e]{A} \autonodetext{B}[n]{B} \autonodetext{C}[w]{C} \autonodetext{D}[s]{D} \autonodetext{E}[e]{E} \edge{A}{B} \edge{B}{C} \edge{C}{D} \edge{D}{E} \edge{E}{A} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{$C_5$.}\label{fig:c5} \end{minipage} \hfill \begin{minipage}{4cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(-1,1) \roundnode{B}(1,1)\roundnode{C}(1,-1)\roundnode{D}(-1,-1)\edge{A}{B}\edge{B}{C}\edge{C}{D}\edge{D}{A}\autonodetext{A}[w]{01} \autonodetext{B}[e]{11}\autonodetext{C}[e]{10}\autonodetext{D}[w]{00} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{$Q_2$.}\label{fig:q2} \end{minipage} \hfill \begin{minipage}{4cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(-.5,.5) \roundnode{B}(.5,.5)\roundnode{C}(.5,-.5)\roundnode{D}(-.5,-.5) \roundnode{E}(-1.25,1.25) \roundnode{F}(1.25,1.25)\roundnode{G}(1.25,-1.25)\roundnode{H}(-1.25,-1.25)\edge{A}{B}\edge{B}{C}\edge{C}{D} \edge{D}{A}\autonodetext{A}[w]{011} \autonodetext{B}[e]{111}\autonodetext{C}[e]{101}\autonodetext{D}[w]{001} \autonodetext{E}[w]{010}\autonodetext{F}[e]{110}\autonodetext{G}[e]{100}\autonodetext{H}[w]{000} \edge{E}{F} \edge{F}{G}\edge{G}{H}\edge{H}{E} \edge{A}{E}\edge{B}{F}\edge{C}{G}\edge{D}{H} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{$Q_3$.}\label{fig:q3} \end{minipage} \hfill \begin{minipage}{4cm} \rput(2,0){\begin{graph}(1,1) \roundnode{C}(1,0) \roundnode{A}(.309,.951) %cos72,sin72 \roundnode{B}(-.809,.587) %cos144,sin144 \roundnode{F}(-.809,-.587) %cos216,sin216 \roundnode{G}(.309,-.951) %cos288,sin288 \roundnode{E}(-.35675, -.1) \roundnode{D}(.54775, -.3) \edge{A}{B} \edge{A}{C}\autonodetext{A}[n]{A}\autonodetext{B}[w]{B}\autonodetext{C}[e]{C} \autonodetext{E}[w]{E} \autonodetext{D}[e]{D} \autonodetext{F}[w]{F} \autonodetext{G}[e]{G} \edge{A}{E} \edge{A}{D} \edge{C}{E} \edge{D}{F} \edge{E}{G} \edge{B}{F} \edge{F}{G} \edge{C}{G} \edge{B}{D} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{Example \ref{exa:color_graph1}.}\label{fig:color_graph1} \end{minipage} \end{figure} \bigskip We will now give a few examples of problems whose solutions become simpler when using a graph-theoretic model. \begin{exa}\label{exa:color_graph1} If the points of the plane are coloured with three different colours, red, white, and blue, say, shew that there will always exist two points of the same colour which are $1$ unit apart. \end{exa}Solution: In figure \ref{fig:color_graph1} all the edges have length $1$. Assume the property does not hold and that $A$ is coloured red, $B$ is coloured white, $D$ coloured blue. Then $F$ must both be coloured red. Since $E$ and $C$ must not be red, we also conclude that $G$ is red. But then $F$ and $G$ are at distance $1$ apart and both coloured red which contradicts our assumption that the property did not hold. \begin{exa}\label{exa:wolf_goat_cabbage} A wolf, a goat, and a cabbage are on one bank of a river. The ferryman wants to take them across, but his boat is too small to accommodate more than one of them. Evidently, he can neither leave the wolf and the goat, or the cabbage and the goat behind. Can the ferryman still get all of them across the river? \end{exa}Solution: Represent the position of a single item by $0$ for one bank of the river and $1$ for the other bank. The position of the three items can now be given as an ordered triplet, say $(W,G, C)$. For example, $(0,0,0)$ means that the three items are on one bank of the river, $(1,0,0)$ means that the wolf is on one bank of the river while the goat and the cabbage are on the other bank. The object of the puzzle is now seen to be to move from $(0,0,0)$ to $(1,1,1)$, that is, traversing $Q_3$ while avoiding certain edges. One answer is $$000\rightarrow 010\rightarrow 011 \rightarrow 001\rightarrow 101 \rightarrow 111.$$ This means that the ferryman (i) takes the goat across, (ii) returns and that the lettuce over bringing back the goat, (iii) takes the wolf over, (iv) returns and takes the goat over. Another one is $$000\rightarrow 010\rightarrow 110 \rightarrow 100\rightarrow 101 \rightarrow 111.$$ This means that the ferryman (i) takes the goat across, (ii) returns and that the wolf over bringing back the goat, (iii) takes the lettuce over, (iv) returns and takes the goat over. The graph depicting both answers can be seen in figure \ref{fig:wolf_goat_cabbage}. You may want to visit \begin{center} \url{http://www.cut-the-knot.org/ctk/GoatCabbageWolf.shtml} \end{center} for a pictorial representation. \vspace{2cm} \begin{figure}[h]\centering\begin{graph}(1,1) \roundnode{A}(1,0) \roundnode{B}(.5,.866) \roundnode{C}(-.5,.866) \roundnode{D}(-1,0) \roundnode{E}(-.5,-.866) \roundnode{F}(.5,-.866) \roundnode{G}(-2,0) \roundnode{H}(2,0) \autonodetext{A}[w]{101} \autonodetext{B}[n]{001} \autonodetext{C}[n]{011} \autonodetext{D}[e]{010} \autonodetext{E}[s]{110} \autonodetext{F}[s]{100} \autonodetext{G}[w]{000}\autonodetext{H}[e]{111} \edge{H}{A} \edge{A}{B} \edge{B}{C} \edge{C}{D} \edge{D}{E} \edge{E}{F} \edge{F}{A}\edge{G}{D} \end{graph} \vspace{2cm}\footnotesize\hangcaption{Example \ref{exa:wolf_goat_cabbage}.}\label{fig:wolf_goat_cabbage} \end{figure} \begin{exa}[E\"{o}tv\"{o}s Mathematical Competition, 1947] \label{exa:ramsey6-2}Prove that amongst six people in a room there are at least three who know one another, or at least three who do not know one another. \end{exa}Solution: In graph-theoretic terms, we need to shew that every colouring of the edges of $K_6$ into two different colours, say red and blue, contains a monochromatic triangle (that is, the edges of the triangle have all the same colour). Consider an arbitrary person of this group (call him Peter). There are five other people, and of these, either three of them know Peter or else, three of them do not know Peter. Let us assume three do know Peter, as the alternative is argued similarly. If two of these three people know one another, then we have a triangle (Peter and these two, see figure \ref{fig:ramsey6-2}, where the acquaintances are marked by solid lines). If no two of these three people know one another, then we have three mutual strangers, giving another triangle (see figure \ref{fig:ramsey6-2_2}). \begin{figure}[h] \begin{minipage}{7cm} \centering \begin{graph}(1,1) \roundnode{A}(-1,0) \roundnode{B}(1,1) \roundnode{C}(2,.7) \roundnode{D}(1.5,.2) \roundnode{E}(2,-.7) \roundnode{F}(1,-1)\autonodetext{A}[w]{Peter} \edge{A}{B} \edge{A}{C} \edge{A}{D} \edge{B}{D} \edge{A}{E}[\graphlinedash{3}] \edge{A}{F}[\graphlinedash{3}] \edge{B}{C}[\graphlinedash{3}]\edge{C}{D}[\graphlinedash{3}] \end{graph} \vspace{1cm}\footnotesize\hangcaption{Example \ref{exa:ramsey6-2}.}\label{fig:ramsey6-2} \end{minipage} \begin{minipage}{7cm} \centering \begin{graph}(1,1) \roundnode{A}(-1,0) \roundnode{B}(1,1) \roundnode{C}(2,.7) \roundnode{D}(1.5,.2) \roundnode{E}(2,-.7) \roundnode{F}(1,-1)\autonodetext{A}[w]{Peter} \edge{A}{B} \edge{A}{C} \edge{A}{D} \edge{B}{D}[\graphlinedash{3}] \edge{A}{E}[\graphlinedash{3}] \edge{A}{F}[\graphlinedash{3}] \edge{B}{C}[\graphlinedash{3}]\edge{C}{D}[\graphlinedash{3}] \end{graph} \vspace{1cm}\footnotesize\hangcaption{Example \ref{exa:ramsey6-2}.}\label{fig:ramsey6-2_2} \end{minipage} \end{figure} \begin{exa}\label{exa:landaus}Mr. and Mrs. Landau invite four other married couples for dinner. Some people shook hands with some others, and the following rules were noted: (i) a person did not shake hands with himself, (ii) no one shook hands with his spouse, (iii) no one shook hands more than once with the same person. After the introductions, Mr. Landau asks the nine people how many hands they shook. Each of the nine people asked gives a different number. How many hands did Mrs. Landau shake? \end{exa} Solution: The given numbers can either be $0,1,2,\ldots , 8$, or $1,2,\ldots , 9$. Now, the sequence $1,2,\ldots , 9$ must be ruled out, since if a person shook hands nine times, then he must have shaken hands with his spouse, which is not allowed. The only permissible sequence is thus $0,1,2,\ldots , 8$. Consider the person who shook hands $8$ times, as in figure \ref{fig:landaus1}. Discounting himself and his spouse, he must have shaken hands with everybody else. This means that he is married to the person who shook $0$ hands! We now consider the person that shook $7$ hands, as in figure \ref{fig:landaus2}. He didn't shake hands with himself, his spouse, or with the person that shook $0$ hands. But the person that shook hands only once did so with the person shaking $8$ hands. Thus the person that shook hand $7$ times is married to the person that shook hands once. Continuing this argument, we see the following pairs $(8,0)$, $(7,1)$, $(6,2)$, $(5,3)$. This leaves the person that shook hands $4$ times without a partner, meaning that this person's partner did not give a number, hence this person must be Mrs. Landau! Conclusion: Mrs. Landau shook hands four times. A graph of the situation appears in figure \ref{fig:landaus3}. \vspace{1cm} \begin{figure}[h] \begin{minipage}{4cm} \centering \begin{graph}(1,1) \roundnode{A}(1,0) \roundnode{B}(.809, .588) %cos36,sin36 \roundnode{C}(.309, .951) %cos72,sin72 \roundnode{D}(-.309, .951) %cos108,sin108 \roundnode{E}(-.809, .588) %cos144,sin144 \roundnode{F}(-1, 0) %cos180,sin180 \roundnode{G}(-.809, -.588) %cos216,sin216 \roundnode{H}(-.309, -.951) %cos252,sin252 \roundnode{I}(.309, -.951) %cos288,sin288 \roundnode{J}(.809, -.588) %cos324,sin324 \autonodetext{A}[e]{Mr. Landau} \autonodetext{B}[e]{8} \autonodetext{C}[n]{7} \autonodetext{D}[n]{6} \autonodetext{E}[n]{5} \autonodetext{F}[w]{4} \autonodetext{G}[s]{3} \autonodetext{H}[s]{2} \autonodetext{I}[s]{1} \autonodetext{J}[s]{0} \edge{B}{A} \edge{B}{C} \edge{B}{D} \edge{B}{E} \edge{B}{F} \edge{B}{G} \edge{B}{H} \edge{B}{I} \end{graph}\vspace{2cm}\footnotesize\hangcaption{Example \ref{exa:landaus}.} \label{fig:landaus1} \end{minipage} \hfill \begin{minipage}{4cm} \centering \begin{graph}(1,1) \roundnode{A}(1,0) \roundnode{B}(.809, .588) %cos36,sin36 \roundnode{C}(.309, .951) %cos72,sin72 \roundnode{D}(-.309, .951) %cos108,sin108 \roundnode{E}(-.809, .588) %cos144,sin144 \roundnode{F}(-1, 0) %cos180,sin180 \roundnode{G}(-.809, -.588) %cos216,sin216 \roundnode{H}(-.309, -.951) %cos252,sin252 \roundnode{I}(.309, -.951) %cos288,sin288 \roundnode{J}(.809, -.588) %cos324,sin324 \autonodetext{A}[e]{Mr. Landau} \autonodetext{B}[e]{8} \autonodetext{C}[n]{7} \autonodetext{D}[n]{6} \autonodetext{E}[n]{5} \autonodetext{F}[w]{4} \autonodetext{G}[s]{3} \autonodetext{H}[s]{2} \autonodetext{I}[s]{1} \autonodetext{J}[s]{0} \edge{B}{A} \edge{B}{C} \edge{B}{D} \edge{B}{E} \edge{B}{F} \edge{B}{G} \edge{B}{H} \edge{B}{I} \edge{C}{D} \edge{C}{E} \edge{C}{F} \edge{C}{G}\edge{C}{H}\edge{C}{A} \end{graph}\vspace{2cm}\footnotesize\hangcaption{Example \ref{exa:landaus}.} \label{fig:landaus2} \end{minipage} \hfill \begin{minipage}{4cm} \centering \begin{graph}(1,1) \roundnode{A}(1,0) \roundnode{B}(.809, .588) %cos36,sin36 \roundnode{C}(.309, .951) %cos72,sin72 \roundnode{D}(-.309, .951) %cos108,sin108 \roundnode{E}(-.809, .588) %cos144,sin144 \roundnode{F}(-1, 0) %cos180,sin180 \roundnode{G}(-.809, -.588) %cos216,sin216 \roundnode{H}(-.309, -.951) %cos252,sin252 \roundnode{I}(.309, -.951) %cos288,sin288 \roundnode{J}(.809, -.588) %cos324,sin324 \autonodetext{A}[e]{Mr. Landau} \autonodetext{B}[e]{8} \autonodetext{C}[n]{7} \autonodetext{D}[n]{6} \autonodetext{E}[n]{5} \autonodetext{F}[w]{4} \autonodetext{G}[s]{3} \autonodetext{H}[s]{2} \autonodetext{I}[s]{1} \autonodetext{J}[s]{0} \edge{B}{A} \edge{B}{C} \edge{B}{D} \edge{B}{E} \edge{B}{F} \edge{B}{G} \edge{B}{H} \edge{B}{I} \edge{C}{D} \edge{C}{E} \edge{C}{F} \edge{C}{G}\edge{C}{H} \edge{D}{E} \edge{D}{F} \edge{D}{G} \edge{E}{F}\edge{C}{A}\edge{D}{A} \edge{E}{A} \end{graph}\vspace{2cm}\footnotesize\hangcaption{Example \ref{exa:landaus}.} \label{fig:landaus3} \end{minipage} \end{figure} \section{Graphic Sequences} \begin{df} A sequence of non-negative integers is {\em graphic} if there exists a graph whose degree sequence is precisely that sequence. \end{df} \begin{exa} The sequence $1,1,1$ is graphic, since $K_3$ is a graph with this degree sequence, and in general, so is the sequence $\underbrace{n,n,\ldots , n}_{n+1\ n\mathrm{'s}}$, since $K_{n+1}$ has this degree sequence. The degree sequence $1,\underbrace{2,2,\ldots , 2}_{n\ \mathrm{twos}}, 1$ is graphic, since $P_{n+1}$ has this sequence. The degree sequence $\underbrace{2,2,\ldots , 2}_{n\ \mathrm{twos}}$ is graphic, since $C_{n}$ has this sequence. From example \ref{exa:landaus}, the sequence $0,1,2,3,4,5,6,7,8$ is graphic, whereas the sequence $1,2,3,4,5,6,7,8,9$ is not. \end{exa} \begin{figure}[h] \begin{minipage}{3cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(-1,0) \roundnode{B}(0,0) \roundnode{C}(1,0) \autonodetext{A}[w]{$A$} \autonodetext{B}[e]{$B_i$} \autonodetext{C}[e]{$D_j$} \bow{A}{B}{0.5}[\graphlinedash{3}] \bow{A}{C}{-0.5} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{Theorem \ref{thm:Havel_Hakimi}.}\label{fig:hvhk1} \end{minipage} \hfill \begin{minipage}{3cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(-1,0) \roundnode{B}(0,0) \roundnode{C}(1,0) \autonodetext{A}[w]{$A$} \autonodetext{B}[e]{$C_j$} \autonodetext{C}[e]{$B_i$} \bow{A}{B}{0.5} \bow{A}{C}{-0.5}[\graphlinedash{3}] \end{graph}} \vspace{2cm} \footnotesize\hangcaption{Theorem \ref{thm:Havel_Hakimi}.}\label{fig:hvhk2} \end{minipage} \hfill \begin{minipage}{3cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(-1,0) \roundnode{B}(-.5,0) \roundnode{C}(.5,0) \roundnode{D}(1,0) \autonodetext{A}[w]{$A$} \autonodetext{B}[s]{$B_i$} \autonodetext{C}[s]{$D$} \autonodetext{D}[e]{$C_j$} \bow{A}{B}{.5}[\graphlinedash{1}] \bow{B}{C}{.5} \bow{C}{D}{.5}[\graphlinedash{1}]\bow{D}{A}{.5} \end{graph}} \vspace{2cm} \footnotesize\hangcaption{Theorem \ref{thm:Havel_Hakimi}.}\label{fig:hvhk3} \end{minipage} \hfill \begin{minipage}{3cm} \rput(2,0){\begin{graph}(1,1) \roundnode{A}(-1,0) \roundnode{B}(-.5,0) \roundnode{C}(.5,0) \roundnode{D}(1,0) \autonodetext{A}[w]{$A$} \autonodetext{B}[s]{$B_i$} \autonodetext{C}[s]{$D$} \autonodetext{D}[e]{$C_j$} \bow{A}{B}{.5} \bow{B}{C}{.5}[\graphlinedash{1}] \bow{C}{D}{.5}\bow{D}{A}{.5}[\graphlinedash{1}] \end{graph}} \vspace{2cm} \footnotesize\hangcaption{Theorem \ref{thm:Havel_Hakimi}.}\label{fig:hvhk4} \end{minipage} \end{figure} \begin{thm}[Havel-Hakimi]\label{thm:Havel_Hakimi} The two degree sequences $$I: \qquad a \geq b_1 \geq b_2 \geq \cdots \geq b_a \geq c_1 \geq c_2 \geq \cdots \geq c_n,$$ $$II: \qquad b_1-1, b_2-1, \cdots , b_a-1, c_1, c_2, \cdots , c_n,$$ are simultaneously graphic. \end{thm} \begin{pf} Assume first that the sequence $II$ is graphic. There is a graph $G'$ with degree sequence equal to sequence $II$. We construct the graph $G$ from $G'$ by adding a vertex and connecting it to the vertices whose degrees are $ b_1-1, b_2-1, \cdots , b_a-1$. Then $G$ is a graph whose degree sequence is sequence $I$, and so $II\implies I$. \bigskip Assume now that sequence $I$ is graphic. Let $A, B_i, C_i$ be vertices with $\deg A = a, \deg B_i = b_i$, and $\deg C_i = c_i$, respectively. If $A$ were adjacent to all the $B_i$, our task is finished by simply removing $A$. So assume that there is $B_i$ to which $A$ is not adjacent, and a $C_j$ to which $A$ is adjacent. As the sequence is arranged in decreasing order, we must have $b_i \geq c_j$. If it happens that $b_i = c_j$, we then simply exchange $B_i$ and $D_j$ (see figures \ref{fig:hvhk1} and \ref{fig:hvhk2}). If $b_i>c_j$ then $B_i$ has at least one more neighbour than $C_j$. Call this neighbour $D$. In this case we remove the edges $AC_j$ and $B_iD$ and add the edges $AB_i$ and $DC_j$ to obtain a new graph with the same degree sequence as $II$. See figures \ref{fig:hvhk3} and \ref{fig:hvhk4}. This process is iterated until $A$ is adjacent to all the $B_i$. This finishes the proof. \end{pf} \begin{exa} Determine whether the degree sequence $6, 5, 4, 3, 2, 2, 2, 2$ is graphic. \end{exa}Solution: Using the Havel-Hakimi Theorem successively we have $$6, 5, 4, 3, 2, 2, 2, 2 \rightarrow$$ $$4, 3, 2, 1, 1, 1, 2 \rightarrow$$ $$4, 3, 2, 2, 1, 1, 1\rightarrow$$ $$2, 1, 1, 0, 1, 1\rightarrow$$ $$2, 1, 1, 1, 1, 0\rightarrow$$ $$0, 0, 1, 1, 0\rightarrow$$ $$1, 1, 0, 0, 0.$$This last sequence is graphic. By the Havel-Hakimi Theorem, the original sequence is graphic. \section{Connectivity } \begin{df}\index{graph!connected}A graph $G=(V,E)$ is {\em connected} if for any two of its vertices there is a path connecting them. \end{df} \begin{df} \index{connected graph} A graph is \em{connected} if for any two vertices there is a path with these vertices at its ends. \index{component of a graph} A \em{component} of a graph is a maximal connected subgraph. \end{df} \begin{df} A {\em forest}\index{forest} is a graph with no cycles (acyclic). A {\em tree} is a connected acyclic graph. A {\em spanning tree} of a graph of a connected graph $G$ is a subgraph of $G$ which is a tree and having exactly the same of vertices as $G$. \end{df} \section{Traversability} We start with the following, which is valid not only for simple graphs, but also for multigraphs and pseudographs. \begin{thm}[Handshake Lemma]\label{thm:handshake_lemma} Let $G=(V,E)$ be a graph. Then $$ \sum _{v\in V} \deg v = 2\card{E}. $$ \end{thm} \begin{pf} If the edge connects two distinct vertices, as sum traverses through the vertices, each edge is counted twice. If the edge is a loop, then every vertex having a loop contributes $2$ to the sum. This gives the theorem. \end{pf} \begin{cor} Every graph has an even number of vertices of odd degree. \end{cor} \begin{pf} The sum of an odd number of odd numbers is odd. Since the sum of the degrees of the vertices in a simple graph is always even, one cannot have an odd number of odd degree vertices. \end{pf} \begin{df} \index{trail}A {\em trail} is a walk where all the edges are distinct. An {\em Eulerian trail} on a graph $G$\index{trail!Eulerian} is a trail that traverses every edge of $G$. A {\em tour}\index{tour} of $G$ is a closed walk that traverses each edge of $G$ at least once. An {\em Euler tour} on $G$ is a tour traversing each edge of $G$ exactly once, that is, a closed Euler trail. \index{tour!Euler} A graph is {\em eulerian}\index{eulerian} if it contains an Euler tour. \end{df} \begin{thm}\label{thm:eulerian} A nonempty connected graph is eulerian if and only if has no vertices of odd degree. \end{thm} \begin{pf} Assume first that $G$ is eulerian, and let $C$ be an Euler tour of $C$ starting and ending at vertex $u$. Each time a vertex $v$ is encountered along $C$, two of the edges incident to $v$ are accounted for. Since $C$ contains every edge of $G$, $d(v)$ is then even for all $v\neq u$. Also, since $C$ begins and ends in $u$, $d(u)$ must also be even. \bigskip Conversely, assume that $G$ is a connected noneulerian graph with at least one edge and no vertices of odd degree. Let $W$ be the longest walk in $G$ that traverses every edge at most once: $$W = v_0, v_0—v_1, v_1, v_1—v_2, v_2, . . . , v_{n-1}, v_{n-1}—v_n, v_n.$$ Then $W$ must traverse every edge incident to $v_n$, otherwise, $W$ could be extended into a longer walk. In particular, $W$ traverses two of these edges each time it passes through $v_n$ and traverses $v_{n-1}—v_n$ at the end of the walk. This accounts for an odd number of edges, but the degree of $v_n$ is even by assumption. Hence, $W$ must also begin at $v_n$, that is, $v_0 = v_n$. If $W$ were not an Euler tour, we could find an edge not in $W$ but incident to some vertex in $W$ since $G$ is connected. Call this edge $u—v_i$. But then we can construct a longer walk: $$u, u—v_i, v_i, v_i—v_{i+1}, . . . , v_{n-1}—v_n, v_n, v_0—v_1, . . . , v_{i-1}—v_i, v_i.$$ This contradicts the definition of $W$, so $W$ must be an Euler tour. \end{pf} \vspace{2cm} \begin{figure}[!hbtp] \begin{minipage}{7cm} \rput(2,2){\begin{graph}(1,1) \roundnode{A}(0,1) \roundnode{B}(0,0)\roundnode{C}(0,-1) \roundnode{D}(2,0)\autonodetext{A}[n]{A}\autonodetext{B}[w]{B}\autonodetext{C}[s]{C}\autonodetext{D}[e]{D} \edge{A}{D}\edge{B}{D}\edge{C}{D}\bow{A}{B}{.1}\bow{B}{C}{.1}\bow{C}{B}{.1}\bow{B}{A}{.1} \end{graph}} \vspace{1cm}\footnotesize\hangcaption{Example \ref{exa:koningsberg}.}\label{fig:koningsberg} \end{minipage} \begin{minipage}{7cm} \rput(6,0){\begin{graph}(1,1) \bow{E}{A}{.2}[\graphlinewidth*{2.5}]\bow{D}{G}{.2}[\graphlinewidth*{2.5}] \roundnode{A}(-5,0)\autonodetext{A}[s]{$v_1$}\roundnode{B}(-4,0)\autonodetext{B}[s]{$v_2$} \roundnode{C}(-3,0)\autonodetext{C}[s]{$v_2$}\roundnode{D}(-1,0)\roundnode{E}(0,0)\roundnode{F}(4,0) \roundnode{G}(5,0) \autonodetext{D}[s]{$v_i$} \autonodetext{E}[s]{$v_{i+1}$} \autonodetext{F}[s]{$v_{n-1}$} \autonodetext{G}[s]{$v_{n}$} \edge{A}{B}[\graphlinewidth*{2.5}]\edge{B}{C}[\graphlinewidth*{2.5}]\edge{C}{D}[\graphlinedash{3} \graphlinewidth*{2.5}] \edge{D}{E}\edge{E}{F}[\graphlinedash{3} \graphlinewidth*{2.5}]\edge{F}{G}[\graphlinewidth*{2.5}]\end{graph}} \vspace{2cm} \hangcaption{Theorem \ref{thm:dirac}}\label{fig:dirac}\end{minipage} \end{figure} The following problem is perhaps the originator of graph theory. \begin{exa}[K\"{o}nigsberg Bridge Problem] \label{exa:koningsberg}The town of K\"{o}nigsberg (now called Kaliningrad) was built on an island in the Pregel River. The island sat near where two branches of the river join, and the borders of the town spreaded over to the banks of the river as well as a nearby promontory. Between these four land masses, seven bridges had been erected. The townsfolk used to amuse themselves by crossing over the bridges and asked whether it was possible to find a trail starting and ending in the same location allowing one to traverse each of the bridges exactly once. Figure \ref{fig:koningsberg} has a graph theoretic model of the town, with the seven edges of the graph representing the seven bridges. By Theorem \ref{thm:eulerian}, this graph is not Eulerian so it is impossible to find a trail as the townsfolk asked. \end{exa} \begin{df} \index{Hamiltonian cycle} \index{Hamiltonian graph} A \emph{Hamiltonian cycle} in a graph is a cycle passing through every vertex. $G$ is \emph{Hamiltonian} if it contains a Hamiltonian cycle. \end{df} Unlike Theorem \ref{thm:eulerian}, there is no simple characterisation of all graphs with a Hamiltonian cycle. We have the following one way result, however. \begin{thm}[Dirac's Theorem, 1952]\label{thm:dirac} \index{Dirac's Theorem} Let $G= (V,E)$ be a graph with $n = \card{E} \geq 3$ edges whose every vertex has degree $\geq \frac{n}{2}$. Then $G$ is Hamiltonian. \end{thm} \begin{pf} Arguing by contradiction, suppose $G$ is a maximal non-Hamiltonian with with $n\geq 3$, and that $G$ has more than $3$ vertices. Then $G$ cannot be complete. Let $a$ and $b$ be two non-adjacent vertices of $G$. By definition of $G$, $G+ab$ is Hamiltonian, and each of its Hamiltonian cycles must contain the edge $ab$. Hence, there is a Hamiltonian path $v_1v_2\ldots v_n$ in $G$ beginning at $v_1=a$ and ending at $v_n = b$. Put $$S =\{v_i: av_{i+1}\in E\} \qquad \mathrm{and}\qquad \{v_j:v_jb\in E\}. $$As $v_n\in S\cap T$ we must have $\card{S\cup T} = n$. Moreover, $S\cap T = \varnothing$, since if $v_i\S \cap T$ then $G$ would have the Hamiltonian cycle $$v_1v_2\cdots v_iv_nv_{n-1}\cdots v_{i+1}v_1,$$as in figure \ref{fig:dirac}, contrary to the assumption that $G$ is non-Hamiltonian. But then $$d(a) + d(b) = \card{S} + \card{T} = \card{S\cup T} + \card{S\cap T} < n. $$But since we are assuming that $d(a)\geq \dfrac{n}{2}$ and $d(b)\geq \dfrac{n}{2}$, we have arrived at a contradiction. \end{pf} \section{Planarity} \begin{df} A graph is {\em planar}\index{graph!planar} if it can be drawn in a plane with no intersecting edges. \end{df} \begin{exa} $K_4$ is planar, as shewn in figure \ref{fig:faces_k4}. \end{exa} \begin{figure}[h] \centering \begin{graph}(2,2) \roundnode{A}(-1,1)\autonodetext{A}[w]{A} \roundnode{B}(1,1)\autonodetext{B}[ne]{B} \roundnode{C}(1,-1)\autonodetext{C}[e]{C} \roundnode{D}(-1,-1)\autonodetext{D}[w]{D} \edge{A}{B}\edge{A}{C}\edge{B}{C}\edge{C}{D} \edge{D}{A} \bow{B}{D}{.8} \freetext(1.5,0){{\bf 2}}\freetext(.5,.5){{\bf 3}} \freetext(-.5,-.5){{\bf 4}}\freetext(2.5,.0){{\bf 1}} \end{graph} \vspace{2cm}\footnotesize\hangcaption{Example \ref{exa:faces_k4}.}\label{fig:faces_k4} \end{figure} \begin{df} A {\em face}\index{face} of a planar graph is a region bounded by the edges of the graph. \end{df} \begin{exa}\label{exa:faces_k4} From figure \ref{fig:faces_k4}, $K_4$ has $4$ faces. Face {\bf 1} which extends indefinitely, is called the {\em outside face}. \end{exa} \begin{thm}[Euler's Formula] For every drawing of a connected planar graph with $v$ vertices, $e$ edges, and $f$ faces the following formula holds: $$v-e+f = 2. $$ \end{thm} \begin{pf} The proof is by induction on $e$. Let $P(e)$ be the proposition that $v - e + f = 2$ for every drawing of a graph $G$ with $e$ edges. If $e = 0$ and it is connected, then we must have $v = 1$ and hence $f = 1$, since there is only the outside face. Therefore, $v - e + f = 1 - 0 + 1 = 2$, establishing $P(0)$. \bigskip Assume now $P(e)$ is true, and consider a connected graph $G$ with $e + 1$ edges. Either \begin{dingautolist}{202} \item $G$ has no cycles. Then there is only the outside face, and so $f=1$. Since there are $e+1$ edges and $G$ is connected, we must have $v=e+2$. This gives $(e+2)-(e+1)+1 = 2-1+1 = 2$, establishing $P(e+1)$. \item or $G$ has at least one cycle. Consider a spanning tree of $G$ and an edge $uv$ in the cycle, but not in the tree. Such an edge is guaranteed by the fact that a tree has no cycles. Deleting $uv$ merges the two faces on either side of the edge and leaves a graph $G'$ with only $e$ edges, $v$ vertices, and $f$ faces. $G'$ is connected since there is a path between every pair of vertices within the spanning tree. So $v - e + f = 2$ by the induction assumption $P(e)$. But then $$v - e + f = 2 \implies (v) - (e+1) + (f+1) = 2 \implies v-e+f = 2, $$establishing $P(e+1)$. \end{dingautolist} This finishes the proof. \end{pf} \begin{thm}\label{thm:kuratowski_almost} Every simple planar graph with $v\geq 3$ vertices has at $e \leq 3v-6$ edges. Every simple planar graph with $v\geq 3$ vertices and which does not have a $C_3$ has $e\leq 2v-4$ edges. \end{thm} \begin{pf} If $v = 3$, both statements are plainly true so assume that $G$ is a maximal planar graph with $v\geq 4$. We may also assume that $G$ is connected, otherwise, we may add an edge to $G$. Since $G$ is simple, every face has at least $3$ edges in its boundary. If there are $f$ faces, let $F_k$ denote the number of edges on the $k$-th face, for $1 \leq k \leq f$. We then have $$F_1 + F_2 \cdots + F_f \geq 3f.$$ Also, every edge lies in the boundary of at most two faces. Hence if $E_j$ denotes the number of faces that the $j$-th edge has, then $$2e \geq E_1 + E_2 + \cdots + E_e. $$Since $E_1 + E_2 + \cdots + E_e = F_1 + F_2 \cdots + F_f$, we deduce that $2e \geq 3f$. By Euler's Formula we then have $e\leq 3v -6$. \bigskip The second statement follows for $v=4$ by inspecting all graphs $G$ with $v = 4$. Assume then that $v\geq 5$ and that $G$ has no cycle of length $3$. Then each face has at least four edges on its boundary. This gives $2e \geq 4f$ and by Euler's Formula, $e \leq 2v -4$. \end{pf} \begin{exa} $K_5$ is not planar by Theorem \ref{thm:kuratowski_almost} since $K_5$ has $\binom{5}{2} = 10$ edges and $10 > 9 = 3(5)-6$. \end{exa} \begin{exa} $K_{3,3}$ is not planar by Theorem \ref{thm:kuratowski_almost} since $K_{3,3}$ has $3\cdot 3 = 9$ edges and $9 > 8 = 2(6)-4$. \end{exa} \begin{df} A {\em polyhedron} is a convex, three-dimensional region bounded by a finite number of polygonal faces. \end{df} \begin{df} A {\em Platonic solid} is a polyhedron having congruent regular polygon as faces and having the same number of edges meeting at each corner. \end{df} By puncturing a face of a polyhedron and spreading its surface into the plane, we obtain a planar graph. \begin{exa}[Platonic Solid Problem]\index{solid!Platonic} How many Platonic solids are there? If $m$ is the number of faces that meet at each corner of a polyhedron, and $n$ is the number of sides on each face, then, in the corresponding planar graph, there are $m$ edges incident to each of the $v$ vertices. As each edge is incident to two vertices, we have $mv = 2e$, and if each face is bounded by $n$ edges, we also have $nf = 2e$. It follows from Euler's Formula that $$\dfrac{2e}{m} - e + \dfrac{2e}{n} = 2 \implies \dfrac{1}{m} + \dfrac{1}{n} = \dfrac{1}{e} + \dfrac{1}{2}.$$ We must have $n \geq 3$ and $m \geq 3$ for a nondegenerate polygon. Moreover, if either $n$ or $m$ were $\geq 6$ then $$\leq \dfrac{1}{3} + \dfrac{1}{6} = \dfrac{1}{2} < \dfrac{1}{e} + \dfrac{1}{2}.$$Thus we only need to check the finitely many cases with $3 \leq n, m \leq 5$. The table below gives the existing polyhedra. $$\begin{array}{|ll|lll|l|}\hline n & m & v & e & f & \mathrm{polyhedron} \\ \hline 3& 3 & 4 & 6 & 4 & \mathrm{tetrahedron} \\ \hline 4 & 3 & 8 & 12 & 6 & \mathrm{cube} \\ \hline 3 & 4 & 6 & 12 & 8 & \mathrm{octahedron} \\ \hline 3 & 5 & 12 & 30& 20 & \mathrm{icosahedron} \\ \hline 5 & 3 & 20 & 30 & 12 & \mathrm{dodecahedron} \\ \hline \end{array}$$ \end{exa} \begin{exa}[Regions in a Circle]Prove that the chords determined by $n$ points on a circle cut the interior into $1 + \binom{n}{2} + \binom{n}{4}$ regions provided no three chords have a common intersection. \end{exa} Solution: By viewing the points on the circle and the intersection of two chords as vertices, we obtain a plane graph. Each intersection of the chords is determined by four points on the circle, and hence our graph has $v = \binom{n}{4} + n$ vertices. Since each vertex inside the circle has degree $4$ and each vertex on the circumference of the circle has degree $n+1$, the Handshake Lemma (Theorem \ref{thm:handshake_lemma}) we have a total of $$e = \dfrac{1}{2}\left(4\binom{n}{4} + n(n+1)\right) $$edges. Discounting the outside face, our graph has $$f-1 = 1 + e-v = 1 + 2\binom{n}{4} + \dfrac{n^2}{2} + \dfrac{n}{2} - \left( \binom{n}{4} + n\right) = 1 + \binom{n}{2} + \binom{n}{4} $$faces or regions. \section*{Homework}\addcontentsline{toc}{section}{Homework}\markright{Homework} \begin{pro} Determine whether there is a simple graph with eight vertices having degree sequence $6, 5, 4, 3, 2, 2, 2, 2$. \end{pro} \begin{pro} Determine whether the sequence $7, 6, 5, 4, 4, 3, 2, 1$ is graphic. \begin{answer7}Using the Havel-Hakimi Theorem, we have $$7, 6, 5, 4, 4, 3, 2, 1\rightarrow$$ $$5, 4, 3, 3, 2, 1, 0\rightarrow$$ $$3, 2, 2, 1, 0, 0\rightarrow$$ $$1, 1, 0, 0\rightarrow$$ This last sequence is graphic. Hence the original sequence is graphic. \end{answer7} \end{pro} \begin{pro}[IMO 1964] Seventeen people correspond by mail with one another---each one with all the rest. In their letters only three different topics are discussed. Each pair of correspondents deals with only one of these topics. Prove that there at least three people who write to each other about the same topic. \begin{answer7} Choose a particular person of the group, say Charlie. He corresponds with sixteen others. By the Pigeonhole Principle, Charlie must write to at least six of the people of one topic, say topic I. If any pair of these six people corresponds on topic I, then Charlie and this pair do the trick, and we are done. Otherwise, these six correspond amongst themselves only on topics II or III. Choose a particular person from this group of six, say Eric. By the Pigeonhole Principle, there must be three of the five remaining that correspond with Eric in one of the topics, say topic II. If amongst these three there is a pair that corresponds with each other on topic II, then Eric and this pair correspond on topic II, and we are done. Otherwise, these three people only correspond with one another on topic III, and we are done again. \end{answer7} \end{pro} \begin{pro} If a given convex polyhedron has six vertices and twelve edges, prove that every face is a triangle. \begin{answer7} Let $x$ be the average number of edges per face. Then we must have $xf = 2e$. Hence $x = \dfrac{2e}{f} = \dfrac{24}{8} = 3$. Since no face can have fewer than three edges, every face must have exactly three edges. \end{answer7} \end{pro} \begin{pro} Prove, using induction, that the sequence $$n, n, n - 1, n - 1, \ldots , 4, 4, 3, 3, 2, 2, 1, 1$$is always graphic. \begin{answer7} The sequence $1, 1$ is clearly graphic. Assume that the sequence $$n - 1, n - 1, \ldots , 4, 4, 3, 3, 2, 2, 1, 1$$is graphic and add two vertices, $u, v.$ Join $v$ to one vertex of degree $n - 1$, one of degree of $n - 2,$, etc., one vertex of degree 1. Since $v$ is joined to $n - 1$ vertices, and $u$ so far is not joined to any vertex, we have a sequence $$n, n - 1, n - 1, n - 1, n - 2, n - 2, \ldots , 4, 4, 3, 3, 2, 2, 1, 0.$$Finally, join $u$ to $v$ to obtain the sequence $$n, n, n - 1, n - 1, \ldots , 4, 4, 3, 3, 2, 2, 1, 1.$$ \end{answer7} \end{pro} \begin{pro} Seven friends go on holidays. They decide that each will send a postcard to three of the others. Is it possible that every student receives postcards from precisely the three to whom he sent postcards? Prove your answer! \begin{answer7} The sequence $3, 3, 3, 3, 3, 3, 3$ is not graphic, as the number of vertices of odd degree is odd. Thus the given condition is not realisable. \end{answer7} \end{pro} \Closesolutionfile{discans} \section*{Answers}\addcontentsline{toc}{section}{Answers}\markright{Answers} {\small\input{discansC7}} \end{document}