2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задачи из Математического Просвещения №14 (2010)
Сообщение26.08.2010, 06:20 
Модератор
Аватара пользователя


11/01/06
5660
Задачи из номера 14 "Математического Просвещения". См. также задачи из номеров 10, 11, 12 и 13.


1. (А. Я. Белов) Дано бесконечное периодическое слово минимального периода $n$ и два его одинаковых подслова длины $n-1$. Доказать, что их начальные буквы находятся на расстоянии кратном $n$.


2. (В. И. Арнольд) Найти предел:
$$\lim\limits_{x\to 0} \frac{\sin\tg(x)-\tg\sin(x)}{\arcsin\arctg(x) - \arctg\arcsin(x)}.$$
Обсуждение: topic5462.html


3. (Фольклор) Бесконечное множество точек на плоскости таково, что все попарные расстояния целые. Докажите, что все точки лежат на одной прямой. А что если все попарные расстояния рациональны?
Обсуждение: topic8304.html


4. (И. Никокошев) Докажите, что при любых натуральных $n\ge l$ выполняется тождество:
$$ \frac{1}{l!}\sum_{\substack{\sum_{i=1}^lk_i=n;\\k_i\ge 1}} \frac{1}{k_1\cdot\ldots\cdot k_l} = \sum_{\substack{\sum_{i=1}^lk_i=n;\\ k_i\ge 1}}\frac{1}{k_1(k_1+k_2)\cdot\ldots\cdot (k_1+\dots+k_l)}.$$


5. (А. Я. Белов) Бесконечно Мудрый Таракан живёт на плоскости. Он близорук и потому видит Истину, только когда находится не более, чем в одном шаге от неё. Первоначально Таракан находится в $n$ шагах от Истины. Когда Таракан делает шаг, друзья говорят говорят ему, приблизился он к Истине, или нет.
а) Докажите, что, пользуясь этой и только этой информацией, Таракан может достичь Истины менее чем за $n+10\ln n$ шагов.
б) Докажите, что не существует алгоритма, позволяющего достичь Истины менее чем за $n+0.1\ln n$ шагов.


6. (Фольклор) $f(x,y)$ -- бесконечно дифференцируемая функция от двух переменных с локальным минимумом в нуле. Других критических точек у ней нет. Верно ли, что этот минимум глобальный? (Точка называется критической, если в ней обе частные производные $\partial f/\partial x$ и $\partial f/\partial y$ обращаются в нуль.)


7. (Н. И. Белухов) Пусть $q\ne 2^k+1$ -- натуральное число. Докажите, что в $q$-ичной системе счисления существует число, равное определителю $q\times q$ матрицы, составленной из цифр этого числа и их циклических перестановок.
Пусть $q$ -- натуральное число. Докажите, что для каждого нечётного делителя $d$ числа $q-1$ в $q$-ичной системе счисления существует $d$-значное число, равное определителю $d\times d$ матрицы, составленной из цифр этого числа и их циклических перестановок. Например, в десятичной системе счисления ($q=10$) для $d=3$ и $d=9$ такими числами являются:
$629 = \det \begin{pmatrix} 6 & 2 & 9 \\ 9 & 6 & 2 \\ 2 & 9 & 6 \end{pmatrix}$ или $456790123 = \det \begin{pmatrix}  4 & 5 & 6 & 7 & 9 & 0 & 1 & 2 & 3 \\ 3 & 4 & 5 & 6 & 7 & 9 & 0 & 1 & 2 \\ 2 & 3 & 4 & 5 & 6 & 7 & 9 & 0 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 9 & 0 \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 9 \\ 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\  7 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 7 & 9 & 0 & 1 & 2 & 3 & 4 & 5 \\ 5 & 6 & 7 & 9 & 0 & 1 & 2 & 3 & 4 \end{pmatrix}.$


8. (Ф. Ивлев) Дан $\triangle ABC$. $A_1, B_1, C_1$ -- точки касания сторон $BC, AC, AB$ с вписанной окружностью соответственно. $A_0, B_0, C_0$ -- середины сторон. Обозначим точку пересечения прямых $A_0B_0$ и $A_1B_1$ через $C'$. Аналогично определяются точки $A'$ и $B'$. Докажите, что прямые $A_1A'$, $B_1B'$ и $C_1C'$ пересекаются в точке Фейербаха.


9. (Фольклор) Докажите, что при игре «Жизнь» а) в квадрате $2010\times 2010$; б) на бесконечной плоскости; найдётся конфигурация без прообраза.


