1994 Putnam A6

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$.) Show that if $A$ is any nonempty finite set of

integers, then at most 512 of the functions in $\mathcal{F}$ map $A$ to

itself.

令 $f_1, \dots, f_{10}$ 为整数集的双射，使得对于

每个整数$n$，都有一些组合$f_{i_1} \circ f_{i_2}

\circ \cdots \circ f_{i_m}$ 这些函数(允许重复)

它将 0 映射到 $n$。考虑 1024 个函数的集合

$$

\mathcal{F} = \{f_1^{e_1} \circ f_2^{e_2} \circ \cdots \circ f_{10}^{e_{10}}\},

$$

$e_i = 0$ 或 1 表示 $1 \leq i \leq 10$。 ($f_i^0$ 是恒等函数

且 $f_i^1 = f_i$。)证明如果 $A$ 是任意非空有限集

整数，则 $\mathcal{F}$ 中最多有 512 个函数将 $A$ 映射到

本身。