M390. Сумма цифр числа

Задача из журнала «Квант» (1976, №6)

Условие

Докажите что существует бесконечно много натуральных ${n}$, для которых сумма цифр числа ${2}^{n}$ больше суммы цифр числа ${2}^{n+1}.$

Решение

Рис.1

Решение этой задачи основано на двух фактах.

I Остатки чисел $ 1,\quad 2,\quad { 2 }^{ 2 },\quad { 2 }^{ 3 }…$ при делении на 9 образуют периодическую последовательность, изображенную на рисунке 1.

II Количество цифр в числе ${2}^{n}$ не превосходит

$$\lg{{ 2 }^{ n }}+1=n\cdot \lg{2}+1\le \frac { n }{ 3 } +1.$$

Покажем, что эти два факта находятся в противоречии с предположением:

III $$s({ 2 }^{ n })\le s({ 2 }^{ n+1 })$$

для всех ${n}$, не меньших некоторого ${N}$, где ${s(a)}$ — сумма цифр числа ${a}.$

Отсюда будет следовать, что III неверно, а это и требуется доказать в задаче.

Допустим, что III верно, то есть что для всех ${n\ge N}$ сумма цифр ${2}^{n}$ все время возрастает. Тогда согласно I для ${n\ge N}$ при переходе от ${2}^{n}$ до ${2}^{n+6}$ (за один период) сумма цифр увеличивается не меньше, чем на

$${1+2+4+8+7+5=27}.$$

(Мы рассуждаем так: если ${a}$ дает при делении на ${9}$ остаток ${8}$, ${b}$ — остаток ${7}$ и ${a<b}$, то разность ${b-a}$ не меньше ${8}$; оценки для разностей указаны на рисунке 1 красным цветом). Итак,

$$s({ 2 }^{ n+6 })\le s({ 2 }^{ n })+27.$$

Значит, при ${n=N+6k}$, где ${k\ge 1}$, будет $$s({ 2 }^{ n })=s({ 2 }^{ N+6k })\ge { s(2 }^{ N })+27k=\cfrac { 9 }{ 2 } n-\cfrac { 9 }{ 2 } N+s({ 2 }^{ N }).$$

Поскольку все цифры не больше 9, согласно II

$$s({ 2 }^{ n })\le 9(\frac { n }{ 3 } +1).$$

Таким образом, при всех ${n=N+6k}$ должно выполняться неравенство

$$\frac { 9 }{ 2 } n-A\le s({ 2 }^{ n })\le 3n+9.$$

(здесь $A$ — число, не зависящее от $n$). Но поскольку $\frac { 9 }{ 2 } >3$, это, очевидно, неверно(при всех $n>2(A+9)/3$). Полученное противоречие доказывает, что предположение III неверно.

М838. О разбиении точек, лежащих на сторонах треугольника, на множества

Задача из журнала “Квант” (1984, №3)

Условие

Все точки, лежащие на сторонах правильного треугольника $ABC$ разбиты на два множества $E_{1}$ и $E_{2}$. Верно ли, что для любого такого разбиения в одном из множеств $E_{1}$ и $E_{2}$ найдется тройка вершин прямоугольного треугольника?

рис. 1

Ответ

Верно.

Доказательство

Доказательство проведем от противного. Пусть точки множества $E_{1}$ окрашены синим цветом, множества $E_{2}$ – красным. Предположим, что не существует прямоугольного треугольника с одноцветными вершинами, и рассмотрим правильный шестиугольник, вписанный в треугольник $ABC$ (см. рисунок 1). Каждые две его противоположные вершины должны быть окрашены по-разному — если, например, противоположные вершины $P$ и $Q$ синие, то любая из остальных четырех вершин должна быть красной, так как образует вместе с $P$ и $Q$ прямоугольный треугольник: но тогда любые три из этих красных точек образуют запрещенный одноцветный прямоугольный треугольник.

рис. 2

