Subcontests
(6)Putnam 2013 A6
Define a function w:Z×Z→Z as follows. For ∣a∣,∣b∣≤2, let w(a,b) be as in the table shown; otherwise, let w(a,b)=0.
aw(a,b)−2−1012−2−1−22−2−1−1−24−44−2b02−412−421−24−44−22−1−22−2−1
For every finite subset S of Z×Z, define A(S)=(s,s′)∈S×S∑w(s−s′). Prove that if S is any finite nonempty subset of Z×Z, then A(S)>0. (For example, if S={(0,1),(0,2),(2,0),(3,1)}, then the terms in A(S) are 12,12,12,12,4,4,0,0,0,0,−1,−1,−2,−2,−4,−4.) Putnam 2013 B6
Let n≥1 be an odd integer. Alice and Bob play the following game, taking alternating turns, with Alice playing first. The playing area consists of n spaces, arranged in a line. Initially all spaces are empty. At each turn, a player either• places a stone in an empty space, or
• removes a stone from a nonempty space s, places a stone in the nearest empty space to the left of s (if such a space exists), and places a stone in the nearest empty space to the right of s (if such a space exists).Furthermore, a move is permitted only if the resulting position has not occurred previously in the game. A player loses if he or she is unable to move. Assuming that both players play optimally throughout the game, what moves may Alice make on her first turn? Putnam 2013 A5
For m≥3, a list of (3m) real numbers aijk (1≤i<j<k≤m) is said to be area definite for Rn if the inequality 1≤i<j<k≤m∑aijk⋅Area(△AiAjAk)≥0 holds for every choice of m points A1,…,Am in Rn. For example, the list of four numbers a123=a124=a134=1,a234=−1 is area definite for R2. Prove that if a list of (3m) numbers is area definite for R2, then it is area definite for R3. Putnam 2013 B5
Let X={1,2,…,n}, and let k∈X. Show that there are exactly k⋅nn−1 functions f:X→X such that for every x∈X there is a j≥0 such that f(j)(x)≤k.[Here f(j) denotes the jth iterate of f, so that f(0)(x)=x and f(j+1)(x)=f(f(j)(x)).] Putnam 2013 A4
A finite collection of digits 0 and 1 is written around a circle. An arc of length L≥0 consists of L consecutive digits around the circle. For each arc w, let Z(w) and N(w) denote the number of 0's in w and the number of 1's in w, respectively. Assume that ∣Z(w)−Z(w′)∣≤1 for any two arcs w,w′ of the same length. Suppose that some arcs w1,…,wk have the property that Z=k1j=1∑kZ(wj) and N=k1j=1∑kN(wj) are both integers. Prove that there exists an arc w with Z(w)=Z and N(w)=N. Putnam 2013 B4
For any continuous real-valued function f defined on the interval [0,1], let μ(f)=∫01f(x)dx,Var(f)=∫01(f(x)−μ(f))2dx,M(f)=0≤x≤1max∣f(x)∣. Show that if f and g are continuous real-valued functions defined on the interval [0,1], then Var(fg)≤2Var(f)M(g)2+2Var(g)M(f)2. Putnam 2013 A3
Suppose that the real numbers a0,a1,…,an and x, with 0<x<1, satisfy 1−xa0+1−x2a1+⋯+1−xn+1an=0. Prove that there exists a real number y with 0<y<1 such that a0+a1y+⋯+anyn=0. Putnam 2013 B3
Let P be a nonempty collection of subsets of {1,…,n} such that:(i) if S,S′∈P, then S∪S′∈P and S∩S′∈P, and
(ii) if S∈P and S=∅, then there is a subset T⊂S such that T∈P and T contains exactly one fewer element than S.Suppose that f:P→R is a function such that f(∅)=0 and f(S∪S′)=f(S)+f(S′)−f(S∩S′) for all S,S′∈P. Must there exist real numbers f1,…,fn such that f(S)=i∈S∑fi for every S∈P? Putnam 2013 A2
Let S be the set of all positive integers that are not perfect squares. For n in S, consider choices of integers a1,a2,…,ar such that n<a1<a2<⋯<ar and n⋅a1⋅a2⋯ar is a perfect square, and let f(n) be the minimum of ar over all such choices. For example, 2⋅3⋅6 is a perfect square, while 2⋅3,2⋅4,2⋅5,2⋅3⋅4, 2⋅3⋅5,2⋅4⋅5, and 2⋅3⋅4⋅5 are not, and so f(2)=6. Show that the function f from S to the integers is one-to-one.