Задачи из Математического Просвещения №14 (2010)

[maxal]

Задачи из номера 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 вернётся в исходную точку.

[ИСН]

На 6 - нет, контрпример легко переделать из этого: post300377.html#p300377

[Хорхе]

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$, получим правую часть, наоборот --- левую. Но я такие доказательства не очень люблю, а понять, что такого комбинаторного в правой части написано, чего-то не получается.

[Хорхе]

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 :)

[Dandan]

А если в 11 не $\mathbb R \times \mathbb R$, а $\mathbb N \times \mathbb N$ ?

[Профессор Снэйп]

Dandan в сообщении #347903 писал(а):

А если в 11 не $\mathbb R \times \mathbb R$, а $\mathbb N \times \mathbb N$ ?

topic29043.html

[Хорхе]

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

[maxal]

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$.

[Dandan]

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

[maxal]

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$.

[EtCetera]

maxal

maxal в сообщении #348144 писал(а):

Что-то здесь не так.

Видимо, имелось в виду, что размер матрицы равен числу цифр в искомом числе (т.е. в условии опечатка).

[maxal]

EtCetera в сообщении #348157 писал(а):

Видимо, имелось в виду, что размер матрицы равен числу цифр в искомом числе (т.е. в условии опечатка).

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

[EtCetera]

maxal

maxal в сообщении #348164 писал(а):

EtCetera в сообщении #348157 писал(а):

Видимо, имелось в виду, что размер матрицы равен числу цифр в искомом числе (т.е. в условии опечатка).

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

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

[ИСН]

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

[maxal]

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