General remark 1
In most combinatorics problems where one is counting the number of
k-digit numbers (decimal or otherwise)
satisfying certain constraints you should assume
that we are only counting nonnegative numbers unless instructed otherwise.
Similarly, when computing the number of integer divisors of a positive integer,
we only count the positive divisors. Remember that while 1 is not a prime
number, it is always a divisor of every positive integer.
General remark 2
In general, the number of ways to choose n groups of things from a
limited supply of resources is NOT n times the
number of ways to choose one group of things from the same supply of resources.
Problem 1
Most students got this right (64 * 49 arrangements).
Some students doubled this, interpreting the problem statement as
counting the _sequence_ of placements
(white rook first then black, versus black rook first then white).
I did not mark off for
this, as long as they explained what was their understanding of the problem.
But students should be aware that in general, when
counting rook arrangements and similar configurations of objects,
we are usually only counting the number of final arrangements,
disregarding the order in which the rooks or objects are placed.
Problem 4 (p51 #27)
Some students, operating from inertia from
problem 3 (#25) thought that this problem also required that all
digits be distinct. Some students also included counts for negative numbers
(i.e. a factor of 2), but I did not mark down for this.
Problem 6 (p51 #34)
This was the toughest problem of this homework set.
The answer is that a maximal (largest cardinality)
collection of subsets of [n] satisfying the condition
that the pairwise intersections of its elements is non-empty has cardinality
exactly 2^{n-1}. There are two parts to this problem:
One part is to to show that 2^{n-1} is a lower bound,
i.e. that there is at least one collection of subsets of this cardinality
satisfying the desired condition. I gave two points for showing this.
The easiest way to show this is to construct an explicit
example, and the easiest example is to choose all subsets of [n]
which contain a fixed number, say 1.
The other part is to show that 2^{n-1} is an upper bound,
i.e. that no collection of subsets satisfying the desired condition can
have larger cardinality. I gave three points for showing this,
since it is the more challenging part of the problem. The easiest
argument is to partition the powerset of [n] into complementary pairs
(i.e. pair a subset with its complement), which serve as
pigeonholes, and apply the pigeonhole principle.
Many students did only one part of the problem.
Some students were under the impression that the problem statement
was asking for a
collection of subsets for which there is exists an element of
[n] common to all subsets in the collection. (The problem asks only
that that the subsets meet pairwise, not collectively.)
Other students, though they understood the problem statement, were under the
impression that any such collection satisfying the condition must in fact
have an element of [n] common to all the subsets in the
collection anyway. This is false; consider n=3 and the collection
{ {1,2}, {1,3}, {2,3}, {1,2,3} }.
Problem 7 (p51, #44)
The answer is
(n!)^2, since we regard a collection of n
sophomore-junior-senior groups as being unordered. I
gave 3 points for (n!)^3, which would be the answer
if we regarded the collection as being ordered. I gave 2 points for n^3, which
is the number of ways to choose a single sophomore-junior-senior from the pool.