Putnam 2009

[dm]

В воскресенье, 6 декабря прошла студенческая олимпиада имени Патнема в Киеве, Львове, Николаеве и Санкт-Петербурге. (По этим же заданиям писали США и Канада в свою субботу, т.е. нашу ночь с субботы на воскресенье). Ниже условия. Регламент - 6 задач на 3 часа, 1 час перерыв и еще 6 задач на 3 часа.

Часть A.

A1. Вещественнозначная функция $f$ задана на плоскости и для любого квадрата $ABCD$ удовлетворяет равенству $f(A)+f(B)+f(C)+f(D)=0$. Обязательно ли $f(P)=0$ для всех точек $P$ плоскости?

A2. Функции $f$, $g$, $h$ дифференцируемы в некоторой окрестности
нуля и удовлетворяют условиям
$f'=2f^2gh+\frac{1}{gh},\qquad f(0)=1,$
$g'=fg^2h+\frac{4}{fh},\qquad g(0)=1,$
$h'=3fgh^2+\frac{1}{fg},\qquad h(0)=1.$
Найдите явную формулу для $f(x)$ (выполняющуюся в некоторой окрестности нуля.)

A3. Пусть $d_n$ - определитель матрицы $n\times n$, коэффициенты которой, слева направо и сверху вниз, суть $\cos1,\ \cos2,\ \ldots,\ \cos n^2$.
(Например, $d_3=\begin{vmatrix} \cos1&\cos2&\cos3\\ \cos4&\cos5&\cos6\\ \cos7&\cos8&\cos9 \end{vmatrix}$. Аргумент косинуса измеряется в радианах.)
Найдите $\lim_{n\to\infty}d_n$.

A4. Пусть $S$ - множество, состоящее из рациональных чисел, такое, что
(a) $0\in S$;
(b) Если $x\in S$, то $x+1\in S$ и $x-1\in S$; и
(c) Если $x\in S$ и $x\notin\{0,1\}$, то $\frac{1}{x(x-1)}\in S$.
Обязательно ли $S$ содержит все рациональные числа?

A5. Существует ли конечная абелева группа $G$ такая, что произведение порядков всех ее элементов равно $2^{2009}$ ?

A6. Пусть $f:[0,1]^2\to\mathbb{R}$ - непрерывная функция, заданная на замкнутом единичном квадрате такая, что $\frac{\partial f}{\partial x}$ и $\frac{\partial f}{\partial y}$ существуют и непрерывны внутри квадрата $(0,1)^2$. Пусть $a=\int_0^1f(0,y)\mathrm{d}y$, $b=\int_0^1f(1,y)\mathrm{d}y$, $c=\int_0^1f(x,0)\mathrm{d}x$, и $d=\int_0^1f(x,1)\mathrm{d}x$. Обязательно ли найдется точка $(x_0,y_0)$ в $(0,1)^2$ такая, что $\frac{\partial f}{\partial x}(x_0,y_0)=b-a$ и $\frac{\partial f}{\partial y}(x_0,y_0)=d-c$?

Часть B

B1. Докажите, что любое положительное рациональное число может быть представлено как отношение произведения факториалов (не обязательно различных) простых чисел. Например, $\frac{10}{9}=\frac{2!\cdot5!}{3!\cdot3!\cdot3!}$.

B2. Заплатив $b^3-ab^2$ долларов, $b>a$, можно переместиться из точки $a$ вещественной прямой в точку $b$. Для каких вещественных чисел $c$ можно переместиться из $0$ в $1$, заплатив в сумме ровно $c$ долларов? (Доллары бесконечно делимы, количество перемещений должно быть конечно.)

B3. Назовем подмножество $S$ множества $\{1,2,\dots,n\}$ посредственным, если вместе с любыми двумя своими элементами одной четности оно содержит их полусумму. Пусть $A(n)$ - количество посредственных подмножеств в $\{1,2,\dots,n\}.$ [Например, любое подмножество $\{1,2,3\}$ кроме $\{1,3\}$ посредственно, так что $A(3)=7.$] Найдите все натуральные $n$ такие, что $A(n+2)-2A(n+1)+A(n)=1.$

B4. Многочлен от двух переменных $x,y$ назовем сбалансированным, если его среднее значение на любой окружности с центром в начале координат равно 0. Сбалансированные многочлены степени не выше чем 2009 образуют векторное пространство $V$ над $\mathbb{R}.$ Найдите размерность $V.$

