ТЮМ-2013

[Edward_Tur]

Задача № 18. «Окружности на плоскости».
Определите, какое наибольшее количество окружностей единичного радиуса можно расположить на плоскости так, чтобы выполнялись такие два условия:
а) расстояние между центрами каких-либо двух окружностей не больше чем 10;
б) для каждой из окружностей найдётся такая прямая, что эта окружность лежит по одну сторону от неё, а остальные окружности - по другую.

[Shadow]

Продолжим сторон правильного n-угольника ($n>4$) до их пересечения (для пятиугольника получится пентаграмма) и впишем в получившихся треугольников наши окружности. Условие б) выполнили. При четном $n$ центры противоположных окружностей и центр многоугольника лежат на одной прямой и тогда условие а) можно записать $R+r\le 5r$. Где R - радиус окружности вписанной в многоугольника, а r - радиус "наших" окружностей. Если нигде не ошибся в вычислениях для них получается условие $\tg{\frac{\pi}{n}} \ge \frac 1 2$ Выполняется до $n=6$.
При $n=7$ очень близко, а для нечетных условия немножко другие, но лень считать
Так что 6 можно, а скорее всего и 7.

[Edward_Tur]

Пускай на плоскости размещено $n$ окружностей единичного радиуса, удовлетворяющих условиям задачи. Центры этих окружностей образуют выпуклый $n$- угольник.
Его периметр несложно оценить снизу, используя неравенство Иенсена: $P\ge\frac{{2n}}{{\sin \left( {\frac{\pi }{n}} \right)}}.
С другой стороны, периметр этого $n$- угольника не превышает длину кривой постоянной ширины $d$, т.е. не превышает $\pi d$.
Получаем неравенство:

$$\frac{{2n}}{{\sin \left( {\frac{\pi }{n}} \right)}} \le \pi d.$$

Для $n=7$ и $d=10$ это неравенство не выполняется.

[Shadow]

Верно. Из любопытства вычислил и для нечетных. Для семиугольника получилось расстояние 10.357. Жаль.

[dm]

Все задачи: https://dl.dropboxusercontent.com/u/157 ... M_2013.pdf
финал: http://vk.com/wall5499034_1941

[Edward_Tur]

Задача № 21. «Наибольшее значение»
Пускай $n\ge2$. Найдите наибольшее значение выражения

$$\frac{{\sqrt {a_1^2 + 1} + \sqrt {a_2^2 + 1} + \ldots + \sqrt {a_n^2 + 1} }}{{{a_1} + {a_2} + \ldots + {a_n}}}$$

для положительных чисел ${a_1},{a_2}, \ldots ,{a_n}$ , удовлетворяющих условию ${a_1}{a_2} \cdot \ldots \cdot {a_n} = 1$.
Решение.

$$\frac{{\sum\limits_{i = 1}^n {\sqrt {a_i^2 + 1} } }}{{\sum\limits_{i = 1}^n {{a_i}} }} \le \frac{{\sum\limits_{i = 1}^n {\sqrt {a_i^2 + 1 + {{(\sqrt {{a_i}} - 1)}^4}} } }}{{\sum\limits_{i = 1}^n {{a_i}} }} = \frac{{\sqrt 2 \sum\limits_{i = 1}^n {({a_i} - \sqrt {{a_i}} + 1)} }}{{\sum\limits_{i = 1}^n {{a_i}} }} = \sqrt 2 + \sqrt 2 \cdot \frac{{n - \sum\limits_{i = 1}^n {\sqrt {{a_i}} } }}{{\sum\limits_{i = 1}^n {{a_i}} }} \le $$\le \sqrt 2 + \sqrt 2 \cdot \frac{{n - n{\sqrt[n]{{\prod\limits_{i = 1}^n {\sqrt {{a_i}} } }}}}}{{\sum\limits_{i = 1}^n {{a_i}} }} = \sqrt 2 .$$

[Edward_Tur]

Задача № 1. «Упрощение выражения»
Пускай задан многочлен $n$ -го степени с действительными коэффициентами и набор действительных чисел ${\lambda _1} < {\lambda _2} < \ldots < {\lambda _{n + 1}}$ . Упростите выражение

$$\varphi (x) = \sum\limits_{i = 1}^{n + 1} {{\alpha _i}Q\left( {x + {\lambda _i}} \right)},$$