Ясно, что в таком случае найдутся две соседние разноцветные вершины шестиугольника. Либо эти две вершины, либо противоположные им (тоже разноцветные!) лежат на одной из сторон треугольника. Пусть для определенности на стороне $AB$ лежат синяя вершина $К$ и красная $L$, тогда противоположные им вершины $K’$ и $L’$ будут красной и синей (см. рисунок 3). Но тогда в какой бы цвет ни была окрашена вершина $А$, один из
прямоугольных треугольников $AKL’$ и $ALK’$ будет одноцветным. Противоречие.

рис. 3

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

Н.Б. Васильев, В.Н. Дубровский

Задача о Дроби

Задача M24

Условие:

Докажите, что любую дробь $\dfrac{m}{n}$, где $ 0<\dfrac{m}{n}<1$, можно представить в виде
$\dfrac{m}{n}= \dfrac{1}{{q}_{1}} +\dfrac{1}{{q}_{2}} + \dfrac{1}{{q}_{3}} + . . . +\dfrac{1}{{q}_{r}} $ где
$ 0<{q}_{1}<{q}_{2}<{q}_{3}<. . .<{q}_{r}$ — целые числа и каждое $ {q}_{k} \left ( k=2, 3,r \right ) $ делится на $ {q}_{k-1}$

Решение:

Каждую дробь $\dfrac{m}{n}$ можно, разделив ее числитель и знаменатель на их наибольший общий делитель заменить равной ей несокрaтимой дробью. Например $\dfrac{288}{504}=\dfrac{4*72}{7*72}=\dfrac{4}{7}$. В дальнейшем мы будем рассматривать только такие несократимые дроби.

Докажем утверждение задачи индукцией по $ m $ Для $ m=1 $ оно очевидно: сама дробь $ \dfrac{m}{n} $ уже имеет нужный вид. Теперь докажем, что если утверждение задачи верно для всех дrобей с числителями, меньшими чем $ m $, то оно верно и для дробей с числителем, равным $ m $. Пусть $ \dfrac{m}{n} $ такая дробь $ \left( 1 < m < n \right) $. Разделим $ n $ на $ m $ с остатком; получится частное $ \left( {d}_{0}-1 \right) $ и остаток $ \left( m-k \right) $, то есть

$ n = m \left( {d}_{0} — 1 \right) + \left( m — k \right)= m {d}_{0}-k \left( * \right)$

где $ {d}_{0}>1 $ и $ 0 < k < m$. Перепишем $ \left( * \right) $ так:

$ m {d}_{0}=n + k$, или

$ \dfrac {m}{n} = \dfrac {1}{{d}_{0}} \left( 1+\dfrac {k}{n} \right) \left( ** \right)$.

Поскольку
$ \left( 1 < k < m \right) $ дробь $ \dfrac {k}{n} $ mожно представить в нужном виде:

$\dfrac{k}{n} = \dfrac{1}{{d}_{1}} + \dfrac{1}{{d}_{1}{d}_{2}} + . . . + \dfrac{1}{{d}_{1}{d}_{2}. . .{d}_{r}} \left( *** \right) $,

где
$ {d}_{1} , {d}_{2}, . . .{d}_{r} $- некоторые натуральные числа, большие 1. Из $ \left( *** \right) $ и $ \left( ** \right) $ получаем

$ \dfrac {m}{n} = \dfrac {1}{{d}_{0}} + \dfrac {1}{{d}_{0}{d}_{1}}+\dfrac {1}{{d}_{0}{d}_{1}{d}_{2}}+ . . . + \dfrac {1}{{d}_{0}{d}_{1}{d}_{2}. . . {d}_{r}} $.

Dробь $ \dfrac {m}{n}$ представлена в требуемом виде.

Заметим, что из нашего решения задачи нетрудно извлечь простой aлrоритм- правило, как любую данную дробь представить в внде суммы $ \left( *** \right) $. Продемонстрируем его на одном примере. Пусть нам дана дробь $ \dfrac {5}{7} : $