B5. Пусть $f:(1,\infty)\to\mathbb{R}$ - такая дифференцируемая функция, что $\[f'(x)=\frac{x^2-\left(f(x)\right)^2}{x^2\left(\left(f(x)\right)^2+1\right)}\quad\text{при всех }x>1.\]$ Докажите, что $\displaystyle\lim_{x\to\infty}f(x)=\infty.$

B6. Докажите, что для всякого натурального числа $n,$ существует последовательность целых чисел $a_0,a_1,\dots,a_{2009}$ с $a_0=0$ и $a_{2009}=n$ такая, что каждый член после $a_0$ либо превосходит один из предыдущих членов на некоторую степень 2 с неотрицательным целым показателем, либо равен остатку от деления одного из положительных предыдущих членов на другой.


Условия: http://putnam.ho.ua/problems.html

(Перевод на русский: http://translate.google.com/translate?h ... google.com )

[TOTAL]

A3 $|d_n|<6\pi /n$

A4 обязательно ли S содержит 2/5?

A6 $f=(y+1)\sin(2\pi x)$

B6 $n=2^k \mod 2^m+1$

[dm]

Поправил.

[OV08]

А1 Х произвольная точка. Строим квадрат, так, что Х центр . Отмечаем середины сторон. Складывая суммы по 4 маленьким квадратам, и используя то, что середины тоже образуют квадрат получим $4F(X)=0$
А3 $d_n=0$ если $n>2$ к 1 столбцу добавить третий...

[vmg]

B1.
1) Достаточно доказать для натуральных.
2) Достаточно доказать для простых.
3) Занумеруем простые и индукция по номеру. Индукционный переход с помощью постулата Бертрана:
$p_{k+1}=\frac{(p_{k+1})!}{(p_{k+1}-1)!}$, у $p_{k+1}-1$ простые делители не больше $p_k$.

-- Ср дек 09, 2009 17:50:14 --

B1.
1) Достаточно доказать для натуральных.
2) Достаточно доказать для простых.
3) Занумеруем простые и индукция по номеру. Индукционный переход с помощью постулата Бертрана:
$p_{k+1}=\frac{(p_{k+1})!}{(p_{k+1}-1)!}$, у $p_{k+1}-1$ простые делители не больше $p_k$.

[vmg]

B!. Бертран - лишнее, и без него все проходит.
B5. Пусть $f(x)=1/x+g(x)$, тогда $g'(x)=\frac{1}{f^2(x)+1}+\frac{1}{x^2(f^2(x)+1)}$, $g(x)<f(x)<g(x)+1$, $g$ возрастает.
Ограниченность $g$ сверху влечет $g'\ge\frac{1}{c^2+1}$, чго быть не может.

[OV08]

В2 Пусть наши шажки $x_{0},x_{1},x_{2},\dots,x_{n}$, где $x_{0}=0, x_{n}=1$. тогда мы ищем $c$ такие, что $\sum_{j=1}^{n}x_{j}^{2}(x_{j}-x_{j-1})=c$. Из возрастания $x^2$ получим, что
$\frac{1}{3}=\int_{0}^{1}x^{2}\,dx<\sum_{j=1}^{n}x_{j}^{2}(x_{j}-x_{j-1})\le 1$
1 достигается прыжком из 0 в 1. То, что до стигаются все числа из интервала $(\frac{1}{3};1)$ нетрудно доказать расматривая разбитие $P_{t}=\{0,tx_{1},tx_{2},\dots,tx_{n-1},1\}$

[mihiv]

A2. Поделим 1-е,2-е и 3-е уравнения на f,g и h соответственно,полученные уравнения сложим,тогда

$$(\ln u)'=6(u+\frac 1u)$$

,где $u=fgh$.Интегрируем это ДУ с учетом начальных условий:$u=\tg (6x+\frac \pi 4).$Поделив 1-е ур-ие на f получим

$$(\ln f)'=2u+\frac 1u$$

,подставив сюда найденное выражение для u найдем:$f(x)=\sqrt [6] {\dfrac {\sin (6x+\frac {\pi }4)}{\sqrt 2 \cos ^2(6x+\frac {\pi}4)}}$

[Sonic86]

A3. При $n \geq 3$ $d_n=0$, поскольку 1-ые 3 строки будут линейно зависимы.
Делается так. Пусть $n$ - размер матрицы.
$i$-я строка $\cos (in+j) = \cos (in) \cos (j) - \sin (in) \sin (j) \sim \sin (j)$ - не зависят от номера строки ($j$ - номер столбца, 1-ые слагаемые уходят за счет 1-й строки $\cos (j)$, потом выносим коэффициент).

[Sonic86]

B3. $A(n+2)-2A(n+1)+A(n)=1 \Leftrightarrow n=2^k-1$. Доказывается через рассмотрение комбинаторного смысла всей левой части.
B2. $\int\limits_0^1 x^2dx \leq c \leq 1$

[Sonic86]

В В3 кто-нибудь смог найти формулу для $A(n)$?

[maxal]

Sonic86 в сообщении #271325 писал(а):

В В3 кто-нибудь смог найти формулу для $A(n)$?

Для получения формулы достаточно заметить, что если $S$ посредственное, то любые два его последовательные элемента обязаны быть разной четности. Отсюда следует, что если $a,b,c$ - любые три последовательных элемента $S$, то $b=(a+c)/2$, то есть, $S$ есть ничто иное как арифметическая прогрессия с нечетной разностью. Ну а найти количество таких прогрессий - плёвое дело.