On 2012 Putnam Problem A2

This post continues my effort to write solutions to the problems on this year’s Putnam competition. I previously posted a solution to problem A1. Problem A2 seems like it should have been reasonable for students familiar with abstract algebra, but it could have been tricky for students without much exposure to axiomatic theories.

My (slight) rephrasing of the question is as follows: Let S be a set with a binary operation \ast that is commutative and associative. Suppose that, for every x and y in S, there exists z in S such that x \ast z = y. (This z may depend on x and y.) Show that, if a,b,c are in S and a \ast c = b \ast c, then a = b.

Don’t read anything below Nyan Cat if you don’t want to see the solution.

poptart1red1

Initial remarks

This is like when you start learning group theory and you have some axioms, and you try to prove things using those axioms. In this case, there are three given axioms: commutativity, associativity, and what I’ll call “transitivity” (for every x and y, there exists z such that x \ast z = y). And you’re asked to prove that the “cancellation law” holds: if a \ast c = b \ast c, then a = b. It’s an exercise in being very careful that every step of your proof is justified, either by the axioms themselves or by results you have already established.

There may be a more direct approach, but it turns out that in this case, you can actually prove that S is a group. We already know that \ast is well-defined and associative, so we need to prove the existence of an identity and inverses.

Solution

Pick any element x. The transitivity property implies that there exists an element e such that x \ast e = x. We need to be careful with this equation, since, as far as we know, e might depend on x. However, for any y there is a z such that x \ast z = y, so

y \ast e = (x \ast z) \ast e = (x \ast e) \ast z = x \ast z = y,

so e really is an identity element. [Note: there can’t be more than one identity, so it turns out that e doesn’t depend on x after all.]

The existence of inverses directly follows from the transitivity property: For every c, there is an element (which we’ll call c^{-1} such that c \ast c^{-1} = e. This concludes the proof that S is a group, and the cancellation law will therefore hold:  if a \ast c = b \ast c, then we can multiply both sides of the equation by c^{-1} to get a = b.

QED

Closing remarks

As I said, there may be a slightly more direct approach that avoids completely proving that S is a group, but the observation that it is actually a group seems to be important and probably explains why the problem was considered “interesting enough” to be on the exam.

I’ll point out that, even though group operations aren’t required to be commutative, the commutativity axiom was crucial for this problem. Consider a set with an operation \diamond that simply “takes the term on the right”, so that x \diamond y = y for all x and y. This is a perfectly good associative operation, and it satisfies the transitivity property. But (as long as the set has more than one element) you won’t have a group.

Can you pinpoint where commutativity was used in the above solution?

Advertisements
Tagged , , , , , ,

One thought on “On 2012 Putnam Problem A2

  1. […] solutions to the problems on this year’s Putnam exam (previous solutions are here and here). More than the actual solutions, I hope that students will find my commentary valuable. When […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: