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

[maxal]

Задачи из номера 18 "Математического Просвещения". См. также задачи из номеров 10, 11, 12, 13, 14, 15, 16, 17.

1. На плоскости начерчен угол величиной в $n$ градусов, где $n$, $n < 180$, — натуральное число.

а) Для каких $n$ этот угол можно разделить с помощью циркуля и линейки на $n$ равных углов?

б) Пусть $m$ — произвольное натуральное число. Для каких $n$ данный угол можно разделить с помощью циркуля и линейки на $m$ равных углов?

в) Пусть $m$ и $n$ — натуральные взаимно простые числа, причём $m/n<180$, и $k$ — ещё одно натуральное число. На плоскости начерчен угол величиной в $m/n$ градусов. Для каких $k$ данный угол можно разделить с помощью циркуля и линейки на $k$ равных углов?
(Г. А. Гальперин)


2. Последовательность функций задана следующим образом:

$$Q_1(x) = x,\qquad Q_{n+1}(x) = \frac{Q_n(x + 1)}{Q_n(x)}.$$

Пусть

$$Q_n(x) - 1 = \frac{A(x)}{B(x)},$$

где $A(x)$, $B(x)$ — многочлены. Найдите отношение старших членов этих многочленов.
(А. А.Шапиро)


3.
а) Пусть $\Pi$ — $d$-мерный параллелепипед. Найдите сумму количеств граней параллелепипеда $\Pi$ всех возможных размерностей:
(число вершин) + (число рёбер) + (число двумерных граней) + (число трёхмерных граней) + ... + (число $(d - 1)$-мерных граней).
Ответ дайте в замкнутой форме (без знаков суммирования, индексов и т. п.).

б) $d$-Мерный параллелепипед $\Pi$ («дом») с размерами $n_1 \times n_2 \times n_3 \times \dots \times n_d$ разделён гиперплоскостями, параллельными его рёбрам, на единичные кубики («квартиры»). У каждой квартиры имеются вершины, одномерные рёбра, а также грани всех остальных размерностей, начиная с двумерных и кончая $(d - 1)$-мерными, — назовём их все «стенками» (размерностей $k = 0, 1, 2, \dots, d - 1$). Стенка, общая для двух или большего числа квартир, считается за одну. Найдите сумму количеств всех стенок у всех квартир дома $\Pi$. Ответ дайте в замкнутой форме (без знаков суммирования, индексов и т. п.).
(Г. А. Гальперин)


4. Даны положительные числа $x_1, \dots, x_n$; $a$ — их среднее арифметическое, $b$ — их среднее геометрическое. Обозначим через $M_3$ среднее арифметическое их кубических корней, через $D_1$ — средний квадрат уклонения чисел $x_i$ от $a$, т. е.

$$D_1 = \sum_{i=1}^n \frac{(x_i - a)^2}{n},$$

и через $D_3$ — средний квадрат уклонения кубических корней чисел $x_i$ от $M_3$, т. е.

$$D_3 = \sum_{i=1}^n \frac{(x_i^{1/3} - M_3)^2}{n}.$$

Докажите неравенства:

а) $\frac{n \cdot D_1}{n - 1} \leq a - b \leq n \cdot D_1$;

б) $(\frac{n}{n-1})^2\leq a-b \leq\frac{n^2}{n-1}\cdot M_3\cdot D_3$ при $n \geq 3$.
(А. Д. Беренштейн)


5. Дано выпуклое тело $T$ в пространстве и точка $M$ внутри него. Докажите, что найдётся плоское сечение $T$, для которого $M$ есть центр тяжести.
(М. Л. Концевич)


6. Город имеет форму квадрата, разделённого на $n^2$ квадратных кварталов. Улицы (двусторонние) идут между кварталами от одного края города к другому, и вокруг города идёт односторонняя улица. Велосипедист едет по городу, соблюдая правила уличного движения, то есть едет по правой стороне улицы, и на перекрёстках не поворачивает налево (на внешней односторонней улице он может ехать только так, что дома находятся справа от него). При каких $n$ можно утверждать, что велосипедист может объехать весь город, побывав на каждой стороне каждой улицы по одному разу (на внешней улице — на её единственной стороне)? Постарайтесь найти возможно более широкий класс таких $n$.
(Фольклор)


7. Пусть $P(x)\ne \text{const}$ — многочлен с целыми коэффициентами. Докажите, что существует бесконечно много простых чисел вида $4k + 1$, делящих его значение в целой точке.
(И. И. Богданов)


