Corrected exercises: writing a mathematical proof (201-N11)

You recognize a direct proof by this: the hypothesis is RICH, it translates at once into an equation, and everything else is computation. Let $n$ and $m$ be two odd integers. By definition, there are integers $k$ and $j$ such that $n=2k+1$ and $m=2j+1$. Then $n+m=(2k+1)+(2j+1)=2k+2j+2=2(k+j+1)$. Since $k+j+1$ is an integer, $n+m$ is 2 times an integer: it is even. Assumed: $n$ and $m$ odd. Established: $n+m$ even. Check on one case: $n=7$ and $m=11$ give $k=3$, $j=5$, $k+j+1=9$ and $n+m=18=2\times 9$. The write-up pitfall, which costs half the marks on a question of this kind: concluding “so $n+m$ is even” without having exhibited the factor 2. A direct proof is finished only when the DEFINITION of the conclusion is satisfied word for word, here when the number appears in the form 2 times an integer. Writing “the sum of two odd numbers is obviously even” is worth no marks: obviousness is not a proof structure, and the marker grades the structure.

Same structure, a rich hypothesis once again. From $a \mid b$ we get an integer $k$ such that $b=ak$, and from $a \mid c$ an integer $l$ such that $c=al$. Watch the letter: $k$ and $l$ have no reason to be equal, and confusing them would amount to assuming $b=c$. Then $bu+cv=aku+alv=a(ku+lv)$. Since $ku+lv$ is an integer, we do have $a \mid (bu+cv)$. Check: $a=7$, $b=21$, $c=35$, $u=2$ and $v=-1$ give $bu+cv=42-35=7=7\times 1$. This result has a name, the linear combination lemma, and it is what makes Euclid's algorithm work: every common divisor of $b$ and $c$ also divides the remainder $b-qc$, which is a linear combination of $b$ and $c$. Euclid's algorithm comes back in exercise 7. Remember the move: a divisibility hypothesis is useless as long as it stays written with the vertical bar; it always translates into an equation with a named integer.

He has proved three particular cases, and nothing more. The statement is UNIVERSAL, it is about infinitely many pairs, and no finite list exhausts them. Three correct examples are not a proof: they are checks, and checking is good for only two things, convincing yourself before writing and catching yourself when you got a sign wrong. The point to remember is the complete asymmetry between proving and disproving. To DISPROVE a universal statement, a single counterexample is enough and settles the matter; that is the subject of exercise 5. To PROVE it, no number of examples is ever enough. It is exactly the difference between testing a program and proving it: a thousand passing tests do not establish that a program is correct, they establish that it is correct on a thousand inputs, and the input that breaks it is precisely the one nobody thought of.

Because using the same letter forces the two numbers to be equal. Writing $n=2k+1$ and $m=2k+1$ assumes $n=m$, so it only handles pairs of EQUAL odd numbers, such as $(7, 7)$, whereas the statement is about any two odd numbers. The computation that follows is correct, it gives $n+m=4k+2=2(2k+1)$, but its scope is wrong: it does not cover the pair $(3, 5)$. A marker takes away almost all the marks here, not for the computation but for the scope. The write-up rule: a fresh letter for each object you know nothing about, and two distinct objects never get the same letter until you have proved they are equal. It is the same mistake as calling both counters of two nested loops $i$, and it does the same kind of damage: the program runs, and it computes something other than what you think.

Between 1 and $10^{6}$ there are $500{,}000$ odd integers, so $500{,}000^{2}=2.5\times 10^{11}$ pairs, that is, 250 billion checks. At a billion tests per second, that takes about 250 seconds, a little over four minutes. And at the end of those four minutes the statement is still NOT proved: we will know that it is true for the odd numbers below a million, and we will know nothing about $10^{6}+1$. The proof of question a) takes three lines and covers every integer at once, including those that will never fit in any memory. That is the argument for learning, in a mathematics course for computer science, to write proofs rather than to test: the machine runs through cases, the proof quantifies over all of them. The practical corollary: when a statement is about an infinite set, looking for a proof structure is not a mathematician's luxury, it is the only way.

(1) $P \Rightarrow Q$ is the original statement. (2) $Q \Rightarrow P$ is its CONVERSE. (3) $\lnot Q \Rightarrow \lnot P$ is its CONTRAPOSITIVE. (4) $\lnot P \Rightarrow \lnot Q$ is the contrapositive of the converse (often called the inverse), so it is equivalent to (2). In words: (2) says “if $n$ is divisible by 3, then $n$ is divisible by 6”, which is FALSE, as $n=9$ shows in one line. (3) says “if $n$ is not divisible by 3, then $n$ is not divisible by 6”, which is true, and it is in fact the form in which it gets used: a number whose digit sum is not a multiple of 3 cannot be a multiple of 6, without any division at all. The exact name matters: on a test, writing “contrapositive” for $Q \Rightarrow P$ loses the marks for the whole question, even if the rest of the reasoning is correct, because what follows then rests on a statement that does not have the announced truth value.

