Let Z be the integers. Let f_{1}, f_{2}, ... , f_{10} **:** Z → Z be bijections. Given any n ∈ Z we can find some composition of the f_{i} (allowing repetitions) which maps 0 to n. Consider the set of 1024 functions S = { g_{1}g_{2}... g_{10}}, where g_{i} = the identity or f_{i}. Show that at most half the functions in S map a finite (non-empty) subset of Z onto itself.

**Solution**

Let A be a finite subset of Z. Suppose all f_{i} map A to itself. Then, since all the f_{i} are bijections, all compositions of the f_{i} also map A to itself. If 0 ∈ A, then since A is finite we can find n ∉ A, and hence no composition of the f_{i} could take 0 to n, contradicting the hypothesis. If 0 ∉ A, then take any n ∈ A. In this case no composition of the f_{i} could take 0 to n, contradicting the hypothesis. Thus some f_{k} does not map A to itself.

Let g be any composition g_{1}...g_{k-1} and g' any composition g_{k+1}...g_{10}, where g_{i} = the identity or f_{i}. [If k = 1, then we take g to be the identity, and if k = 10, then we take g' to be the identity.]. Now if both gg' and gf_{k}g' map A to itself, then f_{k} must map A to itself (since all the functions are bijections), contradiction. Hence at least one of the maps gg' and gf_{k}g' does not map A to itself. But the 1024 maps in S form 512 disjoint pairs gg', gf_{k}g', so at least 512 maps in S (one from each pair) do not map A to itself.

© John Scholes

jscholes@kalva.demon.co.uk

12 Dec 1998