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

[maxal]

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



1. (Фольклор) $\cos\alpha = 1/3$. Докажите, что градусная мера угла $\alpha$ иррациональна.


2. (А.Канель) В пространстве расположено несколько плоскостей общего положения (никакие три не параллельны одной прямой, и все не пересекаются в одной точке). Они делят пространство на несколько частей и в каждой части записан знак - плюс или минус. Разрешается изменить все знаки во всех частях внутри любого тетраэдра, образованного данными плоскостями. Докажите, что за несколько операций можно сделать так, чтобы во всех ограниченных частях стояли плюсы.


3. (А.Скопенков) Вершины $A$ и $B$ графа $G$ назовем эквивалентными, если существует такая последовательность вершин $A=A_0,A_1,\dots,A_n=B$, что любые две соседние вершины $A_i$ и $A_{i+1}$ можно соединить $k$ путями без общих промежуточных вершин. Докажите, что любые две эквивалентные вершины можно соединить $k$ путями без общих ребер.


4. (А.Тартаковский) Пусть $a_1,\dots,a_n$\т положительные числа, $M$ - их среднее арифметическое, $G$ - их среднее геометрическое. Докажите, что для любого $1\le i\le n$ выполняется неравенство:

$$1+\rho < a_i/M < 1+\rho' \,,$$

где $\rho < 0$ и $\rho' > 0$ корни трансцендентного уравнения

$$(1+x)e^{-x} = (G/M)^n.$$

5. (Фольклор) Можно ли из трех стержней и нескольких нитей изготовить жесткую пространственную конструкцию так, чтобы стержни не соприкасались между собой, а были бы связаны нитками, прикрепленными к их концам?


6. (Теорема Лебега) Докажите, что монотонная функция дифференцируема в некоторой точке.

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


7. (Фольклор) a) Может ли определитель $10\times 10$ матрицы с коэффициентами $0, \pm 1$ превосходить $2007$?
б) (Задача на исследование.) Оцените максимально возможный определитель для матрицы $n\times n$ с коэффициентами $0, \pm 1$.


8. (А.В.Акопян) Пусть на плоскости даны два подобных и противоположно ориентированных треугольника с общим ортоцентром. Обозначим их через ${}_\triangle A_1B_1C_1$ и ${}_\triangle A_2B_2C_2$. Докажите, что прямые $A_1A_2, B_1B_2, C_1C_2$ имеют общую точку или параллельны друг другу.


9. (С.В.Охитин, А.Я.Белов) В клетках бесконечной целочисленной решетки стоят целые числа. Докажите, что сумма чисел в некотором квадрате делится на $2008$.

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


10. (В.Л.Попов, Э.Б.Винберг) Назовем множество $C$ перестановок $n$ элементов хорошим, если для любого ненулевого набора чисел $v_1,\dots,v_n$ такого, что $\sum_iv_i=0$, найдется такая перестановка $\pi$ из множества $C$, что $\sum_{i=1}^kv_{\pi(i)}>0$ для всех $k$ от $1$ до $n-1$. Если заменить строгое равенство на нестрогое, то получится определение неплохого множества. Какова мощность
наименьшего хорошего (неплохого) множества?
а) Мощность наименьшего неплохого множества равна $n$.
б) Существует хорошее множество мощности $n2^n$.
в) (открытая проблема) Доказать, что мощность хорошего множества экспоненциально велика по $n$.


11. (Теорема Абьянкара - Моха) Многочлены $P, Q$ и $R$ таковы, что $R(P(x),Q(x))\equiv x$. Докажите, что степень $P$ делит степень $Q$, либо степень $Q$ делит степень $P$.


12. (А.Я.Канель) Линейной рекуррентой порядка $n$ называется такая последовательность $\{u_k\}$, что при всех $k$

$$a_0u_{k+n}+a_1u_{k+n-1}+\dots+a_nu_k= 0,$$

где $a_i$ - некоторые константы, не все равные нулю одновременно.
Нулем линейной рекурренты называется такое $k$, что $u_k=0$. Докажите, что множество нулей линейной рекурренты есть объединение конечного набора точек и конечного набора арифметических прогрессий.

[RIP]

maxal писал(а):

4. (А.Тартаковский) Пусть $a_1,\dots,a_n$\т положительные числа, $M$ - их среднее арифметическое, $G$ - их среднее геометрическое. Докажите, что для любого $1\le i\le n$ выполняется неравенство:

$$1+\rho < a_i/M < 1+\rho' \,,$$

где $\rho < 0$ и $\rho' > 0$ корни трансцендентного уравнения

$$(1+x)e^{-x} = (G/M)^n.$$

Это задача из Пойя, Сегё, Задачи и теоремы из анализа, отд.II, зад. 97 (изд.1956г.).

maxal писал(а):

6. (Теорема Лебега) Докажите, что монотонная функция дифференцируема в некоторой точке.

Странно, теорема Лебега утверждает гораздо больше: монотонная функция почти всюду дифференцируема. Видимо, в таком виде задача сформулирована, чтобы не объяснять, что такое "почти всюду" .

maxal писал(а):

12. (А.Я.Канель) Линейной рекуррентой порядка $n$ называется такая последовательность $\{u_k\}$, что при всех $k$

$$a_0u_{k+n}+a_1u_{k+n-1}+\dots+a_nu_k= 0,$$

где $a_i$ - некоторые константы, не все равные нулю одновременно.
Нулем линейной рекурренты называется такое $k$, что $u_k=0$. Докажите, что множество нулей линейной рекурренты есть объединение конечного набора точек и конечного набора арифметических прогрессий.

