Problem 1:

I recently went to a part with my spouse; there were 11 other married couples there. A lot of handshaking happened (but of course no one shook hands with their spouse). At the end, it turned out that for every k from 0 to 22, someone other than me had shaken hands with exactly k people. How many people did I shake hands with? Prove it.

Problem 2:

Suppose I have a Manhattan-type n × n grid of horizontal and vertical streets. On each street between two neighboring intersections, I put a one way sign (note different parts of the street can point in different directions). See the figure below.

We’ll say that a sink is a point (intersection) with all arrows aiming into it, and a source is a point with all arrows aiming out of it.

We noticed that whenever we labeled the streets so that there was no source or sink, there always seemed to be at least one city block that you could drive directly around, by making four right turns or four left turns. For example, such a cycle is in the upper right corner of the figure.

Prove that this is indeed true. (Hint: use well-ordering.)