8. На полке в некотором порядке стоят тома, пронумерованные числами от 1 до $n$. Библиотекарь берёт том, стоящий не на своём месте, и ставит его на правильное место; при этом некоторые тома сдвигаются.

а) Докажите, что процесс перестановки томов остановится. (Фольклор)

б) Постарайтесь получить оценку на число шагов этого процесса, например полиномиальную. (А. Я. Белов)

Обсуждение: http://dxdy.ru/topic20141.html


9. (Задача на исследование).

а) Из бесконечно тонкой проволоки спаяли каркас многогранника $M$, который считается жёстким (хотя и сделан из бесконечно тонкой проволоки). Существует ли прорезь на плоскости $\alpha$, через которую этот многогранник можно протащить насквозь? (Плоскость не должна распадаться на части. «Протащить насквозь» означает переместить многогранник из верхнего полупространства в нижнее непрерывным движением так, чтобы в каждый момент времени пересечение $M \cap \alpha$ содержалось внутри прорези.) Рассмотрите случай каждого из пяти правильных многогранников, а также проволочный каркас решётки $n \times n \times n$, состоящий из $n^3$ единичных кубиков.

б) А существует ли клубок проволоки (т. е. связный набор отрезков, спаянных вместе произвольным образом), который нельзя протащить сквозь плоскость $\alpha$ ни через какую прорезь, проделанную в $\alpha$?
(М. М. Белова, А. Я. Белов)


10. Какую наибольшую размерность может иметь векторное подпространство пространства $(n\times n)$-матриц над полем вещественных чисел, состоящее только из вырожденных матриц?
(Фольклор)


11. Найдите $\int_0^1 \ln(- \ln x) dx$.
(Фольклор)


12. Двое художников играют в следующую игру. На каждом шаге первый художник отмечает произвольную точку на плоскости и соединяет её дугами с некоторыми ранее отмеченными точками (быть может, ни с одной); при этом пересекать ранее проведённые дуги нельзя. Второй художник красит поставленную первым художником точку так, чтобы все уже соединённые точки были раскрашены в разные цвета. Пусть $n$ — произвольное натуральное число.

а) Может ли первый художник заставить второго использовать более $n$ цветов?
(В. К. Ковальджи)

б) Верно ли, что он может сделать это за полиномиальное по $n$ число шагов?
(А. Я. Белов)


Решения задач 2, 7, 10 приведены в номере 19 (стр. 264-267)

[worm2]

5.
(чтобы к формулировке задачи нельзя было придраться, нужно ещё потребовать ограниченности $T$).
Рассмотрим для начала всевозможные радиус-векторы от $M$ до границы $T$.
Утверждение 1. Их концы будут непрерывно зависеть от их направлений (ну то есть типа от их углов в сферической системе координат, вот это вот всё).
Доказательство утверждения 1 идеологически довольно простое, но немножко муторное.
Пусть $M$ входит в $T$ вместе с шаром радиуса $\varepsilon$, а расстояние от $M$ до любой точки $T$ не превосходит $R$.
Лемма. Прямая, проходящая через две любые точки $X_1$ и $X_2$, лежащие на границе $T$, не может пересекать указанный шар, кроме случая, когда точка пересечения лежит между $X_1$ и $X_2$ (добавлено позже).
Доказательство леммы. В противном случае малым шевелением прямой мы можем получить отрезок, один конец которого лежит внутри шара (а значит, внутри $T$), второй на $X_1$ (для определённости — наиболее удалённая из этих двух от $M$ точка границы), а где-то внутри этого отрезка есть точка (близкая к $X_2$), лежащая вне $T$ (напомню, $X_2$ — граничная для $T$), что противоречит выпуклости $T$.
Следствие леммы. Угол между $X_1M$ и $X_1X_2$ (в условиях леммы), всегда не меньше угла $\varphi_0$, такого, что $\sin\varphi_0=\varepsilon/R$.
Итак, возьмём два радиус-вектора, $\overrightarrow{MX_1}$ и $\overrightarrow{MX_2}$, заканчивающихся на границе, угол между которыми, $\alpha$, мал. Для определённости пусть $|MX_1|\geqslant|MX_2|$. По теореме синусов:

$$|X_1X_2|=|MX_2|\frac{\sin\alpha}{\sin\angle MX_1X_2}\leqslant R\frac{\sin\alpha}{\sin\varphi_0}=\frac{R^2}{\varepsilon}\sin\alpha\,,$$

