MathDB

1994 Putnam

Part of Putnam

Subcontests

(6)
6
2

Putnam 1994 A6

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.

Putnam 1994 B6

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\}
5
2

Putnam 1994 A5

Let (rn)n≥0(r_n)_{n\ge 0} be a sequence of positive real numbers such that lim⁡n→∞rn=0\lim_{n\to \infty} r_n = 0. Let SS be the set of numbers representable as a sum ri1+ri2+⋯+ri1994, r_{i_1} + r_{i_2} +\cdots + r_{i_{1994}} , with i1<i2<⋯<i1994.i_1 < i_2 < \cdots< i_{1994}. Show that every nonempty interval (a,b)(a, b) contains a nonempty subinterval (c,d)(c, d) that does not intersect SS.

Putnam 1994 B5

For each α∈R\alpha\in \mathbb{R} define fα(x)=⌊αx⌋f_{\alpha}(x)=\lfloor{\alpha x}\rfloor. Let n∈Nn\in \mathbb{N}. Show there exists a real α\alpha such that for 1≤ℓ≤n1\le \ell \le n : fαℓ(n2)=n2−ℓ=fαℓ(n2). f_{\alpha}^{\ell}(n^2)=n^2-\ell=f_{\alpha^{\ell}}(n^2). Here fαℓ(x)=(fα∘fα∘⋯∘fα)(x)f^{\ell}_{\alpha}(x)=(f_{\alpha}\circ f_{\alpha}\circ \cdots \circ f_{\alpha})(x) where the composition is carried out ℓ\ell times.
4
2
3
2
2
2
1
2