Самопересечения замкнутой ломаной

30

вигационных сил. Оцените время образования звезд из гигантского сферического obлака космической пыли плотностью $Q = 2 \cdot 10^{-20} \text{ e/cm}^3$. Можно считать, что при скатии частицы не обойтиют друг друга. Гравитационная постоянная $G = 6,67 \times 10^{-11} \text{ H} \cdot \text{m}^2/\text{кг}^2$.

И. Ш. Слободцкого и В. А. Орлова «Весоизные олимпиады по физике»). Поскольку по условию задачи, частицы не обгоют друг друга, суммарная масса, притягивающая нашу частицу, остается неизменной. Предположим, что все эта масса сосредоточена в центре obлака. тогда задача сведется к нахождению времени padения частицы на притягивающий центр.

Будем рассматривать движение частицы к центру как предельный случай движения по очень вытянутому эллипсу, большая получь которую равна $R/2$, и сравним это движение с обращением по круговой орбите радиусом $R$. Воспользовемся третьим законом Кеплера:

$$\frac{T^2}{T^2} = \frac{R^3}{(R/2)^3},$$

где $T_k$ — период движения по круговой орбите, $T_s$ — по эллиптической орбите. Перiod $T_k$ найти легко с помощью второго закона Ньютона и закона всемирного тяготения:

$$\frac{mv^2}{R} = F_T = G \frac{mM}{R^2} = G \frac{mQ \cdot \frac{4}{3} \pi R^3}{R^2},$$

откуда $T_k = \frac{2\pi R}{v} = \sqrt{\frac{3\pi}{G\rho}}$, и

$$T_s = \frac{T_k}{2^{3/2}} = \sqrt{\frac{3\pi}{8G\rho}}.$$

Мы получили, что период $T_s$ не зависит от $R$. Следовательно, и время padения частицы на притягивающий центр (время обращения звезды), равное половине перiodа обращения по эллиптической орбите, не зависит от радиуса obлака космической пыли и равно

$$\tau = \frac{T_s}{2} = \sqrt{\frac{3\pi}{32G\rho}} \approx 1,5 \cdot 10^{13} \text{ c} \approx 10^6 \text{ лет.}$$

В. Е. Скороваров

Самопересечения замкнутой ломаной

В этой заметке мы приведем решение задачи M1064 и обсуждим некоторые ближе задачи.

M1064. Какое максимальное количество точки самопересечения может иметь замкнутая n-звенная плоская ломана, если a) n нечетно: 6) n четно? (Предполагается, что никакие три вершины не лежат на одной прямой и что никакие три звена не пересекаются в одной точке.)

Ответ: a) $n(n-3)/2$; b) $n(n-4)/2+1$.

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

Ясно, что два звена ломаной пересекаются не более чем в одной точке и что смежные звены не пересекаются (т. е. не имеют общих точек, кроме общей вершины). Всего замкнутая n-звенная ломана имеет $n(n-1)/2$ пар звенев, в том числе n пар смежных звенев. Таким образом, число замкнутой ломаной с таким числом самопересечений существует: достаточно в правильном n-угольнике проведены все n диагоналей, наименее удалены от центра (см. рисунок 1 для n=5 и n=7). Эти звены составляют замкнутую n-звенную ломаную, все не-

31

смежные звенья которой пересекаются (в разных точках). Задча а) решена.
Пусть теперь $n$ четно. Занутерум вершины данной $n$-звенной ломаной подряд, начиная с любой, и обозначим через $A$ множество вершин с четыыми номерами и через $B$ множество вершин с четыыми номерами. Любое звено ломаной идет из некоторой точки множества $A$ в некоторую точку множества $B$. Пусть $l$ — прямая, содержащая некоторое звено. Если это звено пересекает все несмежные с ним звены, то все вершины с четыыми номерами лежат по одному сторону от $l$ (мы не принимаем, конечно, во внимание вершин рассматриваемого звена, которые лежат на $l$). Значит, множество $A$ и $B$ лежат по разные стороны от прямой $l$ и при этом имеет с ней по одной общей точке. Таких прямых существует не более двух. Этот факт представляется мне оченьным, но для любителей строящих рассудений я приведу его доказательство (см. рис. 2).

Пусть есть три такие прямые. Точнее, пусть $A_1, A_2, A_3 \in A$ и $B_1, B_2, B_3 \in B$ — такие точки, что множество $A$ и $B$ лежат по разные стороны от каждой из прямых $A_1B_1, A_2B_2, A_3B_3$. Так как точки $A_2, B_2$ лежат по разные стороны от прямой $A_1B_1$, а точки $A_1, B_1$ лежат по разные стороны от прямой $A_2B_2$, то пересекаются отрезки $A_1B_1$ и $A_2B_2$; пусть $C$ — точка пересечения.