See the table in the solution. On the four rows, in the order $(P,Q)=(1,1),(1,0),(0,1),(0,0)$: column (1) reads $1,0,1,1$; column (3) reads $1,0,1,1$; column (2) reads $1,1,0,1$. Columns (1) and (3) are identical row by row: a statement and its contrapositive are the SAME proposition, and that is what allows you to prove one in order to get the other. Column (2) differs from the other two on rows 2 and 3. The computation of row 2 is worth redoing by hand: $P=1$, $Q=0$ give $\lnot Q=1$ and $\lnot P=0$, so (3) is $1 \Rightarrow 0$, that is, 0, like (1). The table is the judge, and it is the only proof of equivalence that counts: no intuition drawn from ordinary language replaces the comparison of two columns.

Two propositions give $2^{2}=4$ rows. The converse differs from the statement on TWO of these four rows, exactly half, which is the best argument against the confusion: getting the form wrong is not a small imprecision, it is a one-in-two chance of reasoning about a false proposition. More generally, a table with $n$ propositions has $2^{n}$ rows, so 8 for three propositions and 32 for five. The point to remember for the rest of the course: when an announced equivalence looks doubtful, do not argue, write out the four rows; it takes thirty seconds and it settles the question.

The mistake is called affirming the converse. The student has proved $P \Rightarrow Q$ and concludes $Q \Rightarrow P$, which is never allowed. The smallest positive integer counterexample is $x=2$: it satisfies $x \geq 0$ and it is not a perfect square, since $1^{2}=1$ and $2^{2}=4$ bracket it strictly. What he was allowed to write is the contrapositive: if $x<0$, then $x$ is not a perfect square. This mistake is the most frequent of the whole chapter, and it does not show in the computations, it shows in the concluding sentence, which makes it treacherous on an exam. It has an exact counterpart in computing: from “if the input is valid then the test returns true”, nothing can be concluded from a test that returns true, whereas a test that returns false guarantees that the input was invalid.

Both (1) AND (2) would have to be true, because an equivalence is the conjunction of an implication and its converse. That is not the case here, since $n=9$ disproves (2). A true equivalence about divisibility by 6 does exist, though: $n$ is divisible by 6 if and only if $n$ is divisible by 2 AND by 3. The forward direction is immediate, and the reverse direction requires 2 and 3 to be relatively prime, which is Euclid's lemma (called Gauss's theorem in French textbooks). The numerical check: 9 is divisible by 3 but not by 2, so not by 6; 4 is divisible by 2 but not by 3, so not by 6; 12 is divisible by both, so by 6. The write-up lesson: “if and only if” is a promise of TWO proofs, and a test that announces it without supplying two loses the marks for the missing direction.

The negation of “$n$ is odd” is “$n$ is even”, and that is a rich hypothesis: it reads $n=2k$. The contrapositive to prove is therefore: if $n$ is even, then $3n+2$ is even. Proof: $n=2k$ gives $3n+2=6k+2=2(3k+1)$, which is 2 times an integer, so even. Since the contrapositive is equivalent to the statement, the statement is proved. Check: $n=4$ gives $3n+2=14$, even, as expected; $n=5$ gives 17, odd, and 5 is indeed odd. Compare with the direct route: starting from “$3n+2$ is odd” gives $3n+2=2k+1$, so $3n=2k-1$, and you then have to argue that $3n$ odd forces $n$ odd, which is a second statement of the same type, not proved. The direct route goes around in circles, the contrapositive takes one line. This contrast is exactly the criterion for choosing.

The conclusion is an OR, and the negation of an OR is an AND: “$x \leq 31$ AND $y \leq 31$”. That is where everything happens, because this negation is rich, it gives two usable upper bounds, whereas the original conclusion, an OR, cannot be manipulated. Contrapositive to prove: if $x \leq 31$ and $y \leq 31$, then $xy \leq 1{,}000$. Proof: since $x$ and $y$ are positive, $xy \leq 31 \times 31 = 961 \leq 1{,}000$. So the statement is true. The bound is sharp: $31^{2}=961$ fits, and $32^{2}=1{,}024$ does exceed 1,000, which shows that the threshold 31 is not chosen at random. The pitfall, penalized on every exam: writing the negation as “$x \leq 31$ or $y \leq 31$”. With that or, the pair $(10, 200)$ satisfies the hypothesis and gives $xy=2{,}000$, the proof collapses and the student wrongly concludes that the statement is false.

