2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Putnam 2013
Сообщение09.12.2013, 21:20 
Экс-админ
Аватара пользователя


23/05/05
2106
Kyiv, Ukraine
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

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение09.12.2013, 23:18 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение10.12.2013, 00:30 
Аватара пользователя


12/05/12
604
Оттуда
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 $$

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение10.12.2013, 01:52 
Заслуженный участник


16/02/13
4105
Владивосток
Urnwestek в сообщении #798484 писал(а):
Правильно ли я полагал, что $f(n)=4n$ для всех $n$, кроме $2$?
А разве $f(3)=12$? у меня что-то не получается.
Я правильно понимаю, что perfect square — это квадрат, а one-to-one означает инъективность?

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение10.12.2013, 01:54 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
One-to-one обычно означает биекцию (one-to-one correspondence — взаимно-однозначное соответствие).

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение10.12.2013, 03:38 
Аватара пользователя


03/10/13
449
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$? (:

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение10.12.2013, 04:08 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение10.12.2013, 04:18 
Аватара пользователя


03/10/13
449
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$. Ну, думаю, понятно.

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение12.12.2013, 10:20 
Заслуженный участник


12/08/10
1608
В А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$

(Оффтоп)

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

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение12.12.2013, 12:50 
Заслуженный участник


12/08/10
1608
А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 у меня неправильно. :-(

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение13.12.2013, 01:37 
Заслуженный участник
Аватара пользователя


08/11/11
5940
А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$ и в интеграле переходим к преобразованию Фурье, получаем положительность той свертки, которая в условии.

 Профиль  
                  
 
 Re: Putnam 2013
Сообщение13.12.2013, 09:54 
Заслуженный участник


12/08/10
1608
Зачем в 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 сломался :-(

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group