### 23rd Putnam 1962

**Problem B2**

Let R be the reals, let N be the set of positive integers, and let P = {X **:** X ⊆ N}. Find f **:** R → P such that f(a) ⊂ f(b) (and f(a) ≠ f(b) ) if a < b.

**Solution**

Let Q be the rationals. Define g: Q → N as follows. For m/n where m and n are positive integers without any common factor, let g(m/n) = 2^{m}3^{n} and let g(-m/n) = 2^{m}5^{n}. Now define f: R → P by f(x) = { g(r) : r <= x is rational }. We claim that f has the required property.

Clearly g is injective. Now suppose x < y are reals. We can find a rational r such that x < r < y. So g(r) belongs to f(y) but not to f(x). But S belongs to f(x), then S = g(q) for some q in Q with q < x. So q < y and hence S belongs to f(y) also. So f(x) is a subset of f(y).

23rd Putnam 1962

© John Scholes

jscholes@kalva.demon.co.uk

5 Feb 2002