Problems I like:

Problem set 9, problem 5: combinatorial proof

I'd like to see a combinatorial proof on the exam.  This can be a/the
problem where they write a proof logically.  It need not be too
difficult, but I really feel these problems are *very* conceptual,
which is a good thing.  In particular, I dislike counting problems
where they count something like, "the number of hands which have 2
hearts but only one queen".  Another thing we can do with
combinatorial proofs is to give a combinatorial proof, and ask them to
fill in the "equation A = equation B" part.

A problem idea:

We could mix counting with asymptotics.  We could say: show that the
(# of something) = O(blah).  Show that it is not Theta(blah).

A problem idea:

We could mix graph theory with logical quantifiers, asking them to
give a logical definition of independent set, vertex cover, coloring,
etc.

In-Class Problems Week 13, Friday, Problem 2:

We could give them the Von-Neumann trick.  Ask them what's the
expected number of flips before we get a bit out, as well as show that
it gives unbiased bits.