Putnam 2013

[dm]

The 74th William Lowell Putnam Mathematical Competition
Saturday, 7 December 2013

A1
Recall that a regular icosahedron is a convex polyhedron having 12 vertices and 20 faces; the faces are congruent equilateral triangles. On each face of a regular icosahedron is written a nonnegative integer such that the sum of all $20$ integers is $39.$ Show that there are two faces that share a vertex and have the same integer written on them.

A2
Let $S$ be the set of all positive integers that are not perfect squares. For $n$ in $S,$ consider choices of integers $a_1,a_2,\dots, a_r$ such that $n<a_1<a_2<\cdots<a_r$ and $n\cdot a_1\cdot a_2\cdots a_r$ is a perfect square, and let $f(n)$ be the minimum of $a_r$ over all such choices. For example, $2\cdot 3\cdot 6$ is a perfect square, while $2\cdot 3,2\cdot 4, 2\cdot 5, 2\cdot 3\cdot 4,$ $2\cdot 3\cdot 5, 2\cdot 4\cdot 5,$ and $2\cdot 3\cdot 4\cdot 5$ are not, and so $f(2)=6.$ Show that the function $f$ from $S$ to the integers is one-to-one.

A3
Suppose that the real numbers $a_0,a_1,\dots,a_n$ and $x,$ with $0<x<1,$ satisfy

\[\frac{a_0}{1-x}+\frac{a_1}{1-x^2}+\cdots+\frac{a_n}{1-x^{n+1}}=0.\]

Prove that there exists a real number $y$ with $0<y<1$ such that

\[a_0+a_1y+\cdots+a_ny^n=0.\]

A4
A finite collection of digits $0$ and $1$ is written around a circle. An arc of length $L\ge 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')|\le 1$ for any two arcs $w,w'$ of the same length. Suppose that some arcs $w_1,\dots,w_k$ have the property that

\[Z=\frac1k\sum_{j=1}^kZ(w_j)\text{ and }N=\frac1k\sum_{j=1}^k N(w_j)\]

are both integers. Prove that there exists an arc $w$ with $Z(w)=Z$ and $N(w)=N.$

A5
For $m\ge 3,$ a list of $\binom m3$ real numbers $a_{ijk}$ $(1\le i<j<k\le m)$ is said to be area definite for $\mathbb{R}^n$ if the inequality

\[\sum_{1\le i<j<k\le m}a_{ijk}\text{Area}(\triangle A_iA_jA_k)\ge0\]

holds for every choice of $m$ points $A_1,\dots,A_m$ in $\mathbb{R}^n.$ For example, the list of four number $a_{123}=a_{124}=a_{134}=1, a_{234}=-1$ is area definite for $\mathbb{R}^2.$ Prove that if a list of $\binom m3$ numbers is area definite for $\mathbb{R}^2,$ then it is area definite for $\mathbb{R}^3.$

A6
Define a function $w:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ as follows. For $|a|,|b|\le 2,$ let $w(a,b)$ be as in the table shown; otherwise, let $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}\]

For every finite subset $S$ of $\mathbb{Z}\times\mathbb{Z},$ define