Negation of the conclusion: $n$ is odd, so $n=2k+1$, a rich hypothesis again. Contrapositive: if $n$ is odd, then $n^{3}+5$ is even. Proof: $n$ odd makes $n^{3}=n \times n \times n$ odd, since a product of odd numbers is odd, then $n^{3}+5$ is the sum of two odd numbers, so even by exercise 1. Check: $n=3$ gives $27+5=32$, even. To spell everything out, $n=2k+1$ gives $n^{3}=8k^{3}+12k^{2}+6k+1=2(4k^{3}+6k^{2}+3k)+1$, then $n^{3}+5=2(4k^{3}+6k^{2}+3k+3)$. The direct route would require starting from “$n^{3}+5$ odd”, so from “$n^{3}$ even”, and proving that an even cube forces $n$ even, which is again a statement of the same family: you would be off on another contrapositive, one step further along.

In all three cases, the starting hypothesis is POOR: it is about a compound expression ($3n+2$, $xy$, $n^{3}+5$) and not about the object $n$ itself, so translating it into an equation gives nothing usable. The conclusion, on the contrary, is directly about $n$, or negates into an AND of two upper bounds. The criterion for choosing can therefore be stated as follows: compare the RICHNESS of $P$ and that of $\lnot Q$, and prove starting from the richer of the two. Three signals almost always announce a contrapositive: the conclusion is a negation, the conclusion is an OR, or the conclusion is about the basic object while the hypothesis is about an expression built from it.

They differ in what you assume and in what you are looking for. In the contrapositive, you assume $\lnot Q$ ALONE and try to establish $\lnot P$: nothing false is ever assumed, you prove a statement equivalent to the original one, and the proof is as solid as a direct proof. In a proof by contradiction, you assume $P$ AND $\lnot Q$, that is, the complete negation of the implication, and you look for any contradiction, not necessarily $\lnot P$. Contradiction is therefore more permissive, and that is both its strength, since it applies to statements that are not implications, and its weakness: you reason in a false world, where any computational error produces a contradiction that looks like a conclusion. The rule of use: if the contrapositive is enough, prefer it, it is shorter and safer; keep contradiction for statements of nonexistence, uniqueness and irrationality, which are the subject of exercise 4.

You assume $P$ AND $\lnot Q$, that is, exactly the negation of the implication, since $\lnot(P \Rightarrow Q)$ is $P \land \lnot Q$. So you keep the hypothesis of the statement, which is the point students forget: in a proof by contradiction you do not throw $P$ away, you add it to $\lnot Q$ and so have TWO assumptions instead of one, which explains why contradiction succeeds where the contrapositive, which only has $\lnot Q$, sometimes fails. Then you look for any contradiction at all: a number that is both even and odd, a fraction in lowest terms whose numerator and denominator are both even, an integer strictly between two consecutive integers. The required write-up has three markers: the announcement “suppose, for the sake of contradiction, that”, the contradiction explicitly named when it arrives, and the conclusion that restates the original statement. A test that finds the contradiction and stops there loses the marks for the conclusion.

Suppose, for the sake of contradiction, that $\sqrt{2}$ is rational. It can then be written $\sqrt{2}=\frac{a}{b}$ with $a$ and $b$ integers, $b$ nonzero, and the fraction chosen in LOWEST TERMS, which is always possible by simplifying. Squaring, $2=\frac{a^{2}}{b^{2}}$, so $a^{2}=2b^{2}$: $a^{2}$ is even, so $a$ is even, by contraposition, since $a$ odd would make $a^{2}$ odd (the move of exercise 3), and we write $a=2c$. Then $4c^{2}=2b^{2}$, so $b^{2}=2c^{2}$, so $b$ is even for the same reason. The assumption contradicted is precisely the LOWEST TERMS: $a$ and $b$ are both even, so both divisible by 2, whereas they were assumed to have no common factor. So $\sqrt{2}$ is irrational. The classic pitfall is forgetting to take the fraction in lowest terms: without that precaution, getting “$a$ and $b$ even” is no contradiction at all, it is an ordinary piece of information, and the proof proves nothing. Check of the order of magnitude: $\sqrt{2}\approx 1.41421$, and $\frac{99}{70}\approx 1.414286$ is an excellent approximation of it, but only an approximation.

