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

[maxal]

Задачи из номера 11 "Математического Просвещения".

1. (М.Панов) Вычислить

$$\int_0^\infty\frac{dx}{(1+x^2)(1+x^\pi)}.$$

2. (Р.М.Травкин) Назовем кубоидом выпуклый многогранник в трехмерном пространстве, комбинаторно эквивалентный кубу (т.е. существует взаимно однозначное соответствие между их вершиами, ребрами и гранями, сохраняющее примыкание). Рассмотрим для каждой грани точку пересечения отрезков, соединяющих середины противоположных сторон. Эти 6 точек являются вершинами некторого октаэдра. Какие значения может принимать отношение объема этого октаэдра к объему исходного кубоида?


3. (К.Шеннон) $A_1,\dots,A_n$ и $B_1,\dots,B_n$ -- два разбиения единичного квадрата на непересекающиеся измеримые множества. $S_{ij}$ -- пересечение множеств $A_i$ и $B_j$, $|G|$ -- площадь множества $G$. Докажите неравенство:

$$\sum_{ij}|S_{ij}|\cdot\ln(|S_{ij}|)\ge\sum_i |A_i|\cdot\ln(|A_i|)+\sum_{j} |B_{j}|\cdot\ln(|B_{j}|).$$

4. (А.Я.Канель) $d$-мерная ладья бьет по прямым вдоль осей координат.
а) Какое максимальное число ладей можно расставить в $d$-мерном кубе $n\times\dots\times n$ так, чтобы они не били друг друга?

Назовем расстановку ладей полной, если в ней максимально возможное число ладей.

б) Слоем трехмерного куба $n\times n\times n$ назовем квадрат $n\times n$, состоящий из клеток с одинаковой третьей координатой. Пусть первые $k$ слоев заполнены полно (т.е. в них стоят $nk$ ладьей). Докажите, что эту расстановку можно продолжить до полной расстановки всего куба. Верно ли аналогичное утверждение для четырехмерного куба?

в) В трехмерном кубе $n\times n\times n$ расставили ладьи и зафиксировали угловую клетку. Рассматриваются подкубы ($k\times k\times k$, для каждого $k$ один подкуб, всего $n$ подкубов) с этой угловой клеткой. В каждом таком подкубе оказывается некоторое число ладей из нашей расстановки, и в некоторых подкубах расстановка оказывается полной (т.е. стоит максимально возможное число для данного $k$). Каково максимальное число таких подкубов с полной расстановкой? Аналогичный вопрос для $d$-мерного куба.


5. (М.Концевич) Hа плоскости отметили $n$ непересекающихся отрезков и $n+2$ точки, которые не лежат на этих отрезках. Докажите, что найдутся две точки, которые "видят" друг друга (т.е. соединяющий их отрезок не пересекает отмеченные отрезки).


6. (Э.Туркевич) Обозначим через $s(n)$ сумму цифр числа $n$. Ограничена ли последовательность $s(n)/s(n^2)$?
Обсуждение: topic11591.html

7. (А.Я.Белов) Рассмотрим множество непрерывных функций на отрезке $[0,2n]$, таких, что $F(0)=0$ и на любом интервале $(k,k+1)$, $k\in\mathbb{Z}$, производная равна $\pm 1$.
a) Каких функций больше: неотрицательных или таких, что $f(2n)=0$?
b) Как подсчитать число функций, таких, что $-n/k < f(x) < n/k$?


8. (A.Kanel-Belov, J.Kaminsky, M.Taicher) В пространстве даны две гладкие кривые $C_1$ и $C_2$. Рассматривается множество $S$ прямых $l=(A,B): A\in C_1, B\in C_2$. Докажите, что если некоторая кривая $C_3$, непересекающаяся с $C_1\cup C_2$, пересекает каждую прямую из $S$, то обе кривые $C_1$ и $C_2$ лежат в одной плоскости.


9. (Д.Муштари) Можно ли множество рациональных точек единичной сферы раскрасить в два цвета (черный и белый) так, что если три точки отвечают концам трех ортогональных векторов, то одна из них будет черной, а две другие -- белыми?


10. (Фольклор) Пусть $A, B$ -- целочисленные матрицы. Известно, что $\det(A)=1$, $\det(B)\ne 0$. Докажите, что существует $n\in\mathbb{N}$ такое, что $B^{-1}A^nB$ -- целочисленная матрица.


11. (Фольклор) Дано $2n+1$ грузов попарно различной массы и чашечные весы без гирь. Докажите, что за $100n$ взвешиваний можно найти медиану (т.е. средний по массе груз).


