M1722. Количество целых точек

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

Условие

Пусть [latex]a,b[/latex] — натуральные числа. Проведем через точку [latex](a;b)[/latex] прямую, отсекающую от первого координатного угла треугольник.
а) Докажите, что количество точек с целыми неотрицательными координатами, которые лежат внутри или на сторонах этого треугольника, больше, чем [latex]2 \cdot a \cdot b + a + b[/latex].
б) Докажите, что эта оценка точная: через точку [latex](a;b)[/latex] можно провести прямую, отсекающую от первого координатного угла треугольник, внутри и на сторонах которого всего [latex]2 \cdot a \cdot b + a + b[/latex] точек с целыми неотрицательными координатами.

Решение

Рассмотрим прямоугольник [latex]OABC[/latex] с центром в точке [latex]P(a;b)[/latex], и сторонами, параллельными осям координат(рис.1). Внутри и на сторонах этого прямоугольника всего [latex](2 \cdot a + 1) \cdot (2 \cdot b+1) = [/latex] [latex] 4\cdot a \cdot b + 2\cdot a + 2 \cdot b +1[/latex] целочисленных точек.

Pис.1

Чуть-чуть сдвинем точку [latex]A[/latex] вправо. Через полученную точку [latex]A'[/latex] и точку [latex]P[/latex] проведем прямую до пересечения с осью ординат в точке [latex]C'[/latex]. Если сдвиг был достаточно мал, то в треугольнике [latex]OA’C'[/latex] не появится ни одной точки с целыми координатами, которой не было бы в треугольнике [latex]OAC[/latex].
При центральной симметрии относительно [latex]P[/latex] любая целочисленная точка прямоугольника [latex]OABC[/latex] переходит в целочисленную точку этого же прямоугольника. Поэтому все отличные от [latex]P[/latex] целочисленные точки прямоугольника разбиваются на пары точек, симметричных относительно [latex]P[/latex].
Итак, если [latex]A'[/latex] достаточно близка к точке [latex]A[/latex], то внутри и на границе треугольника [latex]OA’C'[/latex] расположена ровно половина отличных от [latex]P[/latex] целочисленных точек, т.е. [latex]2 \cdot a \cdot b + a + b[/latex] точек. Вместе с точкой [latex]P[/latex] получаем всего [latex]2 \cdot a \cdot b + a + b + 1[/latex] точек. Мы решили пункт б).

Теперь займемся пунктом а). Для определенности, пусть прямая отсекает от первого координатного угла треугольник [latex]OA_1C_1[/latex], где точка [latex]A_1[/latex] расположена правее точки [latex]A[/latex](рис.2).

Рис.2

Чтобы получить треугольник [latex]OA_1C_1[/latex] из треугольника [latex]OAC[/latex], достаточно «отрезать» от последнего треугольник [latex]CC_{1}P[/latex] и добавить треугольник [latex]AA_{1}P[/latex].
Но при центральной симметрии относительно точки [latex]P[/latex] треугольник [latex]CC_{1}P[/latex] переходит в треугольник, являющийся частью треугольника [latex]AA_{1}P[/latex](закрашенный на рисунке 2). Целочисленные координаты при этом переходят в целочисленные. Задача решена.

М1473. О записи степеней двойки

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

Пусть [latex]c_{n}[/latex] — первая цифра числа [latex]2^{n}[/latex] (в десятичной записи).

Сколько единиц среди первых 1000 членов этой последовательности?
Докажите, что в последовательности
$$ c_{1}=2, \quad c_{2}=4, \quad c_{3}=8, \quad c_{4}=1, \quad c_{5}=3, \quad… $$

встретится ровно 57 различных «слов» [latex]c_{k}c_{k+1}…c_{k+12}[/latex] длины 13.

Решение

Отметим на «логарифмической шкале» [latex]y=\log_{10}{x} [/latex] числа [latex]x=2^{n}[/latex] (каждая следующая отметка получается из предыдущей сдвигом на расстояние [latex]\log_{10}{2}[/latex]). Число [latex]x[/latex] начинается с [latex]1[/latex], если [latex]10^{k} \le x < 2 \cdot 10^{k+1}[/latex] для некоторого [latex]k[/latex]; соответствующие интервалы на рисунке 1 выделены красным (поскольку длина интервала как раз равна [latex]\log_{10}{2}[/latex], на каждый из них попадает ровно одна отметка). Поскольку

$$ \log_{10}{2} = 0.30103…, \quad 10^{301} \le 2^{1000} < 10^{302}, $$

так что [latex]2^{n}(n=0,1,2,…,1000)[/latex] ровно 301 раз перейдет через степень [latex]10[/latex] и поэтому (не считая [latex]2^{0}=1[/latex]) 301-ый её член начинается с 1.