Suppose, for the sake of contradiction, that $\log_{2} 3=\frac{a}{b}$ with $a$ and $b$ positive integers, which is legitimate since $\log_{2} 3>1>0$. By definition of the base-2 logarithm, $2^{a/b}=3$, so raising to the power $b$: $2^{a}=3^{b}$. The left side is even, since $a \geq 1$; the right side is odd, since 3 is odd and a product of odd numbers is odd. An integer cannot be both even and odd: a contradiction. So $\log_{2} 3$ is irrational. Its value is $\log_{2} 3 \approx 1.58$, and it is the average number of bits needed to encode a symbol taken from an alphabet of three equally likely letters. Irrationality then says something concrete: no fixed-length code putting $b$ symbols on $a$ bits can be exactly optimal, whatever grouping is chosen; you get closer without ever getting there. The write-up pitfall: forgetting the condition $a \geq 1$, without which $2^{a}$ could equal 1, which is odd, and the contradiction disappears.

R2 is the only valid one. R1 makes a substantive mistake: nothing guarantees that $N$ is prime, and the given example proves it, $2\times 3\times 5\times 7\times 11\times 13+1=30{,}031=59\times 509$ is not prime. What the proof obtains is more modest and sufficient: $N$ has a prime divisor, and that divisor is missing from the list. In the example, 59 and 509 are indeed two primes absent from the list 2, 3, 5, 7, 11, 13. R3 is not a proof at all, it is an assertion: infinitely many integers do not imply infinitely many elements in a subset; there are infinitely many integers and yet only one even prime. The proofreading lesson: in a proof by contradiction, the contradiction must be EXHIBITED, not announced, and every step that asserts an existence must say which theorem it comes from, here the fact that every integer greater than 1 has a prime divisor.

No, and that is even its main advantage over the contrapositive, which requires an implication. None of the statements b), c) and d) is an implication: “$\sqrt{2}$ is irrational” is a negation, “there are infinitely many prime numbers” is an existence claim. Contradiction applies to any statement $A$, since all it asks is that you can write $\lnot A$. That is why you recognize it from key words in the statement: there is no, none, at most one, is unique, is irrational, is impossible. They all designate a proposition whose negation is an EXISTENCE, hence a rich hypothesis: assuming an object exists lets you name it and compute with it, whereas the original statement, which denies, gives you nothing to manipulate. It is the same criterion as in exercise 3, applied to a statement that is not an implication.

Every integer is even or odd: that is two cases, and they exhaust the integers. Case 1, $n=2k$: then $n^{2}=4k^{2}$, so $n^{2} \equiv 0 \pmod 4$. Case 2, $n=2k+1$: then $n^{2}=4k^{2}+4k+1=4(k^{2}+k)+1$, so $n^{2} \equiv 1 \pmod 4$. In both cases the remainder is 0 or 1, it is NEVER 3. An immediate consequence, by contraposition: an integer of the form $4k+3$, whose remainder modulo 4 is 3, cannot be a perfect square. Check: $7=4\times 1+3$, and $2^{2}=4$, $3^{2}=9$ bracket it; $11=4\times 2+3$, bracketed by 9 and 16; $15=4\times 3+3$, bracketed by 9 and 16. This result is the standard tool for showing that an equation has no integer solution: look at the possible remainders of each side, and if the two sets do not meet, the equation is impossible. The proof by cases is the engine here, and the number of cases is fixed by the modulus chosen.

The list must be EXHAUSTIVE: the union of the cases must give back the whole domain $D$, otherwise the statement remains unproved on whatever is missing. It is the most frequent mistake, and it goes unnoticed because each case, taken on its own, is correct. On the other hand, the cases have no need to be pairwise disjoint: an overlap costs nothing, it only makes you prove the same thing twice on the intersection. So you can handle “$x \leq 0$” then “$x \geq 0$” without worrying about zero being counted twice, whereas handling “$x<0$” then “$x>0$” leaves a gap and ruins the proof. On a test, the sentence that earns the marks is the one that checks exhaustiveness out loud, such as “every integer is even or odd, so the two cases above cover all integers”.

Let $x=\sqrt{2}^{\sqrt{2}}$ and discuss two cases, which exhaust the possibilities. Case 1, $x$ is rational: then the pair $a=b=\sqrt{2}$ works, since $\sqrt{2}$ is irrational by exercise 4. Case 2, $x$ is irrational: then take $a=x$ and $b=\sqrt{2}$, both irrational; we compute $a^{b}=\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=\sqrt{2}^{\,\sqrt{2}\times\sqrt{2}}=\sqrt{2}^{2}=2$, which is rational. In both cases a pair works, so such a pair exists. What the proof does NOT tell you: WHICH of the two pairs works, because it does not settle whether $x$ is rational. It is a NONCONSTRUCTIVE existence proof, and it is exactly the profile of the pigeonhole principle in exercise 6, which guarantees that a box contains two objects without ever saying which box. Remember this kinship: an unsettled proof by cases and the pigeonhole principle are the two ways of proving an existence without exhibiting it.

