MathDB

6

Part of 1994 Putnam

Problems(2)

Putnam 1994 A6

Source:

7/12/2014
Let f1,f2,⋯ ,f10f_1,f_2,\cdots ,f_{10} be bijections on Z\mathbb{Z} such that for each integer nn, there is some composition fℓ1∘fℓ2∘⋯∘fℓmf_{\ell_1}\circ f_{\ell_2}\circ \cdots \circ f_{\ell_m} (allowing repetitions) which maps 00 to nn. Consider the set of 10241024 functions F={f1ϵ1∘f2ϵ2∘⋯∘f10ϵ10} \mathcal{F}=\{f_1^{\epsilon_1}\circ f_2^{\epsilon_2}\circ \cdots \circ f_{10}^{\epsilon_{10}}\} where ϵi=0\epsilon _i=0 or 11 for 1≤i≤10.  (fi01\le i\le 10.\; (f_i^{0} is the identity function and fi1=fi)f_i^1=f_i). Show that if AA is a finite set of integers then at most 512512 of the functions in F\mathcal{F} map AA into itself.
Putnamfunctioncollege contests
Putnam 1994 B6

Source:

7/13/2014
For a∈Za\in \mathbb{Z} define na=101a−100⋅2a n_a=101a-100\cdot 2^a Show that, for 0≤a,b,c,d≤990\le a,b,c,d\le 99 na+nb≡nc+nd(mod10100)  ⟹  {a,b}={c,d} n_a+n_b\equiv n_c+n_d\pmod{10100}\implies \{a,b\}=\{c,d\}
Putnammodular arithmeticcollege contests