10. (С. В. Конягин) Докажите, что существует такое $x<4\cdot 99!$, что $x(x+1)$ делится на $100!$.


11. (Б. П. Панеях) Известно, что если зафиксировать одну переменную, то функция $f(x,y)$ по другой будет многочленом. Верно ли, что она будет сама многочленом от двух переменных?
Обсуждение: topic5072.html

12. (А. Я. Канель, М. Б. Скопенков) По некоторым рёбрам клеток плоской решётки проведены перегородки. Пьяница с равной вероятностью идёт из квадрата, где он находится, в любой соседний квадрат, куда он может пройти. Докажите, что он с вероятностью 1 вернётся в исходную точку.

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение27.08.2010, 15:05 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
На 6 - нет, контрпример легко переделать из этого: post300377.html#p300377

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение28.08.2010, 12:19 
Заслуженный участник
Аватара пользователя


14/02/07
2648
11. Ответ "да", довольно неожиданно. Посмотрим на $f_y(\cdot) = f(\cdot,y)$, $g_x(\cdot)=g(\cdot,y)$. Существует континуально много (хороших) $y$, для которых его степень одна и та же. Пусть эта степень $n$ и для каждого из этих $y$ $f_y(x)=a_n(y)x^n + \dots+a_0$. Снова возьмем какой-то континуальный набор (назовем их хорошими) $x$, что степень соответствующего многочлена от $y$ ограничена, скажем, числом $m$. Будем пытаться теперь искать $a_k(y)$ в виде $s_k(y) = b_{m\,k}y^m+\dots+b_{m\,0}$. Взяли теперь $n+1$ значение $x$ из хороших и нашли эти коэффициенты, приравняв их к коэффициентам многочлена $g_x(y)$. Получилось то, что надо. И вправду, для каждого хорошего $y$ многочлены $f_y(x)$ и $s_n(y)x^n + \dots + s_0(y)$ совпадают в $n+1$ точке, то есть совпадают. А так как хороших $y$ много, то кагбэ и все.

-- Сб авг 28, 2010 14:03:17 --

4 легко получается через двойную производящую функцию: она равна $(1-z)^{-u}$. Разложив сперва по $z$, потом по $u$, получим правую часть, наоборот --- левую. Но я такие доказательства не очень люблю, а понять, что такого комбинаторного в правой части написано, чего-то не получается.

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение28.08.2010, 14:23 
Заслуженный участник
Аватара пользователя


14/02/07
2648
10. Я могу доказать, что найдется число меньше $4\cdot 100!$, что $x(x+1)$ делится на $101!$ :)

-- Сб авг 28, 2010 15:50:27 --

Ага, для $100!$ тоже доказал; можно даже в пару раз улучшить оценку, поскольку, к счастью, $67$ -- простое

(спойлер)

, значит, $100!/67 = 66!33!=-1\cdot \pm 1=\mp 1\pmod{67}$ (в данном случае знак $ - $, посему можно взять $x=100!/67$).

В 2017 году, к столетию Великой октябрьской революции, можно давать эту задачу с числом 2017 :)

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение28.08.2010, 16:04 


24/03/07
321
А если в 11 не $\mathbb R \times \mathbb R$, а $\mathbb N \times \mathbb  N$ ?

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение28.08.2010, 16:49 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Dandan в сообщении #347903 писал(а):
А если в 11 не $\mathbb R \times \mathbb R$, а $\mathbb N \times \mathbb  N$ ?

topic29043.html

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение28.08.2010, 17:00 
Заслуженный участник
Аватара пользователя


14/02/07
2648
$\prod_{k=x}^{x+y} k$. Оно? Не, что-то не то. Лучше Профессора Снэйпа почитаю.

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение29.08.2010, 01:21 
Модератор
Аватара пользователя


11/01/06
5660
maxal в сообщении #347313 писал(а):
1. (А. Я. Белов) Дано бесконечное периодическое слово минимального периода $n$ и два его одинаковых подслова длины $n-1$. Доказать, что их начальные буквы находятся на расстоянии кратном $n$.

В виду периодичности без потери общности можно считать, что позиции этих подслов $0$ и $a>0$. Предположим, что $a$ не кратно $n$. Тогда для $d = a\bmod n$ имеем $0< d <n$.
В виду переодичности те же подслова длины $n-1$ находятся также на позициях $n\cdot k$ для всех неотрицательных целых $k$. При этом можно выбрать $k$ так, чтобы $a - n\cdot k = d$.