A single counterexample is enough, and it is given: $F_{5}=4{,}294{,}967{,}297=641\times 6{,}700{,}417$ is not prime, so the claim “every Fermat number is prime” is false. Fermat had checked FIVE cases, $F_{0}=3$, $F_{1}=5$, $F_{2}=17$, $F_{3}=257$ and $F_{4}=65{,}537$, all prime, and conjectured the rest. Euler found the factor 641 in 1732, some ninety years after Fermat stated his conjecture in 1640. The story is the best argument against reckless generalization: five correct cases in a row, on numbers that grow very fast, guarantee nothing. The expected write-up for a disproof: give the value, check that it satisfies the hypothesis, check that it violates the conclusion, and conclude that the universal statement is false. Three lines, and no other technique is needed: it is the only case where a numerical value on its own constitutes a complete proof.

Modulo 3, there are THREE cases, the remainders 0, 1 and 2, and modulo $n$ there are $n$, the remainders 0 to $n-1$: it is precisely the division algorithm that guarantees exhaustiveness, since every integer has one and only one remainder. The split “even or odd” is the case $n=2$, so it is always legitimate, and that is in fact why it is used without justification. Choosing the modulus is a strategic decision, not a matter of taste: take the smallest one that separates what you want to separate. For question a), modulo 4 is enough and gives only two remainder values, whereas modulo 8 would give three for a barely finer result. The practical rule: the larger the modulus, the more precise the information, and the longer the write-up; stop at the first one that settles the question.

Simple form: if $n+1$ objects are placed in $n$ boxes, then at least one box contains at least two objects. Proof by contradiction, and that is the first point of the question: suppose no box contains two objects, that is, each box contains at most one. Then the total number of objects is at most $1+1+\cdots+1=n$, the sum running over the $n$ boxes. But this total is $n+1$, and $n+1>n$: a contradiction. So at least one box contains two objects. Remember the structure, it is the skeleton of all the following questions: negate the conclusion, the negation imposes an UPPER BOUND on each box, add up these bounds and end up with a total that is too small. The principle says nothing more, and above all it does not say WHICH box: it is a nonconstructive existence, exactly like the unsettled proof by cases of exercise 5.

Generalized form: if $m$ objects are placed in $n$ boxes, then at least one box contains at least $\lceil m/n \rceil$ objects, where $\lceil \cdot \rceil$ denotes the ceiling function. Same proof: if every box contained at most $\lceil m/n \rceil - 1$ objects, the total would be at most $n\left(\lceil m/n \rceil - 1\right)$, which is strictly less than $m$ since $\lceil m/n \rceil < \frac{m}{n}+1$. A contradiction. Application: $\lceil 2{,}000/30 \rceil = \lceil 66.67 \rceil = 67$, so at least one folder contains 67 files or more. The pitfall, which costs a mark every time: writing 66, that is, taking the FLOOR, or worse the average $66.67$, which is the number of files in no folder at all. The bound is sharp, in the sense that a distribution exists with one folder at 67 and the others at 66 or 67: nothing stronger can be claimed.

The objects are the frames and the boxes are the possible checksums. A 16-bit checksum takes $2^{16}=65{,}536$ values, whereas there are $2^{1000}$ frames of 1,000 bits, an astronomically larger number. Since $2^{1000}>2^{16}$, the pigeonhole principle applies: at least two distinct frames carry the same checksum. For the guarantee, $65{,}537$ distinct frames are enough, that is, $2^{16}+1$: it is the smallest number that forces a collision, and with $65{,}536$ frames nothing is forced, since a one-to-one assignment remains conceivable. The practical consequence is the point to remember: a checksum NEVER proves that a frame is intact, it only makes it unlikely that an error goes unnoticed. No choice of checksum function changes that; it is a counting result, not a matter of algorithm quality.

The objects are the nonempty subsets of the 10 chosen integers: there are $2^{10}-1=1{,}023$ of them. The boxes are the possible sums. The smallest sum is at least 1, and the largest is obtained with the ten largest integers available, $91+92+\cdots+100=955$. So there are at most 955 possible sums for $1{,}023$ subsets: two distinct subsets have the same sum. If these two subsets overlap, remove their intersection from both, which takes away the same amount on each side, and you get two DISJOINT subsets with the same sum, both nonempty since the sums were equal and the sets distinct. The strength of the result is that it holds for ANY choice of ten integers: no way to cheat by choosing them cleverly, even though no example would make it obvious.

