Putnam 2013

Bảng A
Câu 1. Nhắc lại rằng một Khối Hai mươi mặt đều là một đa diện lồi có $12$ đỉnh và $20$ mặt, các mặt là những tam giác đều và bằng nhau. Trên mỗi mặt của một Khối Hai mươi mặt đều được viết một số nguyên dương sao cho tổng của tất cả $20$ số nguyên đó là $39$. Chứng minh rằng có hai mặt chung đỉnh được viết cùng một số.

Câu 2. Gọi $S$ là tập hợp tất cả các số nguyên dương không phải là bình phương của một số hoàn hảo. Với mỗi $n \in S$, ta chọn các số nguyên $a_1,a_2,\dots, a_r$ sao cho $n<a_1<a_2<\cdots<a_r$ và $n\cdot a_1\cdot a_2\cdots a_r$  là bình phương một số hoàn hảo. Đặt $f(n)$ là giá trị bé nhất của $a_r$ trong tất cả các cách chọn như vậy. Chẳng hạn, $2\cdot 3\cdot 6$ là một bình phương hoàn hảo, trong khi đó $2\cdot 3,2\cdot 4, 2\cdot 5, 2\cdot 3\cdot 4, 2\cdot 3\cdot 5, 2\cdot 4\cdot 5$, và $2\cdot 3\cdot 4\cdot 5$ thì không, do đó $f(2)=6$. Chứng minh rằng $f$ là tương ứng $1-1$ giữa $S$ và tập các số nguyên.

Câu 3. Giả sử rằng các số thực $a_0 , a_1 , \dots , a_n$ và $x$ , với $0 <x < 1 $, thỏa mãn
$$\frac { a_0 } { 1- x } + \frac { a_1 } { 1- x ^ 2 } + \cdots + \frac { a_n } { 1- x ^ { n +1 }} = 0$$
Chứng minh rằng tồn tại một số thực $y$ với $0 < y < 1$ sao cho $a_0 + a_1y + \cdots + a_ny ^ n = 0$ .

Câu 4. Có hữu hạn các chữ số $0$ và $1$ được viết thành một vòng tròn. Một cung tròn với chiều dài $L \ge 0$ bao gồm $L$ chữ số liên tiếp trên vòng tròn. Đối với mỗi cung $w$, gọi $Z (w)$ và $N ( w)$ lần lượt là số số $0$ và số số $1$ trong $w$. Giả sử $|Z (w) -Z ( w ) | \le 1$ với bất kỳ hai vòng cung $w, w '$ có chiều dài bằng nhau. Giả sử rằng một số vòng cung $w_1 , \dots , w_k$ có tính chất
$$Z = \frac{1}{k}\sum_ { j = 1 } ^ kZ ( w_j ) \text { và } N = \frac1k \sum_ { j = 1 } ^ k N ( w_j )$$
là các số nguyên. Chứng minh rằng có tồn tại một vòng cung $w$ với $Z (w) = Z$ và $N ( w) = N$.

Câu 5. Với $m \ge 3$, một danh sách $\binom{m}{3}$ số thực $a_ { ijk } (1 \le i < j < k \le m )$ được gọi là "vùng" cho $\mathbb {R} ^ n$ nếu bất đẳng thức
$$\sum_ {1 \le i < j < k \le m } a_ { ijk } \cdot S( \Delta A_iA_jA_k ) \ge 0$$
đúng với mọi điểm $A_1 , \dots , A_m$ trong $\mathbb {R } ^ n $. Ví dụ, danh sách bốn số $a_ { 123 } = a_ { 124 } = a_ { 134 } = 1 , a_ { 234 } = -1$ là vùng cho $\mathbb {R} ^ 2$. Chứng minh rằng nếu một danh sách $\binom{m}{3}$ số là vùng cho $\mathbb {R} ^ 2$ thì nó cũng là vùng cho $\mathbb {R} ^ 3 $.

Câu 6. Cho ánh xạ $w : \mathbb {Z} \times \mathbb {Z} \to \mathbb {Z}$ như sau: với $| a | , | b | \le 2 $, cho $w (a, b )$ như trong bảng, nếu không, quy ước $w (a, b ) = 0 $.
\[ \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} \]