где ${\alpha _i} = \prod\limits_{\scriptstyle j = 1\hfill\atop\scriptstyle j \ne i\hfill}^{n + 1} {{{\left( {{\lambda _i} - {\lambda _j}} \right)}^{ - 1}}} ,1 \le i \le n + 1$.
Решение:
Запишем многочлен $Q(x)$ через интерполяционный многочлен Лагранжа в точках ${b_1} < {b_2} < \ldots < {b_{n + 1}}$ :

$$Q(x) = \sum\limits_{i = 1}^{n + 1} {Q({b_i})\prod\limits_{j = 1j \ne i}^{n + 1} {\frac{{x - {b_j}}}{{{b_i} - {b_j}}}} }.$$

Разделив обе части тождества на $x^n$ и устремив $x \to \infty $, получим:

$${q_n} = \sum\limits_{i = 1}^{n + 1} {Q({b_i})\prod\limits_{j = 1j \ne i}^{n + 1} {{{({b_i} - {b_j})}^{ - 1}}} }$$

где $q_n$ - старший коэффициент многочлена $Q(x)$.
Теперь положим в последнем тождестве ${b_i} = x + {\lambda _i}$ . Тогда

$${q_n} = \sum\limits_{i = 1}^{n + 1} {Q(x + {\lambda _i})\prod\limits_{j = 1j \ne i}^{n + 1} {{{({\lambda _i} - {\lambda _j})}^{ - 1}}} } = \sum\limits_{i = 1}^{n + 1} {{\alpha _i}Q(x + {\lambda _i})}.$$

Ответ: $q_n$, где $q_n$ - старший коэффициент многочлена $Q(x)$.

[Edward_Tur]

Задача № 12. «Числовой автомат»
Числовой автомат «ТЮМ-XVI» может выполнять такие операции с натуральными числами :
1) вычесть из данного числа число 3 (если оно больше, чем 3);
2) умножить данное число на 3;
3) разделить данное число на 3 (если оно делится на 3 без остатка).
12.1 За какое наименьшее количество операций можно из числа 82 получить число 81?
12.2 За какое наименьшее количество операций можно из числа 81 получить число 82?
12.3 Аналогичный вопрос относительно получения числа $n$ из числа $m$.

[hippie]

Задача #13.
Рассмотрим последовательность $\{a_n\}_{n\ge 1}:\ \ a_1=0,\ a_2=\alpha,\ a_n=\lambda a_{n-1}+\mu a_{n-2},$ при $n\ge 3.$ Существуют ли такие натуральные $\alpha,\ \lambda$ и $\mu,$ при которых для каждого простого $p>2$ число $a_{p^2}$ делится на $p$ без остатка?

Предлагается доказать более сильное утверждение:

При любых целых положительных $\lambda$ и $\mu$ найдётся только конечное число простых чисел $p,$ при которых $a_{p^2}$ не кратно $p.$

(Следствие: при любых заданных целых положительных $\lambda$ и $\mu$ найдётся целое положительное $\alpha,$ такое, что для каждого простого $p$ число $a_{p^2}$ кратно $p.$)

[nnosipov]

hippie в сообщении #786476 писал(а):

Предлагается доказать более сильное утверждение:

При любых целых положительных $\lambda$ и $\mu$ найдётся только конечное число простых чисел $p,$ при которых $a_{p^2}$ не кратно $p.$

(Следствие: при любых заданных целых положительных $\lambda$ и $\mu$ найдётся целое положительное $\alpha,$ такое, что для каждого простого $p$ число $a_{p^2}$ кратно $p.$)

Это конечное множество составляют простые делители дискриминанта $\Delta=\lambda^2+4\mu$ характеристического трёхчлена $x^2=\lambda x+\mu$ и простые делители числа $\mu$. Положив $\alpha=\Delta\mu$, получим утверждение следствия.

[Sonic86]

hippie в сообщении #786476 писал(а):

Предлагается доказать более сильное утверждение:

При любых целых положительных $\lambda$ и $\mu$ найдётся только конечное число простых чисел $p,$ при которых $a_{p^2}$ не кратно $p.$

