From ecroot@math.gatech.edu Thu Nov 12 12:23:43 2009
Date: Thu, 12 Nov 2009 12:23:42 -0500 (EST)
From: Ernie Croot <ecroot@math.gatech.edu>
To: Blackili Rudi Milhose <blacki@math.gatech.edu>
Subject: Re: grader...


Dear Blackili,

I have decided to have you only grade 2 problems for accuracy, and
the rest for effort.

The two problems to be graded for accuracy, out of 20 points each (so,
60 points left for effort), are the following:  First, go to the
course webpage at

http://www.math.gatech.edu/~ecroot/3012/3012.html

And then look where it says ``Homework 5''.  There should be 2 links
here -- these are the first and second parts of the assignment.

Grade problem 1 from the first part of HW 5, and problem 2 on the
second part of HW 5, for accuracy.

Aim for a course median of at least 80.

----

Solutions.


Here is the solution to problem 1 (in case you need it):  The set

A1 x B1  union A1 x B2 = A1 x (B1 union B2); likewise,
A2 x B1  union A2 x B2 = A2 x (B_1 union B2).

But now

A1 x (B1 union B2)   union   A2 x (B1 union B2)
= (A1 union A2) x (B1 union B2).

And, the size of this cross product is clearly

|A1 union A2| * |B1 union B2|.

Now, applying inclusion-exclusion to each of these factors, we get

|A1 union A2| = |A1| + |A2| - |A1 intersect A2|
|B1 union B2| = |B1| + |B2| - |B1 intersect B2|.

ANd we are done.  (This problem is designed to test manipulations
and properties of cross products -- several different properties
were required to solve it.)



Solution to problem 2 in the second set:  First, suppose that A has
only n elements.  Then, there are only n! bijections

f : A -> A,

since bijections can be interpreted as permutations of the set A.
So, if phi is any such bijection, then since the composition of
two bijections is again a bijection, this implies that all

phi, phi^2, phi^3, ...

are bijections.  And since there are only n! bijections f : A -> A,
we must have that

phi^i = phi^j, for some i,j with i < j;

that is, for each x in A we have

(phi^i)(x) = (phi^j)(x).

Now, since phi is a bijection it is invertible, with inverse phi^{-1}; and
so, we have that upon composing with phi^{-i} on the left on both sides,
we get

x = (phi^{-i} compose phi^i)(x) = (phi^{-i} compose phi^j)(x), for all x.

So,

phi^{j-i} is the identity map, since it sends x -> x, for all x in A.

We are now done.  (This problem was designed to test knowledge of
the pigeonhole principle, along with various properties of maps, such
as bijections from a finite set to itself.)


Best,

Ernie