MathDB

Putnam 1994 A6

Source:

July 12, 2014

Putnamfunctioncollege contests

Problem Statement

Let

f_1,f_2,\cdots ,f_{10}

be bijections on

\mathbb{Z}

such that for each integer

n

, there is some composition

f_{\ell_1}\circ f_{\ell_2}\circ \cdots \circ f_{\ell_m}

(allowing repetitions) which maps

0

to

n

. Consider the set of

1024

functions

\mathcal{F}=\{f_1^{\epsilon_1}\circ f_2^{\epsilon_2}\circ \cdots \circ f_{10}^{\epsilon_{10}}\}

where

\epsilon _i=0

or

1

for

1\le i\le 10.\; (f_i^{0}

is the identity function and

f_i^1=f_i)

. Show that if

A

is a finite set of integers then at most

512

of the functions in

\mathcal{F}

map

A

into itself.

Back to Problems View on AoPS