Ну и я добавлю (хотя уже все все поняли): $a_n=C_1\beta_1^n+C_2\beta_2^n$, $a_1=0 \Leftrightarrow C_2\beta_2=-C_1\beta_1$, $a_n=C_1\beta_1(\beta_1^{n-1}-\beta_2^{n-1})$. Тогда $p\mid a_{p^2}$ при $\beta_1^{p^2-1}\equiv \beta_2^{p^2-1}\pmod p$. Существует только конечное число $p:\beta_1\beta_2\equiv 0\pmod p$, а для $p:\beta\not\equiv 0\pmod p$ имеем $\beta^{p^2-1}\equiv 1\pmod p.$. Произведение оставшегося конечного множества $p$ берем в качестве $\alpha.$
upd:
$a_n=\alpha\frac{\beta_1^{n-1}-\beta_2^{n-1}}{\beta_1-\beta_2}, \beta_1\neq \beta_2$.
А вот при $\beta_1=\beta_2$ уже не получается. Например, для $\lambda=2,\mu=-1$ получаем $a_n=An+B$, для него утверждение неверно. Ну и в общем случае имеем $a_n=(An+B)\beta^n$ - для него тоже неверно $\Delta =0\Rightarrow \alpha \not >0$.

[nnosipov]

Фактически речь идёт о следующей теореме про последовательности Люка (аналог малой теоремы Ферма).

Пусть $U_0=0$, $U_1=1$, $U_n=\lambda U_{n-1}+\mu U_{n-2}$, при этом $\Delta=\lambda^2+4\mu \neq 0$, $\mu \neq 0$. Если нечётное простое $p$ не делит $\Delta$ и не делит $\mu$, то $U_{p-(\Delta/p)} \equiv 0 \pmod{p}$, где $(\Delta/p)$ --- символ Лежандра.

[Sonic86]

Edward_Tur в сообщении #786394 писал(а):

Задача № 12. «Числовой автомат»
Числовой автомат «ТЮМ-XVI» может выполнять такие операции с натуральными числами :
1) вычесть из данного числа число 3 (если оно больше, чем 3);
2) умножить данное число на 3;
3) разделить данное число на 3 (если оно делится на 3 без остатка).
12.1 За какое наименьшее количество операций можно из числа 82 получить число 81?
12.2 За какое наименьшее количество операций можно из числа 81 получить число 82?
12.3 Аналогичный вопрос относительно получения числа $n$ из числа $m$.

12.1. $82\xrightarrow{\cdot 3}82\cdot 3\xrightarrow{-3}82\cdot 3-3\xrightarrow{/3}(82\cdot 3-3)=81$ - $3$ операции
12.2. Можно так, не факт, что минимально:
$81\xrightarrow{/3\circ /3}9\xrightarrow{-3}6\xrightarrow{\cdot 3 \circ \cdot 3 \circ \cdot 3 \circ \cdot 3}486\xrightarrow{-3\circ ...\circ -3}246\xrightarrow{/3}82$ - всего $2+1+4+\frac{486-246}{3}+1=88$ операции.
upd:
Можно быстрее: $f(x):=3x, d(x):=x-3$, тогда $d^3f=fd$ и не всегда $f^{-1}d^3=df^{-1}$. Тогда цепочку преобразований $f^{-1}d^{80}f^4df^{-2}$ можно укоротить до $f^{-1}d^2fd^2fd^2fd^2fdf^{-2}$ из $16$ букв.

12.3. Определим машину «ТЮМ-XVIQ», которая может выполнять над элементами из $\mathbb{Q}$ операции $d,f,f^{-1}$. Если значение $\varphi(x)$ вычислимо (допустимо) на «ТЮМ-XVI», то она вычислимо и на «ТЮМ-XVIQ». С другой стороны, «ТЮМ-XVIQ» вообще не выдает Exceptionов при вычислении любого $\varphi(x)$. Несложно доказать, что над $\mathbb{Q}$ между $d,f$ существует единственное соотношение $d^3f=fd$ (переносим все $f$вправо, потом все $f^{-1}$ влево, получаем $w=f^{-a}d^bf^c$, тогда $(\forall x)w(x)=\frac{3^cx-3b}{3^a}=x$ только при $b=0, a=c$, т.е. при $w=e$). В таком случае кратчайшая программа для перевода $m$ в $n$ строится просто: строится хоть какая-то программа, переводящая $m$ в $n$, потом упрощается до $f^ad^b$, а потом с помощью укорачивающего соотношения $d^3f\to fd$ максимально укорачивается (т.е. при $a\leqslant 0$ программа оптимальна).

(Оффтоп)

В качестве решения наша компания предлагает Вам обновить машину «ТЮМ-XVI» до «ТЮМ-XVIQ»

