ДММ-2008 в УрГУ

[luitzen]

Задачи, за решение которых на олимпиаде по случаю Дня математика и механика на матмехе УрГУ давалось наибольшее число баллов.
Сам я не оттуда и решений не знаю .


Задача 8.
Убойная задача. Источник выдает последовательность независимых букв $A$ и $B$ с фиксированной вероятностью выдачи каждой из этих букв: $P(A)=p$ и $P(B) = 1-p$. Источник включили и он начал выдавать некоторую бесконечную последовательность этих букв. Букву $A$ в этой последовательности будем называть отдельно стоящей, если в этой последовательности и слева, и справа от неё стоят буквы $B$. Доля отдельно стоящих букв $A$ определяется, естественно, как предел $D=\lim\limits_{n\to\infty}\frac{K_n(A)}{n}$, где $K_n(A)$ — количество отдельно стоящих букв $A$ в начальном отрезке этой последовательности из $n$ штук букв. Как настроить источник, т. е. выбрать вероятность $P(A) = p$, так, чтобы доля $D$ была максимальной?

Задача 14.
Игорь Хальясмаа, выпускник матмеха 1985 года, живущий в городе Питтсбурге, просит помочь ему найти коэффициенты $b_n$ в разложении единицы в «почти ряд Фурье» $1\equiv \sum\limits_{n=1}^{\infty} b_n \sin (a_n x)$ на отрезке $[0,1]$, если $\{a_n\}$ – последовательность положительных корней уравнения $\tg(x) = 1/x$, упорядоченных по возрастанию. Помогите Игорю!

Задача 21.
Ещё одна трудная задача. Пусть $n$ – произвольное натуральное число. Докажите, что десятичную запись числа $n$ можно дополнить цифрами слева и справа так, что получится десятичная запись простого числа. Объясните, почему десятичную систему счисления в этой задаче можно заменить любой другой — на ваш выбор и по вашему вкусу.

Задача 23.
Однажды где-то в бескрайнем Тихом океане эсминец засёк вражескую подводную лодку на расстоянии трёх километров от себя. Янки не на шутку струхнули, подлодка тут же погрузилась и ушла на полной скорости прямым курсом в неизвестном направлении! Но скорость нашего эсминца ровно в два раза больше скорости подлодки!! Существует ли такая траектория движения эсминца, которая гарантирует его прохождение через некоторое время точно над подводной лодкой?

[bobo]

luitzen писал(а):

Задача 23.
Однажды где-то в бескрайнем Тихом океане эсминец засёк вражескую подводную лодку на расстоянии трёх километров от себя. Янки не на шутку струхнули, подлодка тут же погрузилась и ушла на полной скорости прямым курсом в неизвестном направлении! Но скорость нашего эсминца ровно в два раза больше скорости подлодки!! Существует ли такая траектория движения эсминца, которая гарантирует его прохождение через некоторое время точно над подводной лодкой?

Существует! Предположим, что эсминец знает, что направление лодки лежит в малом интервале углов $[\varphi, \varphi+\Delta\varphi]$. В этом случае легко построить кривую, удовлетворяющую условию задачи. Оценка максимального времени, за которое эсминец нагонит лодку дает $t_0=\frac{r_0}{v}(1+\frac{\Delta\varphi}{\sqrt{3}})$, где $r_0 =3$ км , $v-$скорость лодки. На всю плоскость решение легко можно распространить.
Хотя, наверное, лучше сразу сказать, что траэктория эсминца - два отрезка и спираль, начальная точка $A$ которой лежит на окружности радиуса $r_0$ с центром в точке, в которой была обнаружена лодка, и удовлетворяющая условию, что расстояние от любой точки $B$ этой спирали до окружности равно половине длины кривой $AB$.

[Юстас]

Задачу 8 решал бы так: пусть у нас есть рулетка с $n$ полями с буквами А и В, и вероятность А есть $p$. После каждого вращения рулетки мы видимо только поле, на котором остановился шар. Если шар на А, то мы имеем право посмотреть два соседних поля. Тогда вероятность попасть на отдельно стоящую А равна $p(1-p)^2$. Так как все испытания независимы, то по закону больших чисел среднее количество отдельно стоящих А будет в точности $p(1-p)^2$, соответственно максимум при $p=\frac13$.

[Sonic86]

Задача 21 легко решается с помощью теоремы Дирихле о бесконечности числа простых чисел в арифм прогресии.
Дописываем справа цифры так, чтобы новое число a длины L было взаимно просто с 2 и 5, а затем берем арифм прогрессию $10^L n+a$. И тода в ней - много простых чисел. Число n определяет цифры слева

Добавлено спустя 4 минуты 30 секунд:

Можно даже без теоремы Дирихле :
Так как число арифм прогрессий с заданным коэффициентов конечно, то среди них существует хотя бы одна, в которой число простых чисел бесконечно (в противном случае - конечно, что невозможно )

Добавлено спустя 5 минут 10 секунд:

В 14 задаче не знаю, точно или нет :
Почему нельзя просто найти координаты $b_k$ умножением на $sin(a_k n)$ и интегрировать на [0,1]. Они тогда будут выражаться через $a_n$. Не находите?

[TOTAL]

bobo писал(а):

luitzen писал(а):

Задача 23.
Однажды где-то в бескрайнем Тихом океане эсминец засёк вражескую подводную лодку на расстоянии трёх километров от себя. Янки не на шутку струхнули, подлодка тут же погрузилась и ушла на полной скорости прямым курсом в неизвестном направлении! Но скорость нашего эсминца ровно в два раза больше скорости подлодки!! Существует ли такая траектория движения эсминца, которая гарантирует его прохождение через некоторое время точно над подводной лодкой?

