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

[maxal]

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


1. (Ф. Ивлев) Можно ли в куб достаточно большой размерности с ребром 1 см вложить здание МГУ?

Решение приведено в номере 20 (стр. 264-265)


2. (А. Я. Белов)
а) Найти 300-ю цифру после запятой числа $\sqrt[3]{{0.\underbrace{99\dots 9}_{\text{\tiny 100 штук}}}}$.

б) С помощью калькулятора найти первую цифру числа $2^{10^6}$.


3.
а) (В. А. Сендеров) На плоскости дано множество $M$, площадь которого меньше $1$, и $n$ точек. Доказать, что множество $M$ можно сдвинуть на вектор, длина которого меньше $\sqrt{n/\pi}$, где $\pi=3,14159\dots\;$, так, что множество, полученное в результате сдвига, не будет покрывать ни одной из данных $n$ точек.

б) (Задача на исследование) Постарайтесь получить оценки для $n$-мерного пространства.


4. ${\cal A}$ -- отображение плоскости в себя, сохраняющее расстояние (т.е. $|XY|=|{\cal A}(X){\cal A}(Y)|$ для любых точек $X$, $Y$ плоскости). Доказать, что ${\cal A}$ -- отображение плоскости на себя (т.е. каждая точка имеет прообраз при этом отображении).


5. На плоскости нарисованы две а) пересекающиеся б) непересекающиеся окружности. Можно ли одной линейкой построить их центры?


6. Если целые $m$ и $n$ взаимно просты, а числа $x^n+x^{-n},x^m+x^{-m}$ -- ненулевые целые, то $x+1/x$ -- тоже целое число ($x\in {\mathbb C}$).
(условие исправлено согласно вып. 25)

7. (А. Я. Канель) На каждом ребре правильного многогранника $M$ с единичными ребрами взяли по точке $A_i$. Найти объем геометрического места центров масс таких наборов. Рассмотреть все 5~возможностей.


8. (D. Bakelin, В. А. Уфнаровский) Слова $u$ и $v$ циклически сопряжены, если $u=s_1s_2, v=s_2s_1$ для некоторых слов $s_1, s_2$. Слово $u$ называется правильным, если оно больше любого своего лексикографически сопряженного.
a) Докажите, что в любом правильном слове $u$ можно так однозначно расставить лиевы скобки $[\cdot,\cdot]$, что при их раскрытии ($[st]$ раскрывается как $st-ts$) слово $u$ будет старшим членом получившегося (некоммутативного) многочлена.

б) Докажите, что достаточно длинное слово содержит подслово вида $UXU$, где $U$, $X$ -- правильные слова.


9. (А. Я. Белов) Имеется $2^{n}-1$ коробок. B коробке первой величины содержатся две коробки второй величины. В каждой из $2^{k-1}$ коробок $k$-ой величины содержатся по две коробки $(k+1)$-ой величины. В коробках последней $n$-ой величины лежит по одной монете. За один ход разрешается в одной из коробок любой величины перевернуть все монеты. Доказать, что за $[n/2]+1$ ходов можно уравнять число монет, лежащих орлом вверх и орлом вниз. Можно ли улучшить эту оценку?


10. Дано векторное пространство $W$, $\dim(W)=m$, два его подпространства $U$ и $V$, такие что $U\cap V=0$ ($\dim(u)=n_1$, $\dim(v)=n_2$) и обратимый оператор $A\colon W\to W$. Докажите, что $A^n(U)\cap V=0$ при некотором $n\le \min(\binom{m}{ n_1},\binom{m}{ n_2})$.

Решение приведено в номере 19 (стр. 263)


11. Существует ли граф с хроматическим числом, большим 2013, все циклы которого имеют длину больше 2013?
(Хроматическое число графа есть минимальное число цветов, в которые его можно правильно раскрасить.)


12. (И. И. Богданов, Г. Р. Челноков) (Задача на исследование).
а) Дан многочлен $P(x,y)$ степени $n$ такой, что $P(x,y)\ge 0$ при всех $x,y$. При этом $P(x,y)=0$ только если $x=y=0$. Верно ли, что для некоторой константы $C>0$ выполняется неравенство $P(x,y)>C\cdot (|x|+|y|)^n$?

б) Для каких натуральных $m$ можно утверждать что для некоторой константы $C>0$ выполняется неравенство $P(x,y)>C\cdot (|x|+|y|)^m$ (при всех $x,y\in [-1,1]$)?

[Neos]

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

1. (Ф. Ивлев) Можно ли в куб достаточно большой размерности с ребром 1 см вложить здание МГУ?

