Here are some answers and comments regarding the 2008 putnam exam.
I thought the test was easier than usual, but I don't have convincing
answers to A6 and B3.

A1. This is essentially cohomology -- we must show that every 2-cocycle
is a 2-coboundary!

Using x=y=z=0  we see f(0,0)=0.
THen using y=z=0 we see f(0,x)=-f(x,0).
Then using z=0 we see f(x,y) = f(x,0) - f(y,0).
So g(x) = f(x,0)  does the trick.

(Remark: for any continuous  f : R^1 -> R^1,  f(x,y) = integral_x^y h(t)dt
is an example of such an   f ; we can use  g = any antiderivative of  h
in this case.)

A2. Barbara has a winning strategy. She can split the 2008 rows into 1004
pairs, and then whenever  Alan  places a number in the i-th entry of one
of the rows, Barbara can place the same number in the i-th entry of the
row paired with it. At some point Alan will fill in the last entry of a
row, and then Barbara will make the paired row be identical to that one,
making the determinant zero.

Obviously this works when the number of rows is even. A similar strategy
gives Alan the advantage when the number of rows is odd. (He can use his
first move to put a number in the center of the one unpaired row.)

A3. The process will stop when the sequence consists of numbers that
each divide the next. 

For each prime  p  dividing any of the  a_i,  let  p^{e_i}  be the largest
power of  p  dividing  a_i.  Then carrying out the process once has
the effect of replacing  e_j  with  min(e_j, e_k)  and replacing  e_k
with  max(e_j, e_k). If we count the number of inversions (i.e. pairs (j,k)
with  j<k but e_j >= e_k)  then we see that the process has not introduced
any new inversions, at has removed at least one inversion relative to at
least one prime  p.  So the process must stop eventually (and indeed will
only stop when the number of inversions is zero, i.e. each a_i divides a_{i+1})

Effectively, the complete process sorts the  e_i  for all primes  p  at once.

I don't think this is the slickest way to word the answer, though!

A4. The series diverges by the Integral Test. The function  f  is increasing
on [1,e] and then on [e, oo)  since  x, ln, and f  are positive and increasing.
Therefore  1/f  is decreasing, and  sum(1/f(n)) is at least as large as
integral_1^oo 1/f(x) dx.  (Indeed we can make this statement for bounded
integrals and use this to estimate the partial sums of our series, to show
the series diverges, but showing the infinite integral diverges will convey
the same information.)

Now define  e_0 = 1 , e_1 = e, and for n>0 let e_{n+1} = e^{e_n} . Then 
if  x  is in  [e_n, e_{n+1}],  we have  ln(x)  in  [e_{n-1}, e_n], and so
by induction on   n  we conclude  f(x) = x ln(x) ln(ln(x)) ... ln^n(x) .
But then on this interval,  integral dx/f(x)  = ln^{n+1}(x)  and so the 
definite integral across the interval is  ln^{n+1} (e_{n+1}) - ln^{n+1} (e_n)
= 1 - 0 = 1. It follows that the integral across the real line is infinite,
so the sum diverges.

A5. There are not many possibilities for these polynomials  f  and  g. 
The points  Z_k = exp(2 pi i k / n)  in the complex plane are the vertices
of such a polygon; allowing for rotations, translations, and scalings
shows that the points  W_k = f(k)+ig(k)  must be  a Z_k + b  for some fixed
complex numbers  a (nonzero) and  b. (No need to discuss reflections -- the 
original polygon is symmetric w.r.t. a line.) So if both  f  and  g  were
polynomials of degree  n-2  or less, then  W  would be a complex-valued
polynomial in one variable whose values at  k = 1, 2, ..., n  equal a Z_k + b .

Writing  W = sum c_j X^j, then the coefficients  c_j  satisfy the  n
equations    sum c_j k^j = a Z_k + b  for k = 1, 2, ..., n, i.e. the
column vector  c = (c_0, ..., c_{n-2})  satisfies the single matrix equation
   V c = u
where  V  is the vandermonde matrix  V_{ij} = i^j  and  u  is the column
vector with  u_k = a Z_k + b . Now, if we let  w  be the row vector whose
entries are the coefficients of  (1-X)^{n-1} (i.e. certain binomial 
coefficients) then the entries of  w V  are of the form
   sum_{k=0}^{n-1} (-1)^k binomial(n-1, k) (k+1)^j
which are all zero, i.e.  w  is in the left-annihilator of  V.
It follows that we would have
   0 = w V c = w u 
But  w u = (a Z_0 + b) -(n-1)(a Z_1 + b) + ...
         = a (Z_0 - (n-1) Z_1 + ... ) + b ( 1 - 1)^{n-1} .
