Putnam 2010

[dm]

Зеркало студенческой олимпиады имени Патнема в 2010 году будет проводиться 5 декабря в следующих городах:

Украина, Киев, просп. академика Глушкова, 4-Е, Киевский национальный университет имени Тараса Шевченко, механико-математический факультет, ауд. 41, 10:00-13:00 ("A"), 14:00-17:00 ("B") по киевскому времени (GMT+2)
(Также ожидаются участники из НТУУ "Киевский политехнический институт" и Национального педагогического университета имени М. П. Драгоманова)

Украина, Львов, ул. Дорошенко, 41, Львовский национальный университет имени Ивана Франко, географический факультет, ауд. 24, 10:00-13:00 ("A"), 14:00-17:00 ("B") по киевскому времени (GMT+2)
(Организует механико-математический факультет)

Украина, Донецк, ул. Челюскинцев, 157, Донецкий государственный университет управления, корпус 3, ауд. 410, 10:00-13:00 ("A"), 14:00-17:00 ("B") по киевскому времени (GMT+2)
(Совместно с Донецким национальным университетом)

Украина, Харьков, площадь Свободы, 4, Харьковский национальный университет имени В. Н. Каразина, механико-математический факультет, ауд. 6-52, 10:00-13:00 ("A"), 14:00-17:00 ("B") по киевскому времени (GMT+2)

Украина, Николаев, ул. Никольская, 24, Николаевский национальный университет имени В. А. Сухомлинского, механико-математический факультет, ауд. 367, 10:00-13:00 ("A"), 14:00-17:00 ("B") по киевскому времени (GMT+2)
(Совместно с Национальным университетом кораблестроения имени адмирала Макарова)

Россия, Санкт-Петербург, просп. Кронверкский, 49, Санкт-Петербургский государственный университет информационных технологий, механики и оптики, ауд. 331, 332, 11:00-14:00 ("A"), 15:00-18:00 ("B") по московскому времени (GMT+3)
(совместно с Санкт-Петербургским государственным университетом)

Туркменистан, Ашгабат, Туркменский государственный университет им. Магтымгулы, математический факультет, 12:00-15:00 ("A"), 16:00-19:00 ("B") по ашгабатскому времени (GMT+5)

Сайт олимпиады: http://putnam.ho.ua/index.html

После того, как олимпиада пройдет везде, постараюсь выложить тексты здесь.

//Закрыто. Когда будет возможно обсуждение, тема будет открыта. / GAA, 4.12.10

//Открыто. / Toucan, 6.12.10

[dm]

The 71st William Lowell Putnam Mathematical Competition
Saturday, December 4, 2010

A1. Given a positive integer $n,$ what is the largest $k$ such that the numbers $1,2,\dots,n$ can be put into $k$ boxes so that the sum of the numbers in each box is the same?
[When $n=8,$ the example $\{1,2,3,6\},\{4,8\},\{5,7\}$ shows that the largest $k$ is at least 3.]

A2. Find all differentiable functions $f:\mathbb{R}\to\mathbb{R}$ such that

$$f'(x)=\frac{f(x+n)-f(x)}n$$

for all real numbers $x$ and all positive integers $n.$

A3. Suppose that the function $h:\mathbb{R}^2\to\mathbb{R}$ has continuous partial derivatives and satisfies the equation

$$h(x,y)=a\frac{\partial h}{\partial x}(x,y)+b\frac{\partial h}{\partial y}(x,y)$$

for some constants $a,b.$ Prove that if there is a constant $M$ such that $|h(x,y)|\le M$ for all $(x,y)$ in $\mathbb{R}^2,$ then $h$ is identically zero.

A4. Prove that for each positive integer $n,$ the number $10^{10^{10^n}}+10^{10^n}+10^n-1$ is not prime.

A5. Let $G$ be a group, with operation $*$. Suppose that
(i) $G$ is a subset of $\mathbb{R}^3$ (but $*$ need not be related to addition of vectors);
(ii) For each $\mathbf{a},\mathbf{b}\in G,$ either $\mathbf{a}\times\mathbf{b}=\mathbf{a}*\mathbf{b}$ or $\mathbf{a}\times\mathbf{b}=\mathbf{0}$ (or both), where $\times$ is the usual cross product in $\mathbb{R}^3.$
Prove that $\mathbf{a}\times\mathbf{b}=\mathbf{0}$ for all $\mathbf{a},\mathbf{b}\in G.$

A6. Let $f:[0;\infty)\to\mathbb{R}$ be a strictly decreasing continuous functions such that $\lim_{x\to\infty}f(x)=0.$ Prove that $\displaystyle\int_0^{\infty}\frac{f(x)-f(x+1)}{f(x)}\,dx$ diverges.

B1. Is there an infinite sequence of real numbers $a_1,a_2,a_3,\dots$ such that

$$a_1^m+a_2^m+a_3^m+\cdots=m$$

for every positive integer $m?$