upd2:
1) Хотя бы одна программа, переводящая $m$ в $n$ такая. Без ограничения общности предполагаем, что $m>n$, ведь если $m<n$, то увеличивая $m\to 3m\to9m\to...$ сведем случай $m<n$ к $m>n$. А в случае $m>n$ подходит такая программа: $m\to 3m\to 3m-3\to...\to 3m-(3m-3n)=3n\to n$, т.е. $f^{-1}d^{m-n}f$.
В итоге искомая программа $w=f^{-1}d^{m_1-n}ff^k, m_1=3^km\geqslant n$, $k$ можно взять $\lceil\log_3\frac{n}{m}\rceil$. Далее, перенося все $f$, кроме одной крайней влево, получаем сильно короткую, возможно, оптимальную программу. Для еще большего укорачивания ее можно также использовать соотношение $d^{3^a}=f^adf^{-a}$. Перенос допустим, поскольку наличие слева одной $f$ гарантирует делимость на 3 выражения $f(x)$, от которого считается все остальное
2) «ТЮМ-XVIQ» оставляет $\mathbb{Q}^-$ на месте, т.е. она не любое рациональное число может перевести в другое рациональное. Поэтому все-таки придется следить, чтобы разности $d$ не приводили к появлению отрицательных чисел
ошибки поисправлял

[Edward_Tur]

Задача № 6. «Геометрическое место точек»
Дана окружность $\omega$, на которой отмечены точки $A$, $B$ и $C$. Пускай $BF$ и $CE$ – высоты треугольника $ABC$, $M$ – середина стороны $AC$. Найдите геометрическое место точек пересечения прямых $BF$ и $ME$ для всевозможных положений точки $A$ на окружности $\omega$.

Решение: Будем считать, что у окружности $\omega$ радиус $R=1$ (все обозначения стандартны), $\alpha<90°$. Обозначим через $P$ точку пересечения прямых $BF$ и $ME$.
Заметим, что если $\alpha=45°$, то угол $AME=90°$ и прямые $BF$ и $ME$ не пересекаются, поэтому далее считаем, что $\alpha\ne45°$.
Пускай $A_1$ - такое положение точки $A$, что угол ${A_1}CB$ - прямой. Искомая точка пересечения $P_1$ лежит на прямой $BC$. Находим длину отрезка ${P_1}B$:
${P_1}B = {P_1}C + CB = 2\sin \alpha - \cos \alpha \tg 2\alpha = - {\sin ^3}\alpha /\cos 2\alpha$.
Введем обозначение: угол $XPB=\varphi$.
Пускай теперь вершина $A$ занимает произвольное место на дуге. Последовательно вычисляем:
$PB = FB - FP = c\sin \alpha + (\sin \alpha \cos \gamma - \cos \alpha \sin \gamma )\tg 2\alpha = \frac{{2{{\sin }^2}\alpha \cos (\alpha + \gamma )}}{{\cos 2\alpha }}$; $\frac{{BP}}{{B{P_1}}} = \frac{{2{{\sin }^2}\alpha \cos (\alpha + \gamma )}}{{\cos 2\alpha }}:\frac{{ - 2{{\sin }^3}\alpha }}{{\cos 2\alpha }} = - \ctg \alpha \cos \gamma + \sin \gamma$;
$\frac{{\sin \angle P{P_1}B}}{{\sin \angle {P_1}PB}} = \frac{{\sin({{180}^ \circ } - \varphi - ({{90}^ \circ } - \gamma ))}}{{\sin \varphi }} = \ctg \varphi \cos \gamma + \sin \gamma$.
Из теоремы синусов $ - \ctg \alpha \cos \gamma + \sin \gamma = \ctg \varphi \cos \gamma + \sin \gamma$; $(\ctg \varphi + \ctg \alpha )\cos \gamma = 0$.
Случай $\cos \gamma = 0$ ми уже рассмотрели, поэтому $\ctg \varphi + \ctg \alpha = 0$ и $\varphi = {180^ \circ } - \alpha$.
Таким образом, точка $P$ принадлежит дуге окружности, из которой отрезок ${P_1}B$ виден под углом $180°-\alpha$.

[Sergic Primazon]

Edward_Tur в сообщении #786557 писал(а):

Задача № 6. «Геометрическое место точек»
Дана окружность $\omega$, на которой отмечены точки $A$, $B$ и $C$. Пускай $BF$ и $CE$ – высоты треугольника $ABC$, $M$ – середина стороны $AC$. Найдите геометрическое место точек пересечения прямых $BF$ и $ME$ для всевозможных положений точки $A$ на окружности $\omega$.

$E$ - как основание высоты бежит по окружности с центром в середине $BC$ , а углы $\triangle BPE$ не изменяются. Поэтому точка $P$ бежит по указанной Вами окружности.