Đối với mỗi tập con hữu hạn $S$ của $\mathbb{Z} \times \mathbb {Z}$, xác định 
$$A ( S ) = \sum_ { (s,s') \in S \times S } w (s - s')$$
Chứng minh rằng nếu $S$ là tập con hữu hạn bất kỳ khác rỗng của $\mathbb {Z} \times \mathbb {Z}$ thì $A ( S ) > 0$ . ( Ví dụ, nếu $S = \{ (0,1), (0,2) , ( 2,0 ) , (3,1) \} $, khi đó các giá trị của $A ( S )$ là $12,12,12 , 12,4,4,0,0,0,0 , -1, -1, -2, -2, -4 , -4 $).



Bảng B
Câu 1

Với số nguyên dương $n$ bất kì, dãy $c(n)$ được xác định như sau:
$$c (1) = 1 , c ( 2n ) = c (n) , c ( 2n +1 ) = (-1) ^ nc ( n )$$

Tìm giá trị của $\sum_{n=1}^{2013}c(n)c(n+2).$

.

Câu 2

Cho $ C=\bigcup_{N=1}^{\infty}C_N, $ ở đó $C_N$ là tập các 'đa thức cos' có dạng:

\[ f(x)=1+\sum_{n=1}^Na_n\cos(2\pi nx) \]thỏa mãn đồng thời hai điều kiện:

$(i) f (x) \ge 0, \forall x \in \mathbb{R}$,

$(ii) a_n = 0$ khi $n$ là bội số của $3$ .

Tìm giá trị lớn nhất của $f(0), \forall f \in C$ .

Câu 3. Cho $P$ là một họ không rỗng các tập con của $\{1 , \dots , n \}$ thỏa mãn đồng thời hai điều kiện :

$(i)$ Nếu $S , S ' \in P$ thì $S \cup S' \in P$ và $S \cap S ' \in P$

$(ii)$ Nếu $S \in P$ và $S \ne \emptyset$ thì tồn tại một tập hợp $T \subset S$ sao cho $T \in P$ và $T$ có  ít hơn $S$ đúng một phần tử.

Cho ánh xạ $f: P \to \mathbb{R}$ có $f (\emptyset ) = 0$ và

$$f ( S \cup S ' ) = f ( S ) + f ( S ) -f ( S \cap S '), \forall S , S ' \in P$$

Có tồn tại hay không các số thực $f_1 , \dots , f_n$ sao cho $f ( S ) = \sum_ { i \in S } f_i, \forall S \in P$ ?

Câu 4

Kí hiệu $C_{[0;1]}$ là tập hợp tất cả các hàm số liên tục $f:[ 0,1] \to \mathbb{R}$. Với mọi $f \in C_{[0;1]}$, đặt:

\[ \mu(f)=\int_0^1f(x)\,dx,\text{Var}(f)=\int_0^1(f(x)-\mu(f))^2\,dx, M(f)=\max_{0\le x\le 1}|f(x)|. \]Chứng minh rằng
$$Var ( fg ) \le 2Var (f) M (g)^2 +2Var (g) M (f )^2, \forall f,g \in  .C_{[0;1]}$$

Câu 5. Cho $X = \{ 1,2, \dots , n \}$ và $k \in X$. Chứng minh rằng có đúng $k \cdot n^{ n- 1}$ ánh xạ $f: X \to X$ thỏa mãn $\forall x \in X$, luôn tồn tại $a_j \ge 0$ sao cho $f ^{ ( k) } (x) \le k$ .

Trong đó $f^{(k)}$ là hàm hợp $j$ lần của $f$, tức là $f^ { (0) } (x) = x, f^1(x)=f(x),..., f^{(j +1) } (x) = f \left ( f ^{ (j) } (x) \right).

Câu 6. Cho $n \ge 1$ là một số nguyên lẻ. Alice và Bob luân phiên nhau chơi một trò chơi, Alice chơi trước. Khu vực chơi bao gồm $n$ ô, sắp xếp theo một đường thẳng. Ban đầu tất cả các ô đều rỗng. Tại mỗi lượt, một cầu thủ hoặc

• Đặt một hòn đá vào một ô rỗng , hoặc

• Bỏ đi một hòn đá từ một ô không rỗng $s$ và đặt thêm 1 hòn đá vào ô trống gần nhất bên trái của $s$ (nếu có ô như vậy tồn tại), và cả ô trống gần nhất ở bên phải của $s$ (nếu ô như vậy tồn tại) .

Hơn nữa, một nước đi chỉ được coi là hợp lệ nếu các vị trí kết quả đã không xảy ra ở các lượt trước đó. Một người chơi bị thua nếu họ không thể thực hiện nước đi của mình. Giả định rằng cả hai người chơi đều dùng chiến lược tối ưu trong suốt trò chơi, Alice cần làm gì trong lần lượt đầu tiên của mình?