B2. Given that $A,B,$ and $C$ are noncollinear points in the plane with integer coordinates such that the distances $AB,AC,$ and $BC$ are integers, what is the smallest possible value of $AB?$

B3. There are 2010 boxes labeled $B_1,B_2,\dots,B_{2010},$ and $2010n$ balls have been distributed among them, for some positive integer $n.$ You may redistribute the balls by a sequence of moves, each of which consists of choosing an $i$ and moving exactly $i$ balls from box $B_i$ into any one other box. For which values of $n$ is it possible to reach the distribution with exactly $n$ balls in each box, regardless of the initial distribution of balls?

B4. Find all pairs of polynomials $p(x)$ and $q(x)$ with real coefficients for which

$$p(x)q(x+1)-p(x+1)q(x)=1.$$

B5. Is there a strictly increasing function $f:\mathbb{R}\to\mathbb{R}$ such that $f'(x)=f(f(x))$ for all $x?$

B6. Let $A$ be an $n\times n$ matrix of real numbers for some $n\ge 1.$ For each positive integer $k,$ let $A^{[k]}$ be the matrix obtained by raising each entry to the $k$th power. Show that if $A^k=A^{[k]}$ for $k=1,2,\cdots,n+1,$ then $A^k=A^{[k]}$ for all $k\ge 1.$

[OV08]

По-моему в этом году задачи достаточно легкие, во всяком случае где-то 7 (А1-4, В1,2,5) делаются практически сходу.

[mihiv]

A5.Пусть $\mathbf {e}\ne \mathbf {0}$ единица группы $G,\mathbf {a}\ne 0\mathbf$ произвольный элемент группы,тогда $\mathbf {e}*\mathbf {a}=\mathbf {a}*\mathbf {e}=\mathbf {a}.$
Предположим $\mathbf {e}\times \mathbf {a}\ne \mathbf {0}$,тогда согласно условию $\mathbf {a}=\mathbf {e}\times \mathbf {a}=\mathbf {a}\times \mathbf {e}$ и,следовательно,$\mathbf {a}=\mathbf {0}$-противоречие.Следовательно,$\mathbf {e}\times \mathbf {a}=\mathbf {0}$ и таким образом $\mathbf {a}=k\mathbf {e}$,а т.к. $\mathbf {a}$ произвольный элемент группы,то всегда $\mathbf {a}\times \mathbf {b}=\mathbf {0}$
Пусть теперь $\mathbf {e}=\mathbf {0}$.Из равенства $\mathbf {a}*\mathbf {a^{-1}}=\mathbf {0}$(доказательство от противного) следует,что $\mathbf {a}\times \mathbf {a^{-1}}=\mathbf {0}$,т.е. $\mathbf {a^{-1}}=k_a\mathbf {a}$,где $k_a$-некоторое действительное число.
Пусть теперь $\mathbf {a}$ и $\mathbf {b}$ элементы группы для которых $\mathbf {a}\times \math {b}\ne \mathbf {0}$Рассмотрим равенство $\mathbf {a^{-1}}*\mathbf {a}*\mathbf {b}=\mathbf {b}$Можно перемножить сначала два последних слагаемых (ассоциативный закон).Это позволяет с учетом условия задачи записать это равенство в таком виде:$k_a\mathbf {a}\times [\mathbf {a}\times \mathbf {b}]=\mathbf {b}$Отсюда следует,что векторы $\mathbf {a}$ и $\mathbf {b}$ ортогональны,а коэффициент $k_a=-\frac 1{(\mathbf {a}\mathbf {a})}.$
Здесь я должен к сожалению прерваться,окончание допишу немного позже.

[mihiv]

Продолжение решения A.5.
Отметим,что коэффициент $k_a<0.$
В предыдущем сообщении было сделано предположение,что $\mathbf {a\times b\ne 0}$.Наряду сэлементами $\mathbf {a}$ и $\mathbf {b}$ в группу входит и элемент $\mathbf {c}=\mathbf {a}*\mathbf {b}=\mathbf {a}\times \mathbf {b}$.Таким образом группа содержит тройку взаимно ортогональных векторов $\mathbf {a,b,c}.$Теперь очевидно,что группа может содержать только элементы,содержащиеся в одном из трех множеств:$1.\alpha \mathbf {a},2.\beta \mathbf {b},3.\gamma \mathbf {c},$ где $\alpha ,\beta ,\gamma$-действительные числа.
Рассмотрим элемент $\mathbf {a}*\mathbf {a}.$Он не равен $\mathbf {0}$,т.к. мы выяснили,что $\mathbf {a^{-1}}=k_a\mathbf {a},(k_a<0).$Поэтому он должен записываться одним из приведенных выше трех способов.Покажем,что это невозможно.Пусть,например,этот элемент записывается первым способом.Тогда,умножая его справа на элемент $\mathbf {b}$ получим:$\mathbf {(a*a)*b}=\alpha \mathbf {a\times b}=\alpha \mathbf {c}$,с другой стороны, это же произведение можно записать как: $\mathbf {a*(a*b)=a\times [a\times b]}=\lambda \mathbf {b}$,где $\lambda $-числовой множитель неравный 0.Получили невозможное равенство:$\alpha \mathbf {c}=\lambda \mathbf {b}$.Аналогично доказывается невозможность случаев 2. и 3.
Отсюда заключаем,что сделанное предположение неверно и,следовательно,$\mathbf {a\times b=0}$.

