General remarks
To make grading easier, please write legibly, leave plenty of
margins for comments, and have no ragged edges on the paper.
Even better if you write out each problem statement before its
solution and only write on one side of the paper.
Regarding the pigeonhole principle
Generally it is a good idea to
spell out clearly what is your set of pigeonholes, your set of
"pigeons", and the rule(s) for how you place pigeons in holes. I do
not mark off for not explicitly mentioning "pigeons" and "holes" so
long as it is crystal clear what the categories are and the placement
rule being used. But if you are vague about this or there is doubt
in my mind, expect to be marked off. The rule you use for placing
items should somehow relate to the properties you are trying to show
for items that land in the same pigeonhole.
Regarding the principle of induction
Unless you can make your
solution crystal clear otherwise, generally it is a good idea to
spell out clearly (1) what is (are) your base case(s); (2) your
induction hypothesis (assumption) for the inductive step; (3) what it
is you aim to prove in the inductive step, using the givens and the
induction hypothesis. I have been somewhat lenient about item (2)
for most problems, but more strict about it for those proofs that
require strong induction, i.e. require more than the immediately
preceding case, such as problem #23 on page 28 of the text.
Be careful to include the range of your variables when you state your
assumptions, givens, and goals, especially the range of your
induction variable in your induction hypothesis. Say your induction
variable is $n$. Your induction hypothesis typically assumes that
the proposition is true for some fixed value of n (say, n = N), not
for all positive vales of n; and you are trying to prove the case for
the next value of $n$ (say, n = N+1). If you are using strong
induction, your induction hypothesis typically assumes that the
proposition is true for values of n up to some fixed value (say, n <=
N), not for all positive values. And do not write "n = n + 1", which
is always false. Use a separate variable name, if necessary, to
distinguish between the induction variable and the fixed value
assumed in the induction hypothesis.
Regarding indirect proofs
Any direct proof can be turned into an
indirect proof, but such gratuitous use of indirect proofs is usually
not helpful, if only because they are more complicated and make it
easier to go astray (also slightly harder to read if not executed
well). I do not mark off for using indirect proofs. This is just a
word to the wise.
Regarding specific problems
Problem 1
Most students either got this (4 or 5 points) or they
didn't (0 points). The majority who got it wrong apparently don't
yet understand the difference between a necessary condition (which
the corollary proved in class provides) and a sufficient condition
(which the corollary does NOT provide!). A few failed for providing a
diagram with no verbal explanation.
Problem 2
Most students got this one right. Most points lost here
were due to not being explicit about pigeonholes.
Problem 3 (p11, #15)
I assigned 3 points to part (i) of the problem
and 2 points to part (ii). Some students apparently misunderstood
the problem, thinking that they were supposed to merely show that
there must be a composite number among the chosen subset of size 11.
For the others, several showed that some specific subsets of size 11
(for example, those that include all of the primes in the range) have
a pair with common divisor, but failed to give an argument for all
subsets of size 11. Others lost points by not being clear about what
their set of pigeonholes was, or about how numbers were associated to
the holes. Some forgot that the number 1 requires special
treatment. (General comment: The number 1 is not a prime number,
strictly speaking, though I did not mark off if they said so.) Some
gave the correct answer "No" to part (ii), but lost a point for
failing to give a clear counterexample.
Problem 4 (p11, #20)
Most lost points were due to failing to
mention key points: (1) The large triangle should be divided into 16
regular (equilateral) triangles, each of side 1/4; (2) the maximum
distance of any two points within a regular triangle is the length of
one side of the triangle.
Problem 5 (p28, #17)
Most students did pretty well on this
problem. Most students assumed without reference the identity $\sum_
{i=1}^n i = n(n+1)/2$. Since I know of no way to do the problem
inductively without using this identity, and since it is usually
already proven in class in most courses by the time they need to do
this exercise, I did not mark off for assuming it. Some students
did explicitly mention that they were using this identity (it would
be nice if it has a theorem or proposition number in the text, but
apparently the text does not discuss the identity). A few students
went the extra mile and proved
this identity in addition to the main proof.
However, a couple of students quoted another identity, namely $\sum_
{i=1}^n i^3 = n^2 (n+1)^2 /4$. This doubtless can be found in
certain reference texts, perhaps in the appendix of calculus texts,
etc, and might be regularly taught in some schools. However, to use
it here is tantamount to assuming the result, so I marked off for
using it -- unless they proved it in their solution.
Problem 6 (p28, #23)
Most students lost some points on this one,
mostly for violating the general remarks regarding (strong) induction
given above. I wanted to be sure that they knew they were using
strong induction, and so need the cases for both n and (n-1) in
order to prove the case for (n+1). Likewise, some did not realize
that they needed two base cases. Some students provided two base
cases, but would provide bases cases for, say, n=2 and n=3,
forgetting that they were supposed to prove the proposition for all
nonnegative values of n (including 0 and 1). Several students were
apparently suffering confusion between the formula that they were
being asked to prove (i.e. $a_n = n 3^n$) and the given recurrence
relation which defines the sequence.
Problem 7 (p28, #29)
Quite a few students lost points on this one.
Some were uncertain how to apply induction to a problem like this,
which asks for a geometric construction rather than an algebraic
formula. Some others did not find the general construction of using
line segments connecting midpoints of the sides of a triangle,
offering other constructions which might work for some triangles
(e.g. right triangles), but which I did not find convincing in the
general case. Perhaps most were marked off for not being clear or
explicit enough. For example, they might offer a diagram, but fail
to describe precisely how they make the construction such that it
ensures that the resulting triangles are all similar (e.g. lines
between midpoints). Some others gave a verbal description that was
unclear or garbled with no diagram to clarify. A few students
apparently did not understand the concept of similar triangles,
instead offering a construction that merely subdivided a triangle
into four smaller triangles of equal area, but not necessarily
similar to each other.
Few if any students mentioned that similarity of triangles is
transitive. I did not mark down for this, even though it is a key
fact.