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) = 2m3n and let g(-m/n) = 2m5n. 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