\[A(S)=\sum_{(\mathbf{s},\mathbf{s'})\in S\times S} w(\mathbf{s}-\mathbf{s'}).\]

Prove that if $S$ is any finite nonempty subset of $\mathbb{Z}\times\mathbb{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.$)

B1
For positive integers $n,$ let the numbers $c(n)$ be determined by the rules $c(1)=1,c(2n)=c(n),$ and $c(2n+1)=(-1)^nc(n).$ Find the value of

\[\sum_{n=1}^{2013}c(n)c(n+2).\]

B2
Let $C=\bigcup_{N=1}^{\infty}C_N,$ where $C_N$ denotes the set of `cosine polynomials' of the form

\[f(x)=1+\sum_{n=1}^Na_n\cos(2\pi nx)\]

for which:
(i) $f(x)\ge 0$ for all real $x,$ and
(ii) $a_n=0$ whenever $n$ is a multiple of $3.$
Determine the maximum value of $f(0)$ as $f$ ranges through $C,$ and prove that this maximum is attained.

B3
Let $P$ be a nonempty collections of subsets of $\{1,\dots,n\}$ such that:
(i) if $S,S'\in P,$ then $S\cup S'\in P$ and $S\cap S'\in P,$ and
(ii) if $S\in P$ and $S\ne\emptyset,$ then there is a subset $T\subset S$ such that $T\in P$ and $T$ contains exactly one fewer element than $S.$
Suppose that $f:P\to\mathbb{R}$ is a function such that $f(\emptyset)=0$ and

\[f(S\cup S')= f(S)+f(S')-f(S\cap S')\text{ for all }S,S'\in P.\]

Must there exist real numbers $f_1,\dots,f_n$ such that

\[f(S)=\sum_{i\in S}f_i\]

for every $S\in P?$

B4
For any continuous real-valued function $f$ defined on the interval $[0,1],$ let

\[\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)|.\]

Show that if $f$ and $g$ are continuous real-valued functions defined on the interval $[0,1],$ then

\[\text{Var}(fg)\le 2\text{Var}(f)M(g)^2+2\text{Var}(g)M(f)^2.\]

B5
Let $X=\{1,2,\dots,n\},$ and let $k\in X.$ Show that there are exactly $k\cdot n^{n-1}$ functions $f:X\to X$ such that for every $x\in X$ there is a $j\ge 0$ such that $f^{(j)}(x)\le k.$
[Here $f^{(j)}$ denotes the $j$th iterate of $f,$ so that $f^{(0)}(x)=x$ and $f^{(j+1)}(x)=f\left(f^{(j)}(x)\right).$]

B6
Let $n\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 $n$ spaces, arranged in a line. At each turn, a player either
\textbullet places a stone in an empty space, or
\textbullet 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?

-- Пн дек 09, 2013 20:25:41 --

Список городов, где проходило зеркало: http://putnam.ho.ua/schedule.html
Некоторые фото: http://vk.com/album5499034_183760322
https://www.facebook.com/dmitry.mitin/m ... 039&type=1

[Urnwestek]

A2) Правильно ли я полагал, что $f(n)=4n$ для всех $n$, кроме $2$?

[cool.phenon]

B1

$$\sum\limits_{n=1}^{2013}{c(n)c(n+2)}=c(1)c(3)+\sum\limits_{i=1}^{1006}{c(2i)c(2i+2)}+\sum\limits_{i=1}^{1006}{c(2i+1)c(2i+3)}=$$ $$=c(1)c(3)+\sum\limits_{i=1}^{1006}{c(i)c(i+1)}+\sum\limits_{i=1}^{1006}{\left(-1\right)^{2i+1}c(i)c(i+1)}=c(1)c(3)=-1 $$

[iifat]

Urnwestek в сообщении #798484 писал(а):

Правильно ли я полагал, что $f(n)=4n$ для всех $n$, кроме $2$?

А разве $f(3)=12$? у меня что-то не получается.
Я правильно понимаю, что perfect square — это квадрат, а one-to-one означает инъективность?

[Aritaborian]

One-to-one обычно означает биекцию (one-to-one correspondence — взаимно-однозначное соответствие).

[Urnwestek]

Aritaborian в сообщении #798531 писал(а):

One-to-one обычно означает биекцию (one-to-one correspondence — взаимно-однозначное соответствие).

В украинском варианте условия была «инъективность», то что отображение не может быть биективным — очевидно, как минимум, оно не равно единице ни в одной точке.

iifat в сообщении #798530 писал(а):

А разве $f(3)=12$? у меня что-то не получается.

$r = 1, a_1 = 12, n = 3, n \cdot a_1 = 6^2$

Или это намёк был на то, что для $n=3$ существует требуемый набор $\{a_i\}$ с меньшим $a_r$? (:

[iifat]

Виноват. Показалось почему-то, что рассматриваются произведения $n$ на ровно $n$ же чисел. Только $f(8)=18\ne4\cdot8$

[Urnwestek]

iifat в сообщении #798544 писал(а):

Виноват. Показалось почему-то, что рассматриваются произведения $n$ на ровно $n$ же чисел. Только $f(8)=18\ne4\cdot8$

Да, беда, ну да ладно.

A1) Докажем, что в любом наборе $a_1, ..., a_{20}$ есть минимум пять одинаковых элементов. Предположим, что существует набор, в котором пяти одинаковых элементов нету. Будем, среди всех таких наборов, искать набор с минимальной суммой: им окажется $4 \cdot 0 + 4 \cdot 1 + 4 \cdot 2 + 4 \cdot 3 + 4 \cdot 4 + 4 \cdot 5 = 40 > 39$. Но сумма элементов набора должна быть равна 39, противоречие.
У икосаэдера к каждой вершине примыкает по 5 граней, и 5 граней с одинаковыми числами есть, а граней всего 20, а $5\cdot 5 = 25 > 20$. Ну, думаю, понятно.

[Null]

В А2 обратная функция выглядит аналогично исходной.

-- Чт дек 12, 2013 11:46:49 --

A3
$a_0+a_1y+\cdots+a_n y^n=f(y)$
$0=f(1)+xf(x)+x^2f(x^2)+\cdots$

(Оффтоп)

Почему я не могу исправлять свои сообщения?

[Null]

А6

$A(S)$ линейна по $w$. А она вроде разбивается в сумму функций вида

$$\begin{array}{ccc} & -1 & \\ -1& 4 & -1 \\ & -1 & \\ \end{array}$$

$$\begin{array}{ccc} -1& 2 & -1 \\ \end{array}$$

$$\begin{array}{ccccc} -1& 0&2 & 0& -1 \\ \end{array}$$

-- Чт дек 12, 2013 14:34:52 --

А6 у меня неправильно.

[g______d]

А6. Функция $w$, с точностью до положительного множителя, равного 16 и сколько-то там $2\pi$, является набором коэффициентов Фурье функции

$$ \check{w}(x,y)=\cos^2 x+\cos^2 y+\cos x\cos y(1-\cos x-\cos y-\cos x\cos y),\quad (x,y)\in [0;2\pi)\times [0;2\pi). $$

Она положительна на множестве полной меры. Следовательно, для любой функции $u(x,y)$, отличной от нуля на множестве положительной меры,

$$ \int\limits_0^{2\pi}\int\limits_0^{2\pi}\check{w}(x,y)u(x,y)\overline{u(x,y)}\,dx\,dy>0. $$

Теперь в качестве $u$ берем обратное преобразование Фурье от характеристической функции $S$ и в интеграле переходим к преобразованию Фурье, получаем положительность той свертки, которая в условии.

[Null]

Зачем в B3 условие ii? По моему остальных условий хватит.

-- Пт дек 13, 2013 11:15:48 --

B5 Рассмотрим граф с вершинами X и ребрами $(s,f(s))$ где $s>k$. По условию этот граф набор деревьев. Каждому графу соответствует $n^k$ функций.( f(s) при $s\le k$ имеет по n вариантов)
Рассмотрим коды Прюфера длинны $n-k$ с выбором максимального по номеру листа. Это будут последовательности из $X^{n-k}$ с единственным ограничением: последний элемент $\le k$. Ну дальше перемножаем.

-- Пт дек 13, 2013 11:19:11 --

(Оффтоп)

TeX сломался