что и есть непрерывная зависимость от углов.
(добавлен не рассмотренный ранее случай). Случай, когда точка пересечения ($A$) прямой $X_1X_2$ с $\varepsilon$-шаром лежит между $X_1$ и $X_2$, придётся рассмотреть отдельно. Можно считать, что $A$ — ближайшая к $M$ точка отрезка $X_1X_2$, так что углы $X_1AM$ и $X_2AM$ прямые. $|X_1X_2|=|X_1A|+|X_2A|\leqslant \varepsilon (\tg\angle X_1MA+\tg\angle X_2MA) < \varepsilon \tg\alpha$ (пользуемся тем, что угол $\alpha$ мал)
Утверждение 1 доказано.

Непрерывная зависимость радиус-векторов влечёт непрерывную зависимость центров тяжестей сечений. Следует из того, что границу можно рассматривать как $2\pi$-периодическую функцию в полярной системе координат на плоскости, а центр тяжести можно получить из этой функции некоторым интегралом (надо ли разжёвывать подробнее?).

Приступим к доказательству утверждения задачи от противного. Пусть не существует такого положения плоскости, проходящей через $M$, что центр тяжести сечения совпадает с $M$. Тогда существует минимальное расстояние $r_0>0$, на которое центры тяжести всевозможных сечений подходят к $M$. Каждая плоскость характеризуется своей единичной нормалью, сопоставим этой нормали вектор $\overrightarrow{r}$, начинающийся в $M$ и заканчивающийся в центре тяжести её сечения. В силу того, что всегда $|\overrightarrow{r}|\geqslant r_0$, зависимость этого вектора от нормали непрерывна. Далее применяем теорему о причёсывании ежа и приходим к противоречию.

[DeBill]

1. Была такая детская задача: разделить угол в 19 градусов на 19 равных частей ($19 \cdot 19 = 361...$). Такое впечатление, что кроме этого фокуса (у$k$атерения) и деления пополам, ниче мы боле и не можем. И - что?

2. Смотрение на первые четыре члена приводит к мысли, что $Q_{n+1} (x) = 1 + \frac{\alpha _n}{x^n} + \frac{\varphi _n}{x^{n+1}} + ...$, и надо найти $\alpha _n$.
Ну, и найдем по индукции: $Q_{n+2} = \frac{Q_{n+1} (x+1)}{Q_n (x)} = \frac{1+\frac{\alpha _n}{(x+1)^n} + \frac{\varphi _n}{(x+1)^{n+1}} + ...}{1+\frac{\alpha _n}{x^n} + \frac{\varphi _n}{x^{n+1}} + ...} = 1 - \frac{n \alpha _n}{x^{n+1} } + ...$, так что $\alpha _{n+1} = -n\cdot \alpha _n$. Окончательно:
$\alpha _n = (-1)^{n-1} \cdot (n-1)!$. Потому ответ $(-1)^n \cdot (n-2)!$

-- 06.04.2016, 15:09 --

11. Заменой $t= -\ln x$ сведем интеграл к $\int\limits_{0}^{\infty} \ln t \cdot e^{-t} dt$. Но это есть $\Gamma ' (1)$...

-- 06.04.2016, 15:18 --

worm2 в сообщении #1112643 писал(а):

Далее применяем теорему о причёсывании ежа и приходим к противоречию.

Вроде, все хорошо: вектор $\overrightarrow{r}$ касается сферы в точке нормали. Но вот что странно: одномерного ежа причесать можно, так что (в четномерном пространстве) док-во почему-то не проходит (хотя утверждение - по крайней мере, на плоскости (сделаем центральную симметрию)- верно)...

-- 06.04.2016, 15:34 --

worm2
Т.е., для пространства четной размерности, надо как-то задействовать факт, что для противоположных нормалей центр масс один и тот же (т.е., мы имеем отображение из $\mathbb{R}P^n$ в $S^n$...

[worm2]

DeBill
, у меня был такой вариант, но я не довёл его до конца. При вращении плоскости вокруг фиксированной прямой центр тяжести обязательно должен пересечь эту прямую. Пытался, повращав теперь уже эту прямую, доказать, что центр тяжести на ней по непрерывности переходит через ноль. Но там возникла сложность, связанная с тем, что таких точек пересечения могло быть несколько, поэтому нельзя так просто сказать, что одна точка непрерывно переходит именно в противоположную себе.

[maxal]

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

8. На полке в некотором порядке стоят тома, пронумерованные числами от 1 до $n$. Библиотекарь берёт том, стоящий не на своём месте, и ставит его на правильное место; при этом некоторые тома сдвигаются.
а) Докажите, что процесс перестановки томов остановится. (Фольклор)

