A curious operation

From the Putnam Competition (I believe):

Suppose # is a binary operation on a set S such that the following properties hold:

  1. For all a, b, c in S, (a#b)#c = a#(b#c);
  2. For all a, b in S, if a#b = b#a then a=b.

Prove that, for all x, y, z in S, we have x#y#z = x#z.

First, note that by rule 1, x#(x#x) = (x#x)#x. So by rule 2, we have x#x = x for all x in S.

It follows that x#(x#y#x) = x#x#y#x = x#y#x = x#y#x#x = (x#y#x)#x, so that by rule 2, we have x#y#x = x for all x, y in S.

Finally, we now have (x#z)#(x#y#z) = x#z#x#y#z = x#y#z = x#y#z#x#z = (x#y#z)#(x#z), so that again by rule 2 we have x#y#z = x#z, and the result is proven.

What I especially like about this problem is that with very few conditions, we end up proving something very strong – that a lot of information in a string of elements is redundant. a#b#c#d#e#f#g is exactly the same element as a#g: the middle five terms add nothing!

As an aside, see if you can find an example of such an operation…

Advertisements

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