Чтобы более детально разобраться в закономерностях последовательности [latex]c_{n}[/latex], свернем логарифмическую шкалу [latex]y=\log{10}{x} [/latex] в «логарифмический круг» [latex]z=y-\left[ y \right][/latex]: каждый отрезок от [latex]10^k[/latex] до [latex]10^{k+1}[/latex] даёт новый оборот круга, а точки [latex]0=\log_{10}{1}, \quad \log_{10}{2}, \quad \log_{10}{3}, \quad …, \quad \log_{10}{9}[/latex] — границы интервалов, в которых расположены значения z, соответствующие различным первым значащим цифрам числа [latex]x[/latex] от [latex]1[/latex] до [latex]9[/latex] (см. рисунок 2).

Прежде чем решать задачу [latex](2)[/latex], объясним идею рассуждения на более простом примере: выясним, сколько разных пар [latex]\left( c_{k}, c_{k+1} \right)[/latex] цифр встречается в нашей последовательности. Читать далее «М1473. О записи степеней двойки»

M1568. Сечение пирамиды

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

Условие

Докажите что при [latex]n\ge 5[/latex] сечение пирамиды, в основании которой лежит правильный n-угольник, не может являться правильным (n+1)-угольником.

Решение

Пусть правильный (n+1) –угольник [latex]{ B }_{ 1 }…{ B }_{ n }[/latex] является сечением пирамиды [latex]S{ A }_{ 1 }…{ A }_{ n }[/latex] где [latex]{ A }_{ 1 }…{ A }_{ n }[/latex] – правильный n-угольник. Мы рассмотрим три случая: [latex]n=5 , n=2k-1 (k>3)[/latex] и [latex]n=2k (k>2)[/latex]
Так как n-угольная пирамида имеет [latex](n+1)[/latex] грань, то стороны сечения находятся по одной в каждой грани пирамиды. Поэтому без ограничения общности рассуждений можно считать, что точки [latex]{ B }_{ 1 }…{ B }_{ n+1 }[/latex] расположены на ребрах пирамиды так, как показано на рисунках 1 и 2 ( в соответствии с указанными случаями).

[latex] n=5 [/latex]. Так как в правильном шестиугольнике [latex]{ B }_{ 1 }…{ B }_{ 6 }[/latex] прямые [latex]{ B }_{ 2 }{ B }_{ 3 }, { B }_{ 5 }{ B }_{ 6 }[/latex] и [latex]{ B }_{ 1 }{ B }_{ 4 }[/latex] параллельны, а плоскости [latex]{ A }_{ 2 }S{ A }_{ 3 }[/latex] и [latex]ASA [/latex] проходят через [latex]{ B }_{ 2 }{ B }_{ 3 }[/latex] и [latex]{ B }_{ 5 }{ B }_{ 6 }[/latex] то их линия пересечения [latex]{ ST ( T= { A }_{ 1 }{ A }_{ 5 } }\bigcap { A } _{ 2 }{ A }_{ 3 } )[/latex] параллельна этим прямым т.е. [latex]ST\parallel { B }_{ 1 }{ B }_{ 4 }[/latex] Проведем через прямые [latex]ST[/latex] и [latex]{ B }_{ 1 }{ B }_{ 4 }[/latex] плоскость. Эта плоскость пересечет плоскость основания пирамиды по прямой [latex]{ B }_{ 1 }{ A }_{ 4 }[/latex] которая должна проходить через точку пересечения прямой [latex]ST[/latex] с плоскостью основания т.е. через точку [latex]T[/latex]. Итак, прямые [latex]{ A }_{ 1 }{ A }_{ 5 }, { A }_{ 4 }{ B }_{ 1 }[/latex] и [latex]{ A }_{ 2 }{ A }_{ 3 }[/latex] пересекаются в одной точке.Аналогично доказывается, что прямые [latex]{ A }_{ 1 }{ A }_{ 2 }, { A }_{ 3 }{ B }_{ 6 }[/latex] и [latex]{ A }_{ 4 }{ A }_{ 5 }[/latex] и пересекаются в одной точке. Из этого следует что [latex]{ A }_{ 4 }{ B }_{ 1 }[/latex] и [latex]{ A }_{ 3 }{ B }_{ 6 }[/latex] – оси симметрии правильного пятиугольника [latex]{ A }_{ 1 }…{ A }_{ 5 }[/latex] , значит. Точка O их пересечения – центр этого пятиугольника. Заметим теперь, что если [latex]Q[/latex] – центр правильного шестиугольника [latex]{ B }_{ 1 }…{ B }_{ 6 }[/latex] , то плоскости [latex] S{ A }_{ 3 }{ B }_{ 6 }, S{ A }_{ 4 }{ B }_{ 1 }[/latex] и [latex]S{ B }_{ 2 }{ B }_{ 5 }[/latex] пересекаются по прямой [latex]SQ[/latex]. Следовательно прямые [latex]{ A }_{ 3 }{ B }_{ 6 },{ A }_{ 4 }{ B }_{ 1 }[/latex] и [latex]{ A }_{ 2 }{ A }_{ 5 }[/latex] должны пересекаться в одной точке – точке пересечения прямой [latex]SQ[/latex] с плоскостью основания пирамиды.Значит диагональ правильного пятиугольника [latex]{ A }_{ 1 }…{ A }_{ 5 }[/latex] должна проходить через его центр [latex]O[/latex], что невозможно.