б) Постарайтесь получить оценку на число шагов этого процесса, например полиномиальную. (А. Я. Белов)

Эту задачу мы обсуждали в теме сортировка случайными вставками.

[DeBill]

$9\frac{a}{2}$ . Тетраэдр и куб - легко. Большой куб: сделаем горизонтальный разрез длины $n$, и перпендикулярно из него $n+1$ длинненьких разреза вверх-вниз. Чуток наклоним большой куб, так, что ребро одно осталось горизонтальным, и будем пихать в дырку: сначала - горизонтальное ребро. Пихаем дальше пока кака-нибудь поперечина не уткнется в плоскость. Подведем ее к горизонтальному разрезу, просунем, пихаем дальше,....
А как дюдю и исю?

-- 07.04.2016, 01:54 --

10. $n^2 - n$ Пример: матрицы с нулевой первой строкой.
Оценка: пусть - больше. Тогда это пространство - множество общих нулей менее чем $n$ линейных функционалов $f_m, m = 1,..., s < n$. Линейный функционал на пространстве матриц $\{Q\}$ имеет вид $f_m(Q) = \varphi _m(Q\cdot a_m)$, где $a_m$ - вектор, $\varphi_m$ - ковектор (таких - по размерности - как раз $n^2$). Устроив процесс ортоганализации векторов $a_m$ (и, соответственно заменяя функционалы линейными комбинациями исходных), сделаем эти вектора $a_m$ ортогональными или совпадающими. Выберем в $\mathbb{R} ^n$ орто-базис так, что все эти $a_m$ были первыми $j$ векторами базиса, $j\leqslant s$. Будем строить матрицу $Q$:первая строка - базисный вектор, отличный от $a_1$, второй - отличный от первого, и от $a_2$, третий - отличный от построенных и от $a_3$, и т.д.. Поскольку $s<n$, то построим невырожденную матрицу, на которой все функционалы занулятся - противоречие.

[EtCetera]

3, а) Требуется найти $S_n-c_n^{\left<n\right>}=S_n-1$, где $S_n=\sum\limits_{k=0}^n c_k^{\left<n\right>}$, $c_k^{\left<n\right>}$ — количество граней размерности $k$ у параллелепипеда размерности $n$, $c_k^{\left<n\right>}=2c_k^{\left<n-1\right>}+c_{k-1}^{\left<n-1\right>}$, $c_{-1}^{\left<n\right>}=0$, $c_k^{\left<n\right>}=0$ при $k>n$. Тогда $S_n=2S_{n-1}+S_{n-1}=3S_{n-1}=3^nS_0=3^n$. Ответ: $3^n-1$.

[EtCetera]

3, б) Сначала показалось, что тут нужна какая-то особая хитрость, но, вроде бы, все точно так же получается, как и в а). Ключевое рекуррентное соотношение в данном случае можно переписать так: $c_k^{\left<n\right>}\left[A_n\right]=(a_n+1)c_k^{\left<n-1\right>}\left[A_{n-1}\right]+a_n c_{k-1}^{\left<n-1\right>}\left[A_{n-1}\right]$. Здесь $A_n$ — кортеж из $n$ первых размеров «дома»: $a_1, a_2, \ldots, a_n$. Тогда аналогичным образом получаем, что

$$S_n\left[A_n\right]=(a_n+1)S_n\left[A_{n-1}\right]+a_nS_n\left[A_{n-1}\right]=(2a_n+1)S_n\left[A_{n-1}\right]=\prod\limits_{m=1}^n(2a_m+1),$$

где $a_m$ ($m=1\ldots n$) — размеры «дома».

[EtCetera]

Чтобы получить искомый ответ, из $S_n\left[A_n\right]$, разумеется, нужно вычесть количество $n$-мерных «стенок» (точнее, «комнат»): $c_n^{\left<n\right>}\left[A_n\right]=\prod\limits_{m=1}^n a_m$.

[VAL]

DeBill в сообщении #1112691 писал(а):

1. Была такая детская задача: разделить угол в 19 градусов на 19 равных частей ($19 \cdot 19 = 361...$). Такое впечатление, что кроме этого фокуса (у$k$атерения) и деления пополам, ниче мы боле и не можем. И - что?

Не понял, что такое у$k$атерение. Умножение на $k$?
Что же до исходной задачи, то она, очевидно, разрешима для всех $n$, взаимно простых с 15.

Это я про первый пункт. А во втором что-то с буковками не так.

[EtCetera]

Предлагаю решить аналогичную 3, а) задачу для симплекса и гипероктаэдра.