### Putnam 1994

Problem A6

Let Z be the integers. Let f1, f2, ... , f10 : Z → Z be bijections. Given any n ∈ Z we can find some composition of the fi (allowing repetitions) which maps 0 to n. Consider the set of 1024 functions S = { g1g2... g10}, where gi = the identity or fi. 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 fi map A to itself. Then, since all the fi are bijections, all compositions of the fi also map A to itself. If 0 ∈ A, then since A is finite we can find n ∉ A, and hence no composition of the fi could take 0 to n, contradicting the hypothesis. If 0 ∉ A, then take any n ∈ A. In this case no composition of the fi could take 0 to n, contradicting the hypothesis. Thus some fk does not map A to itself.

Let g be any composition g1...gk-1 and g' any composition gk+1...g10, where gi = the identity or fi. [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 gfkg' map A to itself, then fk must map A to itself (since all the functions are bijections), contradiction. Hence at least one of the maps gg' and gfkg' does not map A to itself. But the 1024 maps in S form 512 disjoint pairs gg', gfkg', so at least 512 maps in S (one from each pair) do not map A to itself.