Это Skolem-Lech-Mahler theorem.

[arqady]

maxal писал(а):

Задачи из номера 12 [

5. (Фольклор) Можно ли из трех стержней и нескольких нитей изготовить жесткую пространственную конструкцию так, чтобы стержни не соприкасались между собой, а были бы связаны нитками, прикрепленными к их концам?

Можно! 9 ниток хватит. Эта штука ( сам сделал! )стоит у меня на полке лет этак двадцать. Если не ошибаюсь, соответствующую конструкцию придумал венгерский архитектор.

[e2e4]

arqady писал(а):

maxal писал(а):

Задачи из номера 12 [

5. (Фольклор) Можно ли из трех стержней и нескольких нитей изготовить жесткую пространственную конструкцию так, чтобы стержни не соприкасались между собой, а были бы связаны нитками, прикрепленными к их концам?

Можно! 9 ниток хватит. Эта штука ( сам сделал! )стоит у меня на полке лет этак двадцать. Если не ошибаюсь, соответствующую конструкцию придумал венгерский архитектор.

Фотку в студию?

[arqady]

e2e4 писал(а):

Фотку в студию?

Бэвакаша:

[Руст]

Красиво. А нельзя сделать так, чтобы жёсткие стержни не касались? Так было бы ещё красивее.

[arqady]

Руст писал(а):

Красиво. А нельзя сделать так, чтобы жёсткие стержни не касались? Так было бы ещё красивее.

Присмотритесь. Они и не касаются!

[Sergic Primazon]

e2e4 писал(а):

arqady писал(а):

maxal писал(а):

Задачи из номера 12 [

5. (Фольклор) Можно ли из трех стержней и нескольких нитей изготовить жесткую пространственную конструкцию так, чтобы стержни не соприкасались между собой, а были бы связаны нитками, прикрепленными к их концам?

Можно! 9 ниток хватит. Эта штука ( сам сделал! )стоит у меня на полке лет этак двадцать. Если не ошибаюсь, соответствующую конструкцию придумал венгерский архитектор.

Фотку в студию?

Вообще это задачка из " Заочных математических олимпиад " № 1-11

[AD]

Фоменко на лекции демонстрировал такую штуку тоже. И по аудитории пускал.

[Sonic86]

Я правильно рассуждаю?:
$cos \alpha$ - алгебраическое тогда и только тогда, когда $\alpha=q*\pi$, где $q$ - рациональное. Данный косинус - рациональное число, значит его аргумент представляется в виде рациональное число умножить на $\pi$, то есть - трансцендентен.

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

Sonic86 писал(а):

$cos \alpha$ - алгебраическое тогда и только тогда, когда $\alpha=q*\pi$, где $q$ - рациональное.

С чего это Вы взяли?

Я, конечно, не до конца уверен, но мне кажется, что это верно только в одну сторону.

[RIP]

maxal писал(а):

1. (Фольклор) $\cos\alpha = 1/3$. Докажите, что градусная мера угла $\alpha$ иррациональна.

Предположим, что $\alpha=\frac{p\pi}q$, $p\in\mathbb Z$, $q\in\mathbb N$. Тогда $T_q(\cos\alpha)=(-1)^p$, где $T_q(x)=2^{q-1}x^q+\ldots\in\mathbb Z[x]$ - многочлен Чебышёва. Поскольку $\cos\alpha\in\mathbb Q$, то $2^{q-1}\cos\alpha=2^{q-1}/3\in\mathbb Z$ - так не бывает.

[Kid Kool]

maxal писал(а):

3. (А.Скопенков) Вершины $A$ и $B$ графа $G$ назовем эквивалентными, если существует такая последовательность вершин $A=A_0,A_1,\dots,A_n=B$, что любые две соседние вершины $A_i$ и $A_{i+1}$ можно соединить $k$ путями без общих промежуточных вершин. Докажите, что любые две эквивалентные вершины можно соединить $k$ путями без общих ребер.

Простое следствие теоремы Менгера.

Добавлено спустя 3 минуты 40 секунд:

maxal писал(а):

а) Мощность наименьшего неплохого множества равна $n$

Возьмем кучу единиц и одно отрицательное число. В неплохом множестве должна существовать перестановка, которая ставит отрицательное число в конек, всего перестановок будет не меньше n.

Добавлено спустя 4 минуты 53 секунды:

maxal писал(а):

б) Существует хорошее множество мощности $n2^n$.

Рассмотрим перестановки, которые ставят в конец любое подмножество нашего множества (всего их $2^n$). Тогда для любого набора найдется перестановка, ставящая все неположительные числа в конец. Это уже неплохое множество, проблему для его хорошести могут создавать нули в конце. Тогда каждую из наших перестановок размножим так, чтобы в конец ставилось любое число из подмножества, соответствующего перестановке. Теперь множество перестановок станет хорошим, его мощность будет меньше $n2^n$.

[maxal]

maxal писал(а):

7. (Фольклор) a) Может ли определитель $10\times 10$ матрицы с коэффициентами $0, \pm 1$ превосходить $2007$?
б) (Задача на исследование.) Оцените максимально возможный определитель для матрицы $n\times n$ с коэффициентами $0, \pm 1$.

// Решение этой задачи и сопутствующая дискуссия отделены в эту тему.

[maxal]

Решения задач 6 и 9 приведены в номере 20 (стр. 254-258).