1. Да, можно. В 4-х мерный куб. Лист любого формата можно вложить в "пустой" игральный кубик.
Толщина листа $=0$. Аналогично здание МГУ является гиперплоскостью в 4-х
мерном пространстве. Вернее - многоугольником на гиперплоскости.

Получилось так ((.

[ewert]

Neos в сообщении #768253 писал(а):

В 4-х мерный куб. Лист любого формата можно вложить в "пустой" игральный кубик.

Ну там другое имелось в виду -- что в $n$-мерный единичный кубик с гарантией вписывается трёхмерный шар радиуса $\frac1{3+\sqrt3}\sqrt{\frac{n-2}3}$ (если брать самую грубую оценку).

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

2. (А. Я. Белов)
а) Найти 300-ю цифру после запятой числа $\sqrt[3]{{0.\underbrace{99\dots 9}_{\text{\tiny 100 штук}}}}$.

Ну, 4. А в чём прикол?...

[ewert]

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

4. ${\cal A}$ -- отображение плоскости в себя, сохраняющее расстояние (т.е. $|XY|=|{\cal A}(X){\cal A}(Y)|$ для любых точек $X$, $Y$ плоскости). Доказать, что ${\cal A}$ -- отображение плоскости на себя (т.е. каждая точка имеет прообраз при этом отображении).

По-моему, проще доказать, что оно аффинно.

[Sonic86]

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

6. Если целые $m$ и $n$ взаимно просты, а числа $x^n+x^{-n},x^m+x^{-m}$ -- целые, то $x+1/x$ -- тоже целое число ($x\in {\mathbb C}$).

Для $n=2, m=3$ возьмем $x:=\exp\frac{\pi i}{6}$, тогда $x^2+x^{-2}=2\cos\frac{\pi}{3}=1\in\mathbb{Z}$, $x^3+x^{-3}=2\cos\frac{\pi}{2}=0$, но $x+x^{-1}=2\cos\frac{\pi}{6}=\sqrt{3}\not\in\mathbb{Z}$.

[nnosipov]

А оно, оказывается, вообще неверно (сначала подумалось, что очевидно). Что ж так неаккуратно задачи составляют ...

А что нужно добавить, чтобы стало верным? $x \in \mathbb{R}$ не поможет?

[Sonic86]

(Оффтоп)

nnosipov в сообщении #768422 писал(а):

А оно, оказывается, вообще неверно (сначала подумалось, что очевидно).

Мне тоже сначала показалось, а потом я вообще застрял там. Потратил на нее часа 3 Надеюсь, что я не ошибся нигде. Хотелось бы знать, что составители имели ввиду на самом деле

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

7. (А. Я. Канель) На каждом ребре правильного многогранника $M$ с единичными ребрами взяли по точке $A_i$. Найти объем геометрического места центров масс таких наборов. Рассмотреть все 5~возможностей.

Вот интересно, как ее с минимальными затратами решать?
Пока я смог только для куба - внутреннее тело получается тоже кубом с ребром в 3 раза меньшим, так что объем его в $1/3^3$ меньше. А вот для тетраэдра получается аж усеченный октаэдр (картинка есть в вики, и прочие параметры). Считать что-то для додекаэдра просто боюсь У него там штук 20 ребер...
Как считать само тело? Т.е. если в правильном многограннике $r$ ребер, то $r>\dim E^3$, получается проекция какого-то $r$-мерного тела в 3-хмерное, прообраз края - край, но часть края уходит внутрь образуемого тела. Отделить тот край, образ которого - тоже край в общем случае непонятно как. Можно делать так: пусть вектора ребер - $a_1,...,a_r$, считаем одну вершину $X$ и потом натягиваем на нее последовательно каркас из векторов:
$A_0:=X, A_1=A_0+a_1$
$A_{00}:=A_0, A_{01}:=A_1, A_{1I}=A_{0I}+a_2$
и т.п.
Т.е. на $k$-м шаге новый каркас - это старый каркас с параллельным переносом каркаса на $a_k$ и с ребрами переноса. Точек на $k$-м шаге получается $2^k$, но некоторые удается выбросить, если оказываются явно внутренними. Но даже так считать в голове трудно. В итоге я посчитал тело для треугольника - правильный шестиугольник, потом по симметрии перенес его в другие грани тетраэдра и там уже связал, посчитал число 6- и 4-хугольных граней, а потом уже погуглил но так решать не надо.

[Shadow]

nnosipov в сообщении #768422 писал(а):

А оно, оказывается, вообще неверно (сначала подумалось, что очевидно). Что ж так неаккуратно задачи составляют ...

Мои попытки:
Пусть $y=x+\frac 1 x, P_k=x^k+\frac{1}{x^k}$
Рекуррентная формула:
$P_k=yP_{k-1}-P_{k-2} \quad \eqno{(1)}$
$P_k$ - полином степени k с целыми коэффициентами и старший коэффициент 1. И т.к. $P_n \in Z$, если y рациональное, то оно целое.
$P_n \in Z \Rightarrow P_{an} \in Z \quad \forall a \in Z$ Аналогично $P_{bm} \in Z \quad \forall b \in Z$
И т.к. m,n взаимнопростые, найдутся $a,b: an-bm=\pm 1$ тоесть, два последовательные члена $P_k,P_{k-1}$ будут целыми. Сначала показалось, что этого достаточно для доказательства рациональности y (см. $\eqno{(1)}$), но нет - недостаточно, три надо. Три будут только при $n=2$
Формулу $\eqno{(1)}$ можно обобщить $P_{k+d}=P_k\cdot P_{d}-P_{k-d}$ Если для трех членов арифметической прогрессии с разностью d выражения рациональны, то $P_d$ тоже рационально. Напр. $n=4,m=7: P_{12},P_{14},P_{16} \in Z \Rightarrow P_2 \in Q$ но это работает только при четном n. И можно доказать $P_{n} \in Q \Rightarrow P_{n/2} \in Q$ Но когда m,n нечетные - доказательство у меня нет.
А раз неверно - и не будет.

[Dave]

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

1. (Ф. Ивлев) Можно ли в куб достаточно большой размерности с ребром 1 см вложить здание МГУ?

А какие габариты имеет здание МГУ в 4-м, 5-м и т.д. измерениях?

[ewert]

Dave в сообщении #768771 писал(а):

А какие габариты имеет здание МГУ в 4-м, 5-м и т.д. измерениях?

Ровно те же, что и в 3-м. Пафос не в этом, а в том, что, скажем, в обычный трёхмерный кубик можно запихать монетку большего диаметра, чем сторона кубика.

[Dave]

ewert в сообщении #768780 писал(а):

Ровно те же, что и в 3-м.

В смысле? 182 метра в направлениях $x_4$, $x_5$ и т.д.? Тогда вложить нельзя. Объём будет больше $1 \text{ см}^n$.

[ewert]

Dave в сообщении #768784 писал(а):

182 метра в направлениях $x_4$, $x_5$ и т.д.? Т

Я не знаю, что такое 4, 5 и т.д.; но послушайте: Вы что, сомневаетесь, что в кубик можно впихнуть бОльшую монетку?... а если не сомневаетесь в этом, то почему сомневаетесь в возможности дальнейшей экстраполяции?...

[Dave]

ewert в сообщении #768788 писал(а):

Я не знаю, что такое 4, 5 и т.д.;

В том-то и проблема. А задачу решаете так, как будто знаете.

ewert в сообщении #768788 писал(а):

Вы что, сомневаетесь, что в кубик можно впихнуть бОльшую монетку?

Не сомневаюсь. Если под словом "бОльшую" подразумевать бОльшую только в некоторых измерениях, а саму монетку, как и кубик, считать трёхмерными.

ewert в сообщении #768788 писал(а):

а если не сомневаетесь в этом, то почему сомневаетесь в возможности дальнейшей экстраполяции?...

Потому что для дальнейшей экстраполяции недостаточно данных.

[ewert]

Dave в сообщении #768804 писал(а):

А задачу решаете так, как будто знаете.

Да, я знаю. Каким бы ни был МГУ остронос и широко распространён -- он вписывается в некоторый вполне конкретный трёхмерный шар. И тогда вопрос сводится к следующему: можно ли вместить в кубик с фиксированным ребром трёхмерный (вообще любой фиксированной размерности) шарик сколь угодно большого радиуса, если взять достаточно большую размерность кубика?... -- ну можно, конечно.

Dave в сообщении #768804 писал(а):

а саму монетку, как и кубик, считать трёхмерными.

Монетка, естественно, двумерна. Как и МГУ трёхмерно. По умолчанию.

[Dave]

ewert в сообщении #768810 писал(а):

Каким бы ни был МГУ остронос и широко распространён -- он вписывается в некоторый вполне конкретный трёхмерный шар.

Наверняка можно утверждать только, что его сечение некоторым трёхмерным пространством вкладывается в некоторый шар в этом пространстве. Это если допустить существование других размерностей. А если не допускать, то и задача не имеет смысла.

ewert в сообщении #768810 писал(а):

Монетка, естественно, двумерна. Как и МГУ трёхмерно. По умолчанию.

Ни с первым, ни со вторым утверждением не соглашусь. И даже магическая фраза "По умолчанию" не убедит меня в этом .