Putnam 2012

[dm]

A1
Пусть $d_1,d_2,\dots,d_{12}$ --- вещественные числа в открытом
интервале $(1,12).$ Докажите, что найдутся
различные индексы $i,j,k$, такие что $d_i,d_j,d_k$
суть длины сторон остроугольного
треугольника.

A2
Пусть $*$ --- коммутативная ассоциативная
бинарная операция на множестве $S.$
Предположим, что для любых элементов $x$ и $y$ в $S$
найдется элемент $z$ в $S$, такой что $x*z=y.$
($z$ может зависеть от $x$ и $y.$)
Докажите, что если $a,b,c$ в $S$ и $a*c=b*c,$ то $a=b.$

A3
Пусть $f:[-1,1]\to\mathbb{R}$ --- непрерывная функция
такая что
(i) $f(x)=\frac{2-x^2}{2}f\left(\frac{x^2}{2-x^2}\right)$
для всех $x$ из отрезка $[-1,1],$
(ii) $ f(0)=1,$ и
(iii) предел $\lim_{x\to 1^-}\frac{f(x)}{\sqrt{1-x}}$
существует и конечен.
Докажите, что такая функция $f$
единственна и найдите $f(x)$ (в замкнутом виде).

A4
Пусть $q$ и $r$ --- целые числа,
причем $q>0,$ и пусть $A$ и $B$ ---
интервалы на вещественной оси.
Пусть $T$ ---- множество чисел вида $b+mq$, где $b$ и $m$
целые, причем $b$ лежит в интервале $B$; $S$ ---
множество целых чисел $a$ в интервале
$A$ таких что $ra$ лежит в $T.$
Докажите, что если произведение длин
интервалов $A$ и $B$ меньше чем $q,$ то $S$ представляет
из себя пересечение $A$ и некоторой
арифметической прогрессии.

A5
Пусть $\mathbb{F}_p$ --- поле остатков
по простому модулю $p,$ $n$ --- натуральное число.
Пусть $v$ --- фиксированный вектор в $\mathbb{F}_p^n,$
$M$ --- матрица $n\times n$ с элементами в $\mathbb{F}_p$.
определим отображение $G:\mathbb{F}_p^n\to \mathbb{F}_p^n$ формулой
$G(x)=v+Mx.$ Пусть $G^{(k)}$
обозначает $k$-ую композицию $G$ с собой, т.е.
$G^{(1)}(x)=G(x)$ и $G^{(k+1)}(x)=G(G^{(k)}(x)).$
Определите все пары $p,n$, для которых существуют $v$ и $M$
такие что все $p^n$ векторов $G^{(k)}(0),$ $k=1,2,\dots,p^n$
различны.

A6
Пусть $f(x,y)$ --- непрерывная вещественнозначная
функция на плоскости $\mathbb{R}^2.$
Предположим, что для любого прямоугольника $R$ площади $1$
интеграл $f(x,y)$ по $R$ равен нулю.
Обязательно ли функция $f(x,y)$ --- тождественный нуль?

B1
Пусть $S$ --- класс функций из $[0,\infty)$ в $[0,\infty)$,
удовлетворяющий условиям:
(i) функции $f_1(x)=e^x-1$ и $f_2(x)=\ln(x+1)$ лежат в $S;$
(ii) если функции $f(x)$ и $g(x)$ лежат в $S,$
то функции $f(x)+g(x)$ и $f(g(x))$ лежат в $S;$
(iii) если $f(x)$ и $g(x)$ лежат в $S$
и $f(x)\ge g(x)$ для всех $x\ge 0,$
то функция $f(x)-g(x)$ лежит в $S.$
Докажите, что если функции $f(x)$ и $g(x)$ лежат в $S,$
то функция $f(x)g(x)$ тоже лежит в $S.$

B2
Пусть $P$ --- данный невырожденный
многогранник. Докажите, что найдется такая
константа $c(P)>0$, что выполняется условие:
если объединение $n$ шаров с суммой объемов
$V$ содержит поверхность многогранника $P,$
то $n>c(P)/V^2.$

B3
Однокруговой волейбольный турнир $2n$ команд продолжается
$2n-1$ день. Каждый день проходит $n$ игр и
каждая команда играет ровно одну игру.
В итоге каждая сыграла с каждой ровно один
раз. Всегда ли можно выбирать каждый
день команду, победившую в этот день,
так, чтобы все $2n-1$ выбранных команд были различны?

B4
Предположим, что $a_0=1$ и $a_{n+1}=a_n+e^{-a_n}$
для $n=0,1,2,\dots.$
Имеет ли последовательность $a_n-\log n$
конечный предел при $n\to\infty?$ (Здесь $\log n$
обозначает натуральный логарифм $\log n=\log_en=\ln n.$)

B5
Докажите, что для
любых двух ограниченных функций
$g_1,g_2 : \mathbb{R}\to[1,\infty)$
существуют функции $h_1,h_2 : \mathbb{R}\to\mathbb{R}$
такие что для всех $x\in\mathbb{R}$
$\[\sup_{s\in\mathbb{R}}\left(g_1(s)^xg_2(s)\right)=\max_{t\in\mathbb{R}}\left(xh_1(t)+h_2(t)\right).\]$

