Putnam 1994/A6 solution

Putnam 1994

Problem A6

Let Z be the integers. Let f₁, f₂, ... , f₁₀ : 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₁g₂... g₁₀}, 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₁...g_k-1 and g' any composition g_k+1...g₁₀, 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_kg' 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_kg' does not map A to itself. But the 1024 maps in S form 512 disjoint pairs gg', gf_kg', so at least 512 maps in S (one from each pair) do not map A to itself.

Putnam 1994