MathDB

6

Part of 2013 Putnam

Problems(2)

Putnam 2013 A6

Source:

12/9/2013
Define a function w:Z×Z→Zw:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z} as follows. For ∣a∣,∣b∣≤2,|a|,|b|\le 2, let w(a,b)w(a,b) be as in the table shown; otherwise, let w(a,b)=0.w(a,b)=0. bw(a,b)−2−1012−2−1−22−2−1−1−24−44−2a02−412−421−24−44−22−1−22−2−1\begin{array}{|lr|rrrrr|}\hline &&&&b&&\\ &w(a,b)&-2&-1&0&1&2\\ \hline &-2&-1&-2&2&-2&-1\\ &-1&-2&4&-4&4&-2\\ a&0&2&-4&12&-4&2\\ &1&-2&4&-4&4&-2\\ &2&-1&-2&2&-2&-1\\ \hline\end{array} For every finite subset SS of Z×Z,\mathbb{Z}\times\mathbb{Z}, define A(S)=∑(s,s′)∈S×Sw(s−s′).A(S)=\sum_{(\mathbf{s},\mathbf{s'})\in S\times S} w(\mathbf{s}-\mathbf{s'}). Prove that if SS is any finite nonempty subset of Z×Z,\mathbb{Z}\times\mathbb{Z}, then A(S)>0.A(S)>0. (For example, if S={(0,1),(0,2),(2,0),(3,1)},S=\{(0,1),(0,2),(2,0),(3,1)\}, then the terms in A(S)A(S) are 12,12,12,12,4,4,0,0,0,0,−1,−1,−2,−2,−4,−4.12,12,12,12,4,4,0,0,0,0,-1,-1,-2,-2,-4,-4.)
Putnamfunctionlinear algebramatrixinductionSupportinequalities
Putnam 2013 B6

Source:

12/9/2013
Let n≥1n\ge 1 be an odd integer. Alice and Bob play the following game, taking alternating turns, with Alice playing first. The playing area consists of nn 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,s, places a stone in the nearest empty space to the left of ss (if such a space exists), and places a stone in the nearest empty space to the right of ss (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?
Putnamgeometrysymmetryinvariantinductionpigeonhole principle