B6
Пусть $p$ --- нечетное простое такое что $p\equiv 2\pmod{3}.$
Определим перестановку
$\pi$ остатков по модулю $p$ формулой $\pi(x)\equiv x^3\pmod{p}.$
Докажите, что перестановка $\pi$ четная если и только
если $p\equiv 3\pmod{4}.$

Перевод на русский: rus4.

[Yu_K]

http://amc.maa.org/a-activities/a7-problems/putnamindex.shtml ссылка на задачи прошлых лет.

[Утундрий]

Может я чего-то не понимаю, однако
А1. $d_1 = d_2 = … = d_{12} = 5$

[dm]

Утундрий в сообщении #655344 писал(а):

Может я чего-то не понимаю, однако
А1. $d_1 = d_2 = … = d_{12} = 5$

Здравствуйте, верите ли вы

(Оффтоп)

в бога

в существование правильного треугольника со стороной 5?

[Shadow]

Утундрий в сообщении #655344 писал(а):

Может я чего-то не понимаю, однако

Тут нужно доказать, что "всегда найдется". Если отсортировать их в неубывающем порядке и методом от противного предположить, что не будет остроугольного треугольника, должно быть
$\\d_1>1\\ d_2>1\\ d_3>\sqrt 2\\ d_4>\sqrt 3\\ \cdots\\ d_{12}>\sqrt{144}$
Там числа Фибоначчи под корнем.

[Утундрий]

Три раза "Гм". Вот у меня двенадцать одинаковых палочек, причём все равны как на подбор и, осмелюсь заметить, попадают в заявленный интервал. Так меня тут хотят убедить, что из них можно выбрать такие три, которые составят остроугольный треугольник?

[dm]

Утундрий в сообщении #655600 писал(а):

Три раза "Гм". Вот у меня двенадцать одинаковых палочек, причём все равны как на подбор и, осмелюсь заметить, попадают в заявленный интервал. Так меня тут хотят убедить, что из них можно выбрать такие три, которые составят остроугольный треугольник?

Это становится забавно. Конечно, можно

[Утундрий]

Да, теперь согласен. По неведомой причине "остроугольный треугольник" ассоциировался у меня с имеющим один тупой угол. И равносторонний по указанной причине к "остроугольным" не относился.

[Alexander Evnin]

A2. Зафиксируем некоторый элемент $x$. Для него найдётся такой элемент $e$, что $x*e=x$.
Отсюда легко выводится, что и для произвольного элемента $y$ справедливо $y*e=y$.
Пусть элемент $c'$ определяется условием $c*c'=e$.
Теперь из $a*c=b*c$ следует $a*c*c'=b*c*c'$, $a*e=b*e$, $a=b$.

[Alexander Evnin]

A3. Из условия следует, что функция чётная.
Положим $g(x)=f(x)/\sqrt{1-x^2}$. Тогда функция $g(x)$ непрерывна на интервале$(-1;1)$
и имеет конечный предел при $x\to1-0$. Легко проверить, что $g(0)=1$ и $g(x)=g(\frac{x^2}{2-x^2})$. Пусть $x_0\in(0;1)$ и $x_{n+1}=\frac{x_n^2}{2-x_n^2}$.
Нетрудно убедиться в том, что $\lim_{n\to\infty}x_n=0$. Из непрерывности $g(x)$ в нуле получаем, что на $[0;1)$ выполняется равенство $g(x)=1$. Из чётности функции $g(x)$ и характера её поведения в окрестности точки $x=1$ получаем тождество $g(x)=1$ на всём отрезке $[-1;1]$.
Значит, $f(x)=\sqrt{1-x^2}$.

-- 09.12.2012, 11:22 --

B1. Из того, что $f, g\in S$, последовательно получаем принадлежность $S$ следующих функций:
$\ln(f+1),\quad \ln(g+1),\quad \ln(f+1)(g+1),\quad fg+f+g,\quad fg$.

-- 09.12.2012, 11:34 --

B3. Рассмотрим двудольный граф, в первой доле которого $2n-1$ дней, а во второй $2n$ команд. Ребро $uv$ графа означает, что в день $u$ команда $v$ была победительницей.
Докажем, что за любые $k$ дней побеждало не менее $k$ команд. Если это не так, то за эти $k$ дней какие-то $2n-k+1$ команд только проигрывали. Но тогда все встречи между собой они должны были провести за $2n-1-k$ дней, что невозможно.
По теореме Холла, в графе существует совершенное паросочетание. Значит, ответ: да.

Если придётся переиздавать
http://urss.ru/cgi-bin/db.pl?lang=Ru&bl ... &id=125830,
то эту задачу обязательно добавлю!

[mihiv]

A6.В приведенной формулировке задачу решить не удалось, но если потребовать дополнительно, чтобы $f(x,y)$ была равномерно непрерывной (т.е. для любого $\varepsilon >0,|f(P_1)-f(P_2)|<\varepsilon$, как только $\rho _{P_1P_2}<\delta (\varepsilon )$), то ответ положительный.