367 students are needed: the boxes are the 366 possible dates, February 29 included, and $366+1=367$ objects force a coincidence. The two results do not contradict each other at all; they do not answer the same question. The pigeonhole principle gives a worst-case CERTAINTY: with 367, no arrangement avoids the coincidence. The probability computation says that with 23 people the coincidence already has more than a one-in-two chance of happening, which is a statement about FREQUENCY and leaves entirely possible a group of 300 people whose dates are all distinct. Keeping the two registers apart is one of the most useful reflexes of the course: forced and probable are two different words, and confusing them leads to false sentences about computer security.

Statements (i) and (iii) call for induction, and they alone. The signal is twofold: the statement is INDEXED by an integer $n$, and going from rank $n$ to rank $n+1$ takes a small computation, here adding $n+1$ to the sum, there factoring $7^{n+1}-1=7(7^{n}-1)+6$. Statement (ii) is an irrationality, so a contradiction, and nothing in it is indexed by an integer. Statement (iv) is an existence claim without construction: it is a pigeonhole case, 13 objects for 12 possible remainders. Statement (v) is an implication whose conclusion is easy to negate: it is a contrapositive, if $n$ is odd then $n^{2}$ is odd, so not divisible by 4. This sorting is the central move of the chapter, and it is done by reading the FORM of the statement, never its subject: four of these five statements are about integers, and they call for three different structures.

Structure 1, induction: at rank 1, $1=1^{2}$; assuming $1+3+\cdots+(2n-1)=n^{2}$, add the next term $2n+1$ to get $n^{2}+2n+1=(n+1)^{2}$, which is the statement at rank $n+1$. Structure 2, a direct proof by regrouping: the sum of the first $n$ odd numbers is $\sum_{k=1}^{n}(2k-1)=2\times\frac{n(n+1)}{2}-n=n^{2}+n-n=n^{2}$. The second one takes one line to write, provided you know the sum of the first integers. Check for $n=6$: $1+3+5+7+9+11=36=6^{2}$. The lesson is the thread of the set: induction is not compulsory just because a statement is about all integers, it is one choice among others, and it is often the longer of the two paths. Keep it for statements whose rank $n+1$ can ONLY be computed from rank $n$, typically recursively defined sequences, handled in the chapter devoted to them.

The remainder $r=a \bmod b$ satisfies $0 \leq r < b$: it is a natural number and it is STRICTLY less than the previous $b$. The sequence of successive remainders is therefore a strictly decreasing sequence of natural numbers. Such a sequence cannot be infinite: the set of its values would be a nonempty subset of $\mathbb{N}$ with no least element, which contradicts the well-ordering principle. So the algorithm stops after finitely many steps. Run: $1{,}071=2\times 462+147$, then $462=3\times 147+21$, then $147=7\times 21+0$. Three divisions, and the last nonzero remainder, 21, is the GCD. Check: $1{,}071=21\times 51$ and $462=21\times 22$, and $51$ and $22$ are relatively prime. The decreasing quantity has a name, the variant, and exhibiting it is the whole termination proof: that is what is asked for on a test, not a sentence such as “clearly it ends”.

No, and that is precisely where the difference between $\mathbb{N}$ and $\mathbb{Q}$ comes into play. The sequence $\frac{1}{2^{n}}$ is strictly decreasing, strictly positive, and yet infinite: it never stops. So the termination argument does not rest on the decrease, it rests on the fact that the variant lives in $\mathbb{N}$, where there is no room for an infinite descent. The practical consequence in programming: to prove that a loop terminates, exhibit a positive INTEGER quantity that strictly decreases at each iteration. A decreasing real quantity proves nothing, and it is the source of a classic family of infinite loops, the ones that wait for a floating-point number to reach exactly zero.

It hides in the sentence “the fraction can always be chosen in lowest terms”. That sentence is a consequence of well-ordering: among all the ways of writing the same number as $\frac{a}{b}$ with $b>0$, there is one whose denominator is the SMALLEST, and that is the one you take. You can in fact write the proof without ever mentioning lowest terms; this is infinite descent: if $\sqrt{2}=\frac{a}{b}$, you build $\frac{c}{d}$ with $d<b$ representing the same number, then start again, and you get an infinite strictly decreasing sequence of natural numbers, which well-ordering forbids. Induction, well-ordering and infinite descent are three formulations of the same principle, and being able to move from one to another is what lets you recognize an induction in disguise in a statement that does not look like one.