[latex] n=2k-1 (k>3) [/latex] Аналогично первому случаю показывается, что так как в правильном [latex]2k[/latex]-угольнике [latex] { B }_{ 1 }…{ B }_{ 2k }[/latex] прямые [latex] { B }_{ 1 }{ B }_{ 2 },{ B }_{ k+1 }{ B }_{ k+2 }[/latex] и [latex]{ B }_{ k }{ B }_{ k+3 }[/latex]параллельны, то прямые [latex] { A }_{ 1 }{ A }_{ 2 },{ A }_{ k+1 }{ A }_{ k+2 }[/latex] и [latex]{ A }_{ k }{ A }_{ k+3 }[/latex] должны пересекаться в одной точке, что невозможно, так как в правильном [latex](2k-1)[/latex]-угольнике [latex]{ A }_{ 1 }…{ A }_{ 2k-1 }[/latex] имеем [latex]{ A }_{ k+1 }{ A }_{ k+2 }\parallel { A }_{ k }{ A }_{ k+3 }[/latex], а прямые [latex]{ A }_{ 1 }{ A }_{ 2 },{ A }_{ k+1 }{ A }_{ k+2 }[/latex] не параллельны.
[latex]n=2k (k>2) [/latex] Аналогично предыдущему случаю прямые [latex] { A }_{ 1 }{ A }_{ 2 },{ A }_{ k+1 }{ A }_{ k+2 }[/latex] и [latex]{ A }_{ k }{ A }_{ k+3 }[/latex] параллельны, следовательно, прямые [latex] { B }_{ 1 }{ B }_{ 2 },{ B }_{ k+1 }{ B }_{ k+2 }[/latex] и [latex]{ B }_{ k }{ B }_{ k+3 }[/latex] должны пересекаться в одной точке, что невозможно, так как [latex]{ B }_{ k+1 }{ B }_{ k+2 }\parallel { B }_{ k }{ B }_{ k+3 }[/latex], а прямые [latex]{ A }_{ 1 }{ A }_{ 2 }, { A }_{ k+1 }{ A }_{ k+2 }[/latex] не параллельны.

Замечания

При [latex]n=3,4[/latex] утверждение задачи неверно. Примерами могут служить правильный тетраэдр имеющий сечением квадрат и правильная четырехугольная пирамида, все боковые грани которой являются правильными треугольниками, которая имеет сечением правильный пятиугольник
Приведенное решение можно было бы изложить короче, если воспользоваться центральным проектированием и его свойством утверждающим, что при центральном проектировании образами прямых, проходящих через одну точку, являются прямые, проходящие через одну точку ( или параллельные). Достаточно спроектировать сечение пирамиды на плоскость из вершины пирамиды.

Д. Терешин.

M1571. О доске, монете и возможных передвижениях

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

Условие

Дана прямоугольная доска [latex]ABCD[/latex] со сторонами [latex]AB=20[/latex] и [latex]BC=12[/latex], разбитая на [latex]20\times12[/latex] единичных квадратов. Пусть [latex]r[/latex] — данное положительное целое число. За один ход монету можно передвинуть из одного единичного квадрата в другой в том и только том случае, когда расстояние между их центрами равно [latex]\sqrt{r}[/latex]. Требуется найти последовательность ходов, переводящую монету из единичного квадрата с вершиной [latex]A[/latex] в единичный квадрат с вершиной [latex]B[/latex].

Докажите, что это невозможно, когда [latex]r[/latex] делится на [latex]2[/latex] или на [latex]3[/latex].
Докажите, что это можно сделать при [latex]r=73[/latex].
Можно ли это сделать при [latex]r=97[/latex]?

Решение

Введем прямоугольную систему координат с началом в точке [latex]A[/latex] и направим оси [latex]Ax[/latex] и [latex]Ay[/latex] вдоль отрезков [latex]AB[/latex] и [latex]AD[/latex] соответственно. Единица длины будет равна стороне единичного квадрата. Нам необходимо найти путь из точки [latex](0;0)[/latex] в точку [latex](19;0)[/latex] такой, что для каждого хода [latex](x;y)\rightarrow(x+a,y+b)[/latex] выполняется равенство [latex]a^2+b^2=r^2[/latex].