Since  Z_k = zeta^k  for  zeta = exp(2 pi i / n), the first sum is
a ( 1 - zeta )^{n-1}, which means  w u  is not zero, and so  u  is not
a multiple of  V, i.e. there is no possible vector of coefficients  c . 

A6. I don't know a good answer here, but presumably it uses this idea:

If  G = <x>  is cyclic of order  n, we can use the sequence
  { x, x^2, x^4, x^8, ..., x^{2^{k-1}} }
of length  k,  whose subsequences multiply to give all powers of  x
up through but not including  x^{2^k}. So a sequence of length  k  will
suffice if  n <= 2^k, i.e. we need a sequence of length no longer than
log_2( |G| ).

Now if we may write  G  as a product  G = H C  (i.e.  G  is the set of
products  h c  with  h  in  H  and  c  in  C )  then obviously we
may simply concatenate the generating sequences for  H  and  C  together
to get one for  G  ; by induction we can (I expect) find such sequences
for  H  and  C  of lengths <= log_2( |H| ) and  log_2( |C| )  respectively,
giving a sequence for  G  whose length is at most  log_2( |H| |C| ) = 
log_2( |G| ). 

(By similar reasoning we can handle the case where H is a normal
subgroup of G and C is the quotient group.)

This is sufficient to handle abelian groups  G  (and, using the parenthetical
remark, we can handle all solvable groups). Also the symmetric groups
can be covered since  S_n = S_(n-1) C  where  C  is the cyclic group 
generated by an  n-cycle.  But not every group can be written as a product
of two nonintersecting subgroups, e.g. the quaternion groups cannot be.
Maybe it is true that nonexistence of a factorization implies the existence
of a normal subgroup, so we can still win, but that seems kind of complicated
for a PUtnam question!

B1. The answer is 2. Given any two points, the possible centers of the
circles that contain them form a line (the perpendicular bisector of the
segment joining the points); so ANY two rational points lie on a circle
with non-rational center. But by the same reasoning, given any THREE
noncollinear points, the center of the (unique) circle containing them 
may be found by intersecting two such lines. The computations of the
lines and their interections may be carried out in the field containing
the coordinates of the points, hence will be rational if the points are.

B2. I get -1. 

We prove by induction that   F_n (x) = x^n ( a_n log(x) + b_n ), 
(a result familiar to most calculus instructors!) for some constants a_n
and b_n, starting with  a_0 = 1 and b_0 = 0, and then computing that
a_{n-1} = n a_n  and  b_{n-1} = n b_n + a_n . From the first we
see  a_n = 1/n!  and then from the second we conclude that 
b_n = -(1+1/2+1/3+...+1/n) / n! .  Then  F_n(1) = b_n  (the integral
is improper but again every calculus instructor knows  x^n log(x) -> 0
as x->0 ), so n! F_n(1) = - (1+1/2+...+1/n) . This sum is within a
constant of  log(n) ("Integral Test", again), so the limit is -1.

B3. Certainly the circle  [ cos(t)/2, cos(t)/2, sin(t)/2, sin(t)/2 ] sits
inside the cube and has radius 1/sqrt(2). I suspect no larger circle
can be drawn in there but I don't know how to prove it. 

I know that more generally people have looked for the largest X that
can be fit inside a unit cube of dimension  n,  where  X  includes
"line segment", "square box of dimension  k", "equilateral triangle",
"n-ball", etc.  Surely  X="circle"  has also been considered.

B4. This is a fact of life when solving polynomial equations p-adically.

Lemma: if  h  is an integer polynomial which assumes all values mod p^k,
then it assumes all values mod  p^{k+1}  iff  h'  is never zero mod p.
(The lemma holds for any  k > 0 .)

Proof. h(x + p^k y) = h(x) + h'(x) p^k y + h''(x)/2 p^(2k) y^2 + ...
Now, the denominators here are only nominal: for example, h''(x)/2  is the
sum of terms of the form  c (k+1)(k+2)/2 x^k,  and that binomial coefficient
is an integer. So we see first of all that the values of  h(x)  mod p^k
depend only on  x mod p^k,  which means that a set of residues
{a, a+p^k, a+2p^k, ...} can only be the output of  h  for inputs that
are in the same residue class mod  p^k . Thus  h  attains all residue
classes mod  p^{k+1}  iff for  y = 0, 1, 2, ..., p-1  the values of
h'(x) y  are distinct mod  p, and this happens iff  h'(x)  is nonzero.

So in our problem,  h  attains all values mod p^2, hence all values mod p;
the we use the Lemma with k=1 to conclude  h'(x)  is never zero mod p. 
Now use (the converse of) the lemma with k=2 to conclude  h  attains all
values mod  p^3  (and indeed by induction holds for all values of  k .)