Хотя, наверное, лучше сразу сказать, что траэктория эсминца - два отрезка и спираль

Надо сразу гнать к точке обнаружения лодки, выходя на общий радиус $R=1$км, и тогда можно гарантированно проплыть над лодкой за

$$T=\frac{e^{\displaystile \frac{2\pi}{\sqrt{3}}}}{v}$$

. Но потопить лодку не сможем, т.к. лодку не видим и не узнаем, когда она окажется под нами. (Если бы видели, то не нужны никакие спирали, можно было бы плыть точно на лодку. То есть это очередной пример некорректной задачи.)

[Руст]

Sonic86 писал(а):

Задача 21 легко решается с помощью теоремы Дирихле о бесконечности числа простых чисел в арифм прогресии.
Дописываем справа цифры так, чтобы новое число a длины L было взаимно просто с 2 и 5, а затем берем арифм прогрессию $10^L n+a$. И тода в ней - много простых чисел. Число n определяет цифры слева

Это не арифметическая прогрессия. Для решения требуется знать нечто больше, чем теорема Чебышева, а именно, для любого $\epsilon >0$ и любых достаточно больших x, в интервале $(x,x+\epsilon x)$ существует простое число.
в 14. я не понял условие, так как при х=0 справа 0 (какие бы коэффициенты не взяли. Поэтому на замкнутом [0,1] интервале тождество не выполняется.

[Kid Kool]

Руст писал(а):

Это не арифметическая прогрессия.

А что же еще? $10^L n+a$ при постоянных a и L как раз и есть арифметическая прогрессия.

Руст писал(а):

Для решения требуется знать нечто больше, чем теорема Чебышева

Речь шла не о теореме Чебышева, а о теореме Дирихле о бесконечности количества простых чисел в арифметической прогрессии.

Добавлено спустя 3 минуты 52 секунды:

P.S. Это мы десятичную запись числа a дополняем цифрами, в данном случае слева. А справа нужно еще чего-нибудь дописать, чтоб число a оказалось взаимно простым с 10-ю.

[Руст]

Kid Kool писал(а):

Руст писал(а):

Это не арифметическая прогрессия.

А что же еще? $10^L n+a$ при постоянных a и L как раз и есть арифметическая прогрессия.

Руст писал(а):

Для решения требуется знать нечто больше, чем теорема Чебышева

Речь шла не о теореме Чебышева, а о теореме Дирихле о бесконечности количества простых чисел в арифметической прогрессии.

Добавлено спустя 3 минуты 52 секунды:

P.S. Это мы десятичную запись числа a дополняем цифрами, в данном случае слева. А справа нужно еще чего-нибудь дописать, чтоб число a оказалось взаимно простым с 10-ю.

В условии задачи речь идёт о дополнении числа n цифрами слева или справа. Соответственно число n фиксировано. Слева не удастся дополнять, если n делится на 2 или 5. Поэтому остаётся дополнять справа, т.е. рассмотреть числа $10^Ln+a, 0<a<10^L$ и доказать, что среди них найдётся хотя бы одно простоё, т.е. если $x=10^Ln$, то в интервале $(x,x+\epsilon x), \ \epsilon=\frac 1n.$ есть хотя бы одно простое.

[Kid Kool]

Руст писал(а):

в 14. я не понял условие

Наверное, там cos, а не sin

[TOTAL]

Kid Kool писал(а):

$10^L n+a$ при постоянных a и L как раз и есть арифметическая прогрессия.

Здесь $n$ - номер члена прогрессии, а не число, о котором говорится в условии.
Поэтому и путаница. Надо аккуратнее с обозначениями.

[Kid Kool]

Руст писал(а):

В условии задачи речь идёт о дополнении числа n цифрами слева или справа.

В условии задачи речь идёт о дополнении числа n цифрами слева и справа. Поэтому если n взаимно просто с 10, то теорема Дирихле говорит нам, что последовательность $10^Lx+n$, где L - количество цифр n, содержит бесконечно много простых.

Добавлено спустя 27 минут 22 секунды:

TOTAL писал(а):

Здесь $n$ - номер члена прогрессии, а не число, о котором говорится в условии.
Поэтому и путаница. Надо аккуратнее с обозначениями.

Я как раз об этом в P.S. и написал.

[bobo]

TOTAL писал(а):

Если бы видели, то не нужны никакие спирали, можно было бы плыть точно на лодку. То есть это очередной пример некорректной задачи.

Ну почему же? А если взять такую модель: эсминец и лодка - 2 материальные точки, причем над водой дальность видения эсминца равна бесконечности, а под водой - нулю Тогда, чтобы потопить лодку, все время движения по куску спирали нужно было бы сыпать какие-нибудь потроха, опасные только для лодки
Конечно, для физиков достаточно было бы потребовать одновременного нахождения лодки и эсминца в малой окрестности, но тогда, вроде, условие, что лодка будет идти по прямому курсу, было бы лишним.

[bobo]

Kid Kool писал(а):

Руст писал(а):

в 14. я не понял условие

Наверное, там cos, а не sin

Если там действительно косинусы, то при $k\neq 0$ функции $\cos (a_nx)$ и $\cos (a_{n+k}x)$ ортогональны на отрезке $[0,1]$ и все коэффициенты $b_n$ легко находятся после интегрирования.

[Kid Kool]

bobo писал(а):

при $k\neq 0$ функции $\cos (a_nx)$ и $\cos (a_{n+k}x)$ ортогональны на отрезке $[0,1]$

На отрезке $[-\pi,\pi]$ - соглашусь. А почему на [0,1]?

[bobo]

Нужно воспользоваться тем, что $\sin(a_{n+k}\pm a_n) = \sin a_n\sin a_{n+k}(a_n\pm a_{n+k})$