Точка $A_3$ лежит по ту же сторону от прямой $A_1B_1$, что точка $A_2$, и лежит по ту же сторону от прямой $A_2B_2$, что точка $A_1$; значит, она содержится в угле $A_1CA_2$. По аналогичным принципам точки $B_3$ лежит в угле $B_1CB_2$. Значит, пряма $A_3B_3$ не пересекает хотя бы один из отрезков $CA_1, CA_2$ и не пересекает хотя бы один из отрезков $CB_1, CB_2$. Пусть она не пересекает $CA_i$ и $CB_j$ (на рисунке это $CA_2$ и $CB_1$); тогда точки $A_i$ и $B_j$ лежат от нее по одному сторону, что противоречит предположению.

Итак, имеется не более двух звенев, которые пересекаются все несмежные с ними звены. Значит, по крайней мере $n-2$ звеня не пересекают хотя бы один из несмежных с ними звенев; следовательно, имеется по крайней мере $(n-2)/2$ пар непересекающихся несмежных звенев и общее число точек самопересечения не превыходит $n/(n-3) - \frac{n-2}{2} = \frac{n(n-4)}{2} + 1$.

Остается при любом момент $n$-звенную ломаню с $n/(n-4)/2+1$ самопересечениями.

Проведем в правильном $n$-угольнике все диагонали, близкие к его центру, но не проходящие через центр. (Причем $n/2$ они образуют замкнутую ломаню, при нечетном $n/2$ — две замкнутые ломаные, симметричные друг друга относительно центра.) Каждый из этих диагоналов все несмежные с ней диагонали, кроме один — параллельной ei; это дает $n/(n-4)/2$ пересечений. Сотрем две параллельные диагонали, а их концы соединим крест-накрест. (См. рисунок 3 для $n=6$ и $n=12$. Тонкие сплошные линии — это ближешие к центру не проходящие через центр диагонали правильного $n$-угольника. Пунктирные линии — выбрасывемые диагонали. Жирные сплошные линии — диагонали, которые они заменяют. Сплошные точки и жирные линии составляют нашу ломаню.) Число пересечений увеличится на 1, причем, как легко проверить, $n$ проведенных отрезков образуют замкнутую ломаную. Задча 6) решена.

Приведем еще несколько задач, по форме похожих на разобранную задачу. Прежде всего, можно рассмотреть класс рассматриваемых ломаных, разрешив ломаной распадаться на несколько замкнутых ломаных. Чтобы придать задание естественного форму, мы сформулируем ее так. На плоскости фиксированных $n$ точки, никакие три из которых не лежат на одной прямой. Некоторые из этих точки соединены отрезками, причем каждая точка соединенаровно с двумя другими. Каково наиболее возможное число (Окончание см. на с. 34)

34

Программы перебора
(Начало см. на с. 7)

квадрат к ранее подсчитанному числу частливых билетников для меньших значений S. Это осуществляется в строке 100. Наконец, когда цикл по S (от 0 до 13) завершен, нужно удвоить полученное число P и вычесть 1.

Задание
23. Сколько слагаемых суммы 1+2+3+… надо взять, чтобы получилось трехзначное число, состоящее из одинаковых цифр?
24. Сколько есть целых чисел от 1 до 1988, которые не делятся ни на одно из чисел 6, 10, 15?
25. Найдиите наименьшее натуральное число M, обладающее тем свойством, что сумма

квадратов одинапчатыми последовательными натуральными чисел, начиная с M, является точным квадратом.

26. Сколько способами можно разметить рублей медными монетами (достоинством 1, 2, 3, 5 копеек)?

27. В последовательности 19886138… каждая цифра, начиная с пятой, равна последней цифре суммы четных предыдущих цифр. Через сколько цифр снова встречается начальная комбинация 1988 (инчете говоря, сколько цифр в периоде)?

28. Пусть X — сумма кубов десяти последовательных натуральных чисел, а Y — сумма этих же натуральных чисел. Докажите, что X² — Y² делится на 300.

29. Определите a) наименьшее значение отношения трехзначного числа к сумме его цифр. Для каких чисел это наименьшее (наименьшее) значение достигается?

30. Найдите четырехзначное число, в четыре раза меньше числа, записанного теми же цифрами, но в обратном порядке.