$ 7 = 2 * 5 — 3; \dfrac {5}{7}= \dfrac {1}{2} \left( 1 + \dfrac {3}{7} \right); $

$ 7 = 3 * 3 — 2; \dfrac {3}{7}= \dfrac {1}{3} \left( 1 + \dfrac {2}{7} \right); $

$ 7 = 4 * 2 — 1; \dfrac {2}{7}= \dfrac {1}{4} \left( 1 + \dfrac {1}{7} \right); $

Итак,

$ \dfrac{5}{7} = \dfrac{1}{2} + \dfrac{1}{2*3} + \dfrac{1}{2*3*4} + \dfrac{1}{2*3*4*7} = \dfrac{1}{2} + \dfrac{1}{6} + \dfrac{1}{24} + \dfrac{1}{168}$.

Конечно же могут найтись несколько представлений дроби в виде $ \left( *** \right) $, например:

$ \dfrac{3}{8} = \dfrac{1}{4} + \dfrac{1}{8} = \dfrac{1}{3} + \dfrac{1}{24}$.

M927. Замена пересекающихся отрезков

Задача из журнала «Квант» (1985, №10)

Условие

На плоскости дано конечное множество точек, никакие три из которых не лежат на одной прямой. Проведено несколько отрезков с концами в данных точках. Эти отрезки разрешается менять: если какие-то два из них, [latex]AC[/latex] и [latex]BD[/latex], пересекаются, их можно стереть и провести

отрезки [latex]AB[/latex] и [latex]CD[/latex]
[latex]AB[/latex] и [latex]BC[/latex].

(Если «новый» отрезок уже проведён, проводить его второй раз не нужно.)
Можно ли после нескольких таких замен (только по правилу 1 или по правилу 2, но не по обоим) вернуться к исходному набору отрезков?

Решение

Докажем, что через конечное число операций «типа 1» — замены пересекающихся [latex]AB[/latex] и [latex]CD[/latex] — мы придём к конфигурации, в которой уже не будет пересекающихся отрезков.

Рассмотрим сумму [latex]s[/latex] длин всех отрезков конфигурации. При каждой операции «типа 1» она уменьшается:
[latex]AB + CD < AC + BD[/latex] (*)
(для треугольников [latex]APB[/latex] и [latex]CPD[/latex], где [latex]P[/latex] — точка пересечения [latex]AC[/latex] и [latex]BD[/latex] — рис. 1, выполнены неравенства [latex]AB < AP + PB[/latex] и [latex]CD < CP + PD[/latex]; сложив их, получим (*)).

С другой стороны, величина [latex]s[/latex] может принимать лишь конечное число различных значений, поскольку существует лишь конечное число различных конфигураций из отрезков с вершинами в данных точках. Поэтому через конечное число шагов мы придём к конфигурации, с которой уже нельзя проделать операцию, уменьшающую [latex]s[/latex].

Это решение даёт очень грубую верхнюю оценку для максимального количества [latex]T_n[/latex] операций, которое может быть проделано с конфигурацией на [latex]n[/latex] точках — можно сказать лишь что оно меньше числа всех конфигураций, то есть [latex]2^{n\cdot(n-1)/2}[/latex], [latex]n\cdot(n-1)/2[/latex] — это число различных отрезков с концами в данных [latex]n[/latex] точках.

Приведём идею другого решения, дающего значительно лучшую оценку. Рассмотрим произвольное разбиение [latex]f[/latex] данных точек на два непустых множества, каждое из которых лежит целиком по одну сторону от некоторой прямой [latex]l[/latex]. Таких прямых для данного разбиения, конечно, бесконечно много, но одну из них всегда можно получить, повернув по часовой стрелке прямую, соединяющую две какие-либо точки [latex]A[/latex] и [latex]B[/latex] на очень маленький угол вокруг середины отрезка [latex]AB[/latex] (рис. 2); эту прямую обозначим [latex]l_i[/latex]. Число прямых [latex]l_i[/latex], и значит, что число рассматриваемых «выпуклых» разбиений не превосходит числа пар точек [latex]n\cdot(n-1)/2[/latex].