Задание №1

Если [latex]r[/latex] чётно, то для каждого целого решения уравнения [latex]a^2+b^2=r^2[/latex] сумма [latex]a+b[/latex] чётна. Для каждой точки [latex](x;y)[/latex], в которую можно попасть из [latex](0;0)[/latex], [latex]x+y[/latex] чётно. Следовательно, в точку [latex](19;0)[/latex] попасть невозможно.

Задание №2

Один из примеров продвижения монеты из [latex](0;0)[/latex] в [latex](19;0)[/latex] при [latex]r=73[/latex] такой: [latex](0;0)\rightarrow(3;8)\rightarrow(11;5)\rightarrow(19;2)\rightarrow(16;10)\rightarrow(8;7)\rightarrow(0;4)\rightarrow(8;1)\rightarrow(11;9)\rightarrow(3;6)\rightarrow(11;3)\rightarrow(19;0)[/latex]

Задание №3

Пусть [latex]R=\left\{(i;j);0\leq{i}\leq19,0\leq{j}\leq19\right\}[/latex], [latex]P=\left\{(i;j);0\leq{i}\leq49,4\leq{j}\leq7\right\}[/latex], [latex]Q[/latex] — их разность: [latex]Q=R\setminus{P}[/latex]. Так как число [latex]97[/latex] представимо в виде суммы квадратом единственным образом: [latex]9^2+4^2[/latex], то каждый ход состоит из одного из векторов [latex](\pm4;\pm9)[/latex], [latex](\pm9;\pm4)[/latex]. Ход типа [latex](\pm9;\pm4)[/latex] приводит нас в точку [latex]Q[/latex] из точки из множества [latex]P[/latex] и наоборот, тогда как ход [latex](\pm4;\pm9)[/latex] не выводит нас из множества [latex]Q[/latex] (заметим, что за один шаг нашими ходами нельзя попасть из точки из [latex]P[/latex] в точку из [latex]P[/latex]). Каждый ход типа [latex](\pm9;\pm4)[/latex] изменяет чётность [latex]x[/latex]-координаты, поэтому, чтобы попасть из [latex](0;0)[/latex] в [latex](19;0)[/latex], требуется нечётное число таких ходов. Каждый такой ход от точки из [latex]P[/latex] в точку из [latex]Q[/latex] и наоборот. Значит после нечётного числа ходов из точки [latex](0;0)\in{Q}[/latex] попадаем в точку из [latex]P[/latex], но [latex](19;0)\in{Q}[/latex]. Поэтому требуемое невозможно.

Д. Терешин

М1570. Выпуклый многогранник с шестью вершинами

Задачи из журнала «Квант» (1996 год, выпуск 5)

Условие:

Три пары диаметрально противоположных точек сферы — вершины выпуклого многогранника с шестью вершинами. Один из его двугранных углов — прямой. Доказать, что у него ровно 6 прямых двугранных углов.

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

Противоположные грани нашего многогранника симметричны относительно центра сферы О и потому параллельны. Все эти грани — треугольники (поскольку многогранник — выпуклая оболочка трех пар диаметрально противоположных точек сферы). Пусть [latex]AB[/latex] — ребро прямого двугранного угла, образуемого плоскостями граней [latex]ABC[/latex] и [latex]ABC'[/latex]. Эти две плоскости, а также параллельные им плоскости [latex]A’B’C'[/latex] и [latex]A’B’C[/latex], пересекают сферу по окружностям. Эти четыре окружности пересекаются в восьми точках — вершинах прямоугольного треугольного параллелепипеда(рис. 2). Точки [latex]C[/latex] и [latex]C'[/latex] должны (так же как и [latex]A[/latex] и [latex] A'[/latex] [latex]B[/latex] и [latex] B'[/latex]) лежать в некоторых двух противоположных вершинах этого параллелепипеда. Соответственно (быть может, поменяв обозначения точек [latex]A[/latex] и [latex]B[/latex]), мы получаем единственный возможный пример — октаэдр [latex]ABCA’B’C'[/latex], вершины которого — это шесть вершин прямоугольного треугольного параллелепипеда [latex]ABCDD’C’A’B'[/latex](рис. 1). У этого октаэдра, очевидно, ровно шесть прямых двугранных углов — при ребрах [latex]AB[/latex], [latex]BC[/latex], [latex]CA'[/latex], [latex]A’B'[/latex], [latex]B’C'[/latex], [latex]C’A[/latex] (и шесть — тупых).