FALSE, and it is the costliest confusion of the chapter. The contrapositive of $P \Rightarrow Q$ is $\lnot Q \Rightarrow \lnot P$; its converse is $Q \Rightarrow P$. The first ALWAYS has the same truth value as the statement, the second has no link with it: on the four rows of the truth table in exercise 2, the converse differs from the statement on two rows, one in two. An example that settles it: “if $n$ is divisible by 6 then $n$ is divisible by 3” is true, its contrapositive “if $n$ is not divisible by 3 then $n$ is not divisible by 6” is true as well, and its converse “if $n$ is divisible by 3 then $n$ is divisible by 6” is false, as $n=9$ shows. Correct statement: the contrapositive of a statement is equivalent to it; its converse is an independent proposition that needs its own proof.

FALSE, and no choice of example changes that. A universal statement covers infinitely many cases, and a finite list never exhausts them. The story of the Fermat numbers in exercise 5 shows it starkly: five cases checked, $F_{0}$ to $F_{4}$, all prime, and the sixth, $F_{5}=4{,}294{,}967{,}297=641\times 6{,}700{,}417$, is composite. The asymmetry between the two directions is total: to DISPROVE a universal statement, a single counterexample is enough and closes the question; to PROVE it, you need a structure valid for all cases at once. Correct statement: an example illustrates, it does not prove, except for an EXISTENCE statement, where exhibiting an object really is a complete proof.

FALSE, even though both begin by assuming the conclusion is false. The contrapositive assumes $\lnot Q$ ALONE and aims for exactly $\lnot P$: nothing false is assumed, and it applies only to implications. Contradiction assumes $P$ AND $\lnot Q$, hence the complete negation of the implication, and aims for any contradiction; it applies to any statement, including those that are not implications, such as the irrationality of $\sqrt{2}$ or the infinitude of the primes. Correct statement: the contrapositive is a very disciplined special case, contradiction is more general and more dangerous, since you reason in a false world where the slightest computational error produces a contradiction that looks like a conclusion.

FALSE: induction does NOT prove the base case, it REQUIRES it. Its two steps are the base case, where you check the property at the first rank, and the inductive step, where you prove that rank $n$ implies rank $n+1$. The inductive step alone proves nothing: the property “$n=n+1$” passes from each rank to the next, since $n=n+1$ yields $n+1=n+2$, and it is false at every rank, for lack of a base case. Conversely, a base case alone proves only one case. Correct statement: induction proves the statement at every rank from the verified base case on, and that base case must be established separately. The chapter of this course devoted to induction details both pitfalls, along with strong induction and recursively defined sequences.

FALSE, and that is precisely what the principle does NOT say. The pigeonhole principle guarantees the EXISTENCE of a crowded box, without ever designating which one or exhibiting the two objects: it is a nonconstructive existence proof, of the same type as the unsettled proof by cases of exercise 5. In the checksum question, we know that two 1,000-bit frames share a 16-bit checksum, and that certainty provides no means of finding such a pair. That is why computer security relies on the DIFFICULTY of exhibiting a collision and not on its absence, which is impossible. Correct statement: the pigeonhole principle asserts that some box contains at least two objects, and it gives neither the box nor the objects.

Each bit takes two values and the choices are independent, so there are $2^{10}=1{,}024$ sequences of 10 bits. That is the multiplication principle, and it is the only counting computation in the whole problem.

There is $2^{0}=1$ sequence of length 0, the empty sequence, then $2^{1}=2$ sequences of length 1, and so on up to $2^{9}=512$ sequences of length 9. The total is $1+2+4+\cdots+512=2^{10}-1=1{,}023$, by the sum of a geometric sequence with ratio 2. This number deserves a look: all the sequences shorter than 10 bits, ALL lengths combined, are fewer than the 10-bit sequences alone. It is this one-unit inequality that will do all the work, and it is no accident of the example: $2^{0}+\cdots+2^{n-1}=2^{n}-1$ for every $n$.

“Lossless” means that decompression recovers the original file, so two DIFFERENT files cannot give the same compressed version: otherwise the decompressor, faced with that compressed version, would not know which of the two to return. The function that sends a file to its compressed version is therefore INJECTIVE. That is the whole translation of the problem, and it is the step students skip: the word “injective” does not appear in the company's claim, it has to be produced by reading. Without it, the counts of questions a) and b) are useless.