Итак, у нас есть слово $w=w_1w_2\dots$ с периодом $n$, причем $w_i = w_{i+d}$ для всех $0 < i < n$, что в совокупности с периодом $n$ эквивалентно равенствам $w_{i}=w_{i\bmod d}$ для всех $d < i < n+d$.
Понятно, что если при этом ещё $w_n = w_{n+d}$, то $d$ также является периодом $w$, что противоречит минимальности периода $n$. Поэтому $w_n\ne w_{n+d}=w_d.$
Пусть $m=\frac{d}{\gcd(n,d)}$ - минимальное целое число такое, что $mn\equiv 0\pmod {d}$. Тогда
$$w_n = w_{n\bmod d} = w_{n + (n\bmod d)} = w_{2n\bmod d} = \dots = w_{(m-1)n\bmod d}=$$
и, наконец,
$$= w_{n + ((m-1)n \bmod d)} = \dots = w_d,$$
противоречие. Поэтому наше предположение неверно, и $a$ обязано быть кратно $n$.

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение29.08.2010, 02:01 


24/03/07
321
это вообще относится к разделу Combinatorics on words. Там много интересных теорем и утверждений. Попробуйте, кто хочет, например, доказать, что слово Фибоначчи - непериодично.

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение29.08.2010, 16:03 
Модератор
Аватара пользователя


11/01/06
5660
maxal в сообщении #347313 писал(а):
7. (Н. И. Белухов) Пусть $q\ne 2^k+1$ -- натуральное число. Докажите, что в $q$-ичной системе счисления существует число, равное определителю $q\times q$ матрицы, составленной из цифр этого числа и их циклических перестановок. Например, в десятичной системе счисления ($q=10$)
$692 = \det \begin{pmatrix} 6 & 2 & 9 \\ 9 & 6 & 2 \\ 2 & 9 & 6 \end{pmatrix}$ или $456790123 = \det \begin{pmatrix} 4 & 5 & 6 & 7 & 9 & 0 & 1 & 2 & 3 \\ 3 & 4 & 5 & 6 & 7 & 9 & 0 & 1 & 2 \\ 2 & 3 & 4 & 5 & 6 & 7 & 9 & 0 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 9 & 0 \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 9 \\ 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 7 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 7 & 9 & 0 & 1 & 2 & 3 & 4 & 5 \\ 5 & 6 & 7 & 9 & 0 & 1 & 2 & 3 & 4 \end{pmatrix}.$

Что-то здесь не так. Во-первых, в приведённых примерах для $q=10$ матрицы не $10\times 10$ как того требует условие; во-вторых, для $q=6$ искомого 6-значного числа не существует (если только не разрешить ему начинаться с нулевых цифр - но в этом случае 1 дает решение для всех $q$, и задача становится бессодержательной). Если же отбросить требование размера $q\times q$, то опять же 1 дает решение для всех $q$.

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение29.08.2010, 17:02 
Заслуженный участник


28/04/09
1933
maxal
maxal в сообщении #348144 писал(а):
Что-то здесь не так.
Видимо, имелось в виду, что размер матрицы равен числу цифр в искомом числе (т.е. в условии опечатка).

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение29.08.2010, 17:36 
Модератор
Аватара пользователя


11/01/06
5660
EtCetera в сообщении #348157 писал(а):
Видимо, имелось в виду, что размер матрицы равен числу цифр в искомом числе (т.е. в условии опечатка).

Тогда 1 работает для всех $q$.

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение29.08.2010, 17:57 
Заслуженный участник


28/04/09
1933
maxal
maxal в сообщении #348164 писал(а):
EtCetera в сообщении #348157 писал(а):
Видимо, имелось в виду, что размер матрицы равен числу цифр в искомом числе (т.е. в условии опечатка).

Тогда 1 работает для всех $q$.
М-да, тогда вообще непонятно... Кстати, интересно, что в обоих примерах размер матрицы как раз $2^k+1$. Т.е. (если принять за аксиому, что примеры правильные, т.к. они довольно красивы и потому не случайны) подразумевалось более сложное условие, чем то, что пошло в печать.

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение29.08.2010, 18:55 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
В 5 тоже, кажется, подразумевалось какое-то более сложное условие.
Написал и тут же понял: я предполагал плоскость уже расчерченной на квадраты, а ведь это не так.

 Профиль  
                  
 
 Re: Задачи из Математического Просвещения №14 (2010)
Сообщение03.09.2010, 15:11 
Модератор
Аватара пользователя


11/01/06
5660
Условие задачи 7 исправлено, согласно авторскому тексту любезно предоставленному мне редакторами.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group