### 39th Putnam 1978

Problem A4

A binary operation (represented by multiplication) on S has the property that (ab)(cd) = ad for all a, b, c, d. Show that: (1) if ab = c, then cc = c; (2) if ab = c, then ad = cd for all d. Find a set S, and such a binary operation, which also satisfies: (A) a a = a for all a; (B) ab = a ≠ b for some a, b; (C) ab ≠ a for some a, b.

Solution

(1): (ab)(ab) = ab, so cc = c. (2): (ab)d = ( (ab)(ab) ) (dd) = (ab)(dd) = ad. Note that an exactly similar argument gives a(bc) = ac. So the operation is in fact associative and a1a2... an = a1an.

In passing we note various possible special cases: (A) ab = k for all a, b (where k is fixed); (B) ab = a for all a, b; (C) ab = b for all a, b. The extra conditions are presumably designed to rule out these special cases.

So we need some operation which preserves something of the first element and something of the second. The easiest is to take S to consist of pairs (r, s) and to define the operation as: (r, s) (u, v) = (r, v). The simplest such example is S = { (0, 0), (0, 1), (1, 0), (1, 1) }. This obviously satisfies all the required conditions. Writing a = (0, 0), b = (0, 1), c = (1, 0), d = (1, 1), we have:

```   a  b  c  d

a  a  b  a  b

b  a  b  a  b

c  c  d  c  d

d  c  d  c  d

```