Назовём балансом конфигурации суммарное число [latex]b[/latex] пересечений её отрезков со всеми прямыми [latex]l_i[/latex]; ясно, что [latex]0 \le b \le (n\cdot(n-1)/2)^2[/latex]. При операции типа 1 число пересечений любой прямой [latex]l_i[/latex] с отрезками конфигурации не увеличивается, а по крайней мере для одной прямой оно уменьшается на 2. Следовательно, [latex]T_n \le n^2 \cdot (n-1)^2 / 8[/latex]. Интересно было бы получить ещё более точную оценку для [latex]T_n[/latex].
Приведём пример, показывающий, что для операции «типа 2» — замены пересекающихся отрезков [latex]AC[/latex] и [latex]BD[/latex] не имеющих общий конец [latex]AB[/latex] и [latex]BC[/latex] — процесс может «зациклиться» и тем самым продолжаться неограниченно. Расположим 18 точек в вершинах правильного 18-угольника и обозначим через [latex]D(k, l)[/latex] конфигурацию из 36 отрезков, в которой каждая из 18 точек соединена [latex]k[/latex]-й и [latex]l[/latex]-й от неё по счёту.

Чтобы пройти за 54 операции путь [latex]D(4, 8) \to D(5, 9) \to D(6, 7) \to D(4, 8)[/latex] (рис. 3), достаточно каждую из операций, изображенных на рисунке 4, проделать по 18 раз (поворачивая картинку каждый раз на [latex]20^{\circ}[/latex]).

По-видимому, существуют и примеры с существенно меньшим числом точек [latex]n[/latex] и длинной цикла [latex]T[/latex], чем [latex]n = 18[/latex] и [latex]T = 54[/latex].

Н.Б. Васильев, В.Е. Колосов

M1626. О сумме длин отрезков в треугольнике, вписанном в окружность

Задача из журнала «Квант» (выпуск №1, 1998).

Условие

В треугольнике $ABC$ угол $A$ является наименьшим. Точки $B$ и $C$ делят окружность, описанную около этого треугольника, на две дуги. Пусть $U$ — внутренняя точка той дуги с концами $B$ и $C$, которая не содержит точку $A$. Серединные перпендикуляры к отрезкам $AB$ и $AC$ пересекают прямую $AU$ в точках $V$ и $W$ соответственно. Прямые $BV$ и $CW$ пересекаются в точке $T$. Докажите, что $$AU = TB + TC.$$

Решение

Нетрудно доказать, что если $\angle A$ — наименьший из углов $\triangle ABC$, то точка $T$ находится внутри этого треугольника. Пусть прямые $BV$ и $CW$ пересекают окружность, описанную около $\triangle ABC$, вторично в точках $B_1$ и $C_1$ соответственно (рис. 1).

В силу симметрии относительно серединного перпендикуляра к стороне $AB$ имеем $AU = BB_1$. Аналогично, $AU = CC_1$. Следовательно, $BB_1 = CC_1$, а значит, и $TB = TC_1$ ($BCB_{1}C_{1}$ — равнобедренная трапеция). Тогда $TB + TC = TC_1 + TC = CC_1 = AU$, что и требовалось доказать.

Замечания

Если $\angle A = 30 ^ \circ$, а $O$ — центр окружности, описанной около $\triangle ABC$, то $|BT — CT| = OT$.
Если отказаться от требования минимальности угла $A$, то (при условии, что прямые $BV$ и $CW$ действительно пересекаются, а не параллельны) справедливо следующее утверждение: из отрезков $AU$, $TB$ и $TC$ один равен сумме двух других. Например, в ситуации, изображенной на рисунке 2, $TB = AU + TC$.