12. (А.Белов, Г.Челноков) Двое по очереди на доске пишут многочлены от $n$ переменных. Запрещается писать многочлен $R$, если:
(1) $R$ представим в виде суммы кратных ранее написанных многочленов, т.е. $R=\sum_{i=1}^kR_iQ_i$ при некоторых $Q_i$;
(2) Единица представляется в виде суммы кратных написанных многочленов и кратного $R$:
$1=\sum_{i=1}^kR_iQ_i+RQ$ при некоторых $Q_i$, $Q$.
Проигрывает тот, кто не может сделать хода.
а) Докажите, что игра заканчивается.
б) Кто выигрывает при правильной игре?


Условие задачи 7.10 задачника "Математического просвещения" было сформулировано неточно. Приводим уточнение формулировки.
7.10. а) В пространстве даны две гладкие поверхности $S_1$ и $S_2$, заданные уравнениями $f=0$ и $f=1$ и гомеоморфные плоскости. Известно, что любую точку поверхности $S_1$ можно соединить с некоторой точкой поверхности $S_2$ такой ломаной длины не более $1$, которая находится в области $0<f<1$ (за исключением начальной и конечной точек). Можно ли установить взаимно однозначное и взаимно непрерывное соответствие между точками $S_1$ и $S_2$ так, чтобы соответствующие точки находились бы на расстоянии меньше $10^6$?

б) Аналогичный вопрос для плоскости ($S_0$ и $S_1$ -- линии уровня функции, гомеоморфные прямой).

[RIP]

maxal писал(а):

1. (М.Панов) Вычислить

$$\int_0^\infty\frac{dx}{(1+x^2)(1+x^\pi)}.$$

$$\int_0^\infty\frac{dx}{(1+x^2)(1+x^\alpha)}=\left(\int_0^1+\int_1^\infty\right)\frac{dx}{(1+x^2)(1+x^\alpha)}=$$

во втором замена $x\mapsto1/x$

$$=\int_0^1\frac{dx}{1+x^2}=\frac\pi4$$

для любого $\alpha$.

Решение задачи 6 перенесено в топик S(n)/S(n^2).

[RIP]

maxal писал(а):

3. (К.Шеннон) $A_1,\dots,A_n$ и $B_1,\dots,B_n$ -- два разбиения единичного квадрата на непересекающиеся измеримые множества. $S_{ij}$ -- пересечение множеств $A_i$ и $B_j$, $|G|$ -- площадь множества $G$. Докажите неравенство:

$$\sum_{ij}|S_{ij}|\cdot\ln(|S_{ij}|)\ge\sum_i |A_i|\cdot\ln(|A_i|)+\sum_{j} |B_{j}|\cdot\ln(|B_{j}|).$$

Известное неравенство. Надо просто переписать в виде

$$\sum_{i,j}|S_{ij}|\ln\frac{|A_i||B_j|}{|S_{ij}|}\leqslant\sum_{i,j}|S_{ij}|\left(\frac{|A_i||B_j|}{|S_{ij}|}-1\right),$$

где суммирование идет по тем i,j, для которых $|S_{ij}|>0$.

[Батороев]

maxal писал(а):

4. (А.Я.Канель) $d$-мерная ладья бьет по прямым вдоль осей координат.
а) Какое максимальное число ладей можно расставить в $d$-мерном кубе $n\times\dots\times n$ так, чтобы они не били друг друга?

Назовем расстановку ладей полной, если в ней максимально возможное число ладей.

Хочу лишь сверить свои измышления с чужими размышлениями.
"Ладьи бьют" - это, когда $ (d - 1) $ координат одной ладьи совпадают с таким же количеством координат другой ладьи?
Если так, то, если обозначить координаты всех ячеек $d$-мерного куба через числа от $ 0 $ до $ (n^d - 1) $ в n-чной системе счисления, то у координат ладей не должны совпадать цифры в любых $ (d - 1) $ разрядах. Это возможно, как мне кажется, максимально только для $ n^{(d-1)} $ ладей.
А может я ошибаюсь, т.к. ни разу не видел $d$- мерный куб, больше $ d = 3 $

[sergey1]

8. Если кривая Пеано - это кривая, то С1 и С2 не обязаны лежать в одной плоскости. В качестве С1 и С2 можно тогда взять противоположные ребра правильного тетраэдра, а кривой Пеано заполнить квадрат свершинами в серединах остальных ребер.

[RIP]

maxal писал(а):

10. (Фольклор) Пусть $A, B$ -- целочисленные матрицы. Известно, что $\det(A)=1$, $\det(B)\ne 0$. Докажите, что существует $n\in\mathbb{N}$ такое, что $B^{-1}A^nB$ -- целочисленная матрица.

Пусть $m=|\det B|$. $SL_{\cdot}(\mathbb{Z}_m)~-$ конечная группа, пусть её порядок равен $n$. Тогда $A^n\equiv I\pmod m$. Поскольку $mB^{-1}~-$ целочисленная матрица, то $mB^{-1}A^nB\equiv mB^{-1}IB\equiv0\pmod m$, т.е. матрица $B^{-1}A^nB$ целочисленная.