Year: 1994
Topic: Combinatorics Number Theory

Problem:
Let $f_1, \dots, f_{10}$ be bijections of the set of integers such that for each integer $n$, there is some composition $f_{i_1} \circ f_{i_2} \circ \cdots \circ f_{i_m}$ of these functions (allowing repetitions) which maps 0 to $n$. Consider the set of 1024 functions \[ \mathcal{F} = \{f_1^{e_1} \circ f_2^{e_2} \circ \cdots \circ f_{10}^{e_{10}}\}, \] $e_i = 0$ or 1 for $1 \leq i \leq 10$. ($f_i^0$ is the identity function and $f_i^1 = f_i$.) Given that $A$ is any nonempty finite set of integers, find the maximum number the functions in $\mathcal{F}$ that map to $A$ to itself.

Solution:
Let $A$ be a nonempty finite subset of the integers $\mathbb{Z}$. By the Pigeonhole Principle, any bijection of $\mathbb{Z}$ which maps $A$ to itself must be a bijection when restricted to $A$; in particular, its inverse also maps $A$ to itself. Note that not all the bijections $f_1, f_2, \dots, f_{10}$ can map $A$ to itself, for otherwise, if $0 \in A$, we could not map 0 to any $n \notin A$ by a composition $f_{i_1} \circ f_{i_2} \circ \dots \circ f_{i_m}$, while if $0 \notin A$, we could not map 0 to any $n \in A$ by such a composition.

Let $k$ be the smallest integer such that $f_k$ does not map $A$ to itself, and suppose that more than 512 of the functions $\mathcal{F}$ map $A$ to itself. We can write $\mathcal{F}$ as a disjoint union of unordered pairs of functions such that two compositions $f_{1}^{e_1} \circ f_{2}^{e_2} \circ \dots \circ f_{10}^{e_{10}}$ and $f_{1}^{d_1} \circ f_{2}^{d_2} \circ \dots \circ f_{10}^{d_{10}}$ are in the same pair when they differ only in the $k$-th exponent; that is, when $e_i = d_i$ for $i \neq k$. By the Pigeonhole Principle, there is then at least one of these 512 pairs in which both functions map $A$ to itself. Since all $f_l$ with $l > k$ also map $A$ to itself, we can use composition with the inverses of $f_l$, as needed, to conclude that for some $e_1, \dots, e_{k-1}$, the functions $F_1 = f_{1}^{e_1} \circ f_{2}^{e_2} \circ \dots \circ f_{k-1}^{e_{k-1}} \circ f_k$ and $F_2 = f_{1}^{e_1} \circ f_{2}^{e_2} \circ \dots \circ f_{k-1}^{e_{k-1}} \circ f_k$ both map $A$ to itself. But then $F_1^{-1} \circ F_2 = f_k$ also maps $A$ to itself, a contradiction. This makes the final answer \boxed{512}.