Suppose, for the sake of contradiction, that the announced compressor exists. It sends each of the $1{,}024$ sequences of 10 bits to a strictly shorter sequence, so one of length between 0 and 9, and there are $1{,}023$ of those. We place $1{,}024$ objects in $1{,}023$ boxes: by the pigeonhole principle, two distinct 10-bit sequences receive the same compressed version. This contradicts the injectivity established in c), so the announced compressor does not exist. The structures used are therefore TWO, nested: a proof by contradiction whose contradiction is produced by the pigeonhole principle, the whole thing resting on a count. It is the most frequent pattern of impossibility proofs in computer science, and it is worth remembering as is: assume the object, count what it would have to tell apart, and observe that there are more objects than places.

If such a compressor existed, applying it $n$ times would reduce any 10-bit file to a length of at most $10-n$ bits, so after ten applications to 0 bits, the empty sequence. All the files would have become the same, and no decompression could tell them apart: it is the same contradiction, in a more spectacular form. Real compressors work because they do NOT claim to shrink every file: they shrink the ones that carry structure, text, images, server logs, and they ENLARGE the others by a few bits, which you can see by compressing an already compressed file or a sequence of random bits. So the theorem does not say that compression is useless, it says that it is a trade-off: what is gained on frequent files is lost on rare files, and the average gain depends entirely on the actual distribution of files, never on the algorithm alone.

A hexadecimal digit takes 16 values, so three digits give $16^{3}=4{,}096$ distinct IDs. A repetition becomes certain from $4{,}097$ sessions on, by the simple form of the pigeonhole principle. With $5{,}000$ sessions, the generalized form confirms it, without giving more: at least one ID is carried by $\lceil 5{,}000/4{,}096 \rceil = 2$ sessions. This 2 is indeed the ceiling of $1.22$, and not 1: that is why rounding is never to the nearest integer in this kind of question. Note that the conclusion looks weak, only two sessions, whereas a probability computation would predict a very large number of collisions; but it has a quality that probability lacks: it is CERTAIN.

R4 is the only valid one. R1 is CIRCULAR: it begins by assuming what it wants to prove, “since two sessions have the same ID”, so its conclusion rests on nothing. It is the hardest mistake to spot when proofreading, because the text reads very smoothly. R2 reasons BY EXAMPLE: a simulation exhibits one case, and one case does not prove a statement about every possible day; besides, if the simulation had found nothing, that would not have disproved anything either. R3 proves the CONVERSE: the implication it establishes goes from the collision to the count, whereas it should go from the count to the collision, and the sentence “that is indeed the case here” then applies the implication backwards, which is the mistake of affirming the converse from exercise 2. Three STRUCTURE mistakes, no computational mistake: that is the chapter in a nutshell.

Expected write-up. First element, the starting point: the IDs are written with 3 hexadecimal digits, so there are $16^{3}=4{,}096$ of them, and the server served $5{,}000$ sessions. Second element, the technique, named: apply the pigeonhole principle, the objects being the sessions and the boxes the possible IDs. Third element, the chain of reasoning: since $5{,}000>4{,}096$, there are strictly more objects than boxes, so at least one box contains two objects. Fourth element, the conclusion that restates the claim: at least two sessions received the same ID. Four sentences, and each one is worth marks. What does NOT count as a written proof: a sequence of correct computations without the sentence that names the technique, and a conclusion that stops at “so a collision” without coming back to the sessions of the statement.

No, it does not remove the risk, it only removes the CERTAINTY. With 4 hexadecimal digits there are $16^{4}=65{,}536$ IDs for $5{,}000$ sessions, so more boxes than objects, and the principle no longer applies: it concludes nothing. But concluding nothing is not concluding that there is no collision. Since the IDs are drawn at random, a collision remains possible, and the birthday paradox computation, covered in the counting and probability set of the course, even shows that it is likely long before the number of IDs is reached. It is the most common misreading of the pigeonhole principle: it gives a SUFFICIENT condition for a collision, never a necessary one, and its negation says nothing.

You would have to stop drawing at random and assign the IDs with a COUNTER that increments, or with any process that never assigns the same value twice. The proof structure would then change completely: you would no longer count, you would prove that the function from sessions to IDs is injective, which is done by a direct proof, or by contrapositive in the form “if two sessions have the same ID, then they have the same counter number, so they are the same session”. You would gain the guarantee and lose the unpredictability, which is exactly what you want for a session ID: a counter can be guessed, and guessing another visitor's ID is a security hole. The real engineering answer is therefore to lengthen the ID until a collision becomes negligible, accepting that it remains possible, which is exactly what this chapter teaches you to say correctly.