[mihiv]

A1.$k_{max}=[\frac {n+1}2]$
A3.Поделим обе части уравнения на $\sqrt {a^2+b^2}.$В правой части уравнения получим производную функции $h(x,y)$ по направлению вектора k(a,b)Перейдем к системе координат (x',y'),повернутой вокруг начала так,что ее ось абсцисс направлена по вектору k.В новых координатах уравнение принимает вид:$h(x',y')=\dfrac {\partial {h(x',y')}}{\partial {x'}}.$
Пусть $h(x_0',y'_0)>0.$Интегрируем по $x'$ от $x'_0$ до $x'$ и получим:$h(x',y'_0)=h(x'_0,y'_0)\exp(x'-x'_0)$.Функция неограничена при $x'\to \infty .$Следовательно необходимо $h(x',y')\equiv 0.$

[mihiv]

B1.Предположим такая последовательность существует и для всех $i,|a_i|<1$,тогда $\sum \limits _{i=1}^{\infty }a_i^4<\sum \limits _{i=1}^{\infty }a_i^2=2,$что противоречит условию.С другой стороны последовательность не может содержать более одного элемента с модулем $\geqslant 1,$т.к. иначе не выполнялось бы равенство для $m=2$.
Пусть для $i=L$ выполнено неравенство $|a_L|\geqslant 1$,для четных $m$ из условия следует: $1\leqslant |a_L|\leqslant \sqrt [m]{m}.$Устремляя $m$ к бесконечности по четным $m$,получим $|a_L|=1.$Поэтому \sum \limits _{i\ne L}a_i^4=3<\sum \limits _{i\ne L}a_i^2=1$,противоречие,т.е. такой последовательности не существует.
B2.$AB_{min}=3$

[Юстас]

dm в сообщении #384262 писал(а):

[b]A6. Let $f:[0;\infty)\to\mathbb{R}$ be a strictly decreasing continuous functions such that $\lim_{x\to\infty}f(x)=0.$ Prove that $\displaystyle\int_0^{\infty}\frac{f(x)-f(x+1)}{f(x)}\,dx$ diverges.

$$\int_0^{\infty}\frac{f(x)-f(x+1)}{f(x)}\,dx\geq\lim_{A\to \infty}\int_0^A \int_{x+1}^x \frac{f'(y)}{f(x)}dydx \geq\lim \int_1^{A+1}\int_{y-1}^{y}\frac{f'(y)}{-f(x)}dxdy\geq \lim \int_1^{A+1}\frac{f'(y)}{-f(y)}dy=-\int \ln f(y)dy$$

[mihiv]

B4.Пусть $\alpha _i,i=1,\dots ,m$-корни полинома $p(x),$ а $\beta _j,j=1,\dots ,n$-корни полинома $q(x).$В равенстве (1):

$$p(x)q(x+1)-p(x+1)q(x)=1 \qquad (1)$$

положим сначала $x=\alpha _i$,а затем $x=\alpha _i-1$,получим $p(\alpha _i+1)q(\alpha _i)=-1,p(\alpha -1)q(\alpha _i)=1,$сложив полученные равенства получим $q(\alpha _i)[p(\alpha _i+1)+p(\alpha _i-1)]=0.$Т.к. $q(x)$ и $p(x)$ не имеют общих корней,то $p(\alpha _i+1)+p(\alpha _i-1)=0.$Видим,что полиномы $P(x)=p(x+1)+p(x-1)$ и $p(x)$ имеют одинаковые корни,а т.к. их степени равны,то $P(x)=cp(x).$Сравнивая коэффициенты при старших степенях $x$ находим $c=2.$Таким образом $p(x+1)+p(x-1)=2p(x)\text {или} p(x+1)-p(x)=p(x)-p(x-1)$.Отсюда следует,что $p(x+n+1)-p(x+n)=p(x+1)-p(x)$.Это возможно только если $p(x)=p_1x+p_0.\qquad (2)$
Точно также можно показать,что $q(x)=q_1x+q_0.\qquad (3)$Подставляя полученный вид полиномов в равенство (1) видим,что $p_0q_1-q_0p_1=1\qquad (4)$
Т.е. равенство (1) выполняется для полиномов вида (2),(3) коэффициенты которых связаны равенством (4).

[CrypticMath]

Если вас интересует, здесь решение: http://www.amc8.org/a-activities/a7-problems/putnam/-pdf/2010s.pdf