B5. f  must be of the forms  f(x) = M+x  or  M-x  for some integer  M.

We must (apparently!) use the fact that  f  is differentiable. I think I
am being kind of clumsy here but this works. 

For any rational  a,  let  L = f'(a).  Then I claim first that  L  is
rational, and in fact an integer.  Indeed, find integers  m,n  so that 
|L - m/n| < 1/(2n)  and then use  epsilon=1/(2n)  in the definition
   L = lim (1/h)( f(a+h) - f(a) )
So there is some  N  such that for all integers  k > N  we have
   | k ( f(a+1/k) - f(a) ) - L | < 1/(2n).
In particular (triangle inequality)
   | k ( f(a+1/k) - f(a) ) - m/n | < 1/n.
Apply this to integers  k  which are multiples of the denominator of  a.
Then both  k f(a+1/k)  and  k f(a)  will be integers. But no integer
can differ from a multiple of  1/n  by less than  1/n  unless that
difference is zero, i.e. we must have
     k ( f(a+1/k) - f(a) ) = m/n 
for these integers  k.  (Notice that by taking  k -> oo  we conclude  L
is actually equal to  m/n, i.e. it's rational.) Furthermore, since
the left side is an integer, we must have  n | m  (i.e.  L  is an integer).

Now,  we are also told that  f'  is continuous, so there is an interval
around  a  where  | f'(x) - f'(a) | < 1 ; but for rational  x  in this
interval,  f'(x)  is also integral by the previous analysis, and so
f'(x) and f'(a) must be equal. So  f'(x)=L  for all rational  x  in this
interval, and hence (by taking limits and using the continuity of f')
for all  x  in this interval.

But a locally-constant function defined on all of  R  is actually constant,
so  f'(x) = L  everywhere, which means  f(x) = L x + M  for some integer  L
and some constant  M  (which must also be an integer since  M = f(0/1)  is
an integer).

Finally, note that if  p | L  then  f(1/p) = (L/p) + M  is integral,
contradicting the assumption about denominators. So  L  is a unit, i.e.
L = +- 1 .


B6. Note that if  sigma  is k-limited, so is  sigma tau  where  tau = (1, j)
is a 2-cycle, iff   sigma(j)  <= 1+k   and    sigma(1) >= j-k . So in our
tally of k-limited permutations we will not change the parity if we ignore 
e.g. all the ones with sigma(2) not equal to  2+k, because each of these 
may be paired with (sigma) o (1,2)  (which is different from sigma).
Then, among all the k-limited permutations that DO have  sigma(2)=2+k, 
we note most of them come in pairs under right-multiplication by (1,3);
only those with  sigma(3)> 1+k  remain unpaired. (Of course with sigma(2)=2+k
this leaves only sigma(3)=3+k.) Similarly we can pair off most of those
k-limited sigmas having sigma(2)=2+k AND sigma(3)=3+k, using 
right-multiplication by  (1,4),  and so on.  So, apart from all these
pairs, all we need to count are those k-limited permutations that have
  sigma(j) = j+k  for  j = 2, 3, ..., k+1 .
(We must stop at this point because finally when using  (1, k+2)  we
have an additional point to consider: we cannot have sigma(k+2) too high,
but now also we cannot have  sigma(1) too low --- if sigma(1)=1 then
(sigma tau)(k+2) = sigma(1) = 1  differs from  k+2  by more than  k.)

But note that for a k-limited sigma, we must have  sigma(x)=1  for some  x;
the k-limitation means  x < k+2, but for all those  x  we have already
determined the values of  sigma  (and it's never  1)  except for the
case  x=1.  So we now know  sigma(1) = 1.

In a similar way, there is only one candidate left to have  sigma(x)=2,
and that is  x = k+2. Likewise with  sigma(x)=3, etc.  So now we know these
values of  sigma:
   x     :  1, 2,  3, ..., k, k+1, k+2, ...,2k+1
 sigma(x):  1,k+2,k+3,...,2k,2k+1,  2 , ..., k+1
The rest of the table will then show a k-limited permutation of
{2k+2, ..., n}, a set of  n-(2k+1) integers.

So if  p_k(n)  is the number we seek, then  p_k(n) = p_k(n-(2k+1)) mod 2,
which shows that the answer depends only on  n mod  2k+1 .

Furthermore, the same analysis shows that there are NO unpaired k-limited
permutations if  n < 2k+1, as long as  n>=2  (so that we could start our
analysis with the permutation  (1,2) !). In the case  n=1  there is
obviously only the identity permtuation.  In the case  n=2k+1  the only
unpaired permutation is the one shown.

So the parity of the count  p_k(n)  is odd  iff n = 0 or 1 mod 2k+1.