Версия для печати
Убрать все задачи

---

Окружности ω₁ и ω₂ касаются внешним образом в точке P. Через центр ω₁ проведена прямая l₁, касающаяся ω₂. Аналогично прямая l₂ касается ω₁ и проходит через центр ω₂. Оказалось, что прямые l₁ и l₂ непараллельны. Докажите, что точка P лежит на биссектрисе одного из углов, образованных l₁ и l₂.

   Решение

---

Докажите, что геометрическая прогрессия {a_n} = bx₀ⁿ удовлетворяет соотношению (11.2 ) тогда и только тогда, когда x₀ -- корень характеристического уравнения (11.3 ) последовательности {a_n}.

   Решение

---

На плоскости даны две точки A и B. Пусть C – некоторая точка плоскости, равноудалённая от точек A и B. Построим последовательность точек
C₁ = C, C₂, C₃, ...,  где C_n+1 – центр описанной окружности треугольника ABC_n. При каком положении точки C
  а) точка C_n попадёт в середину отрезка AB (при этом C_n+1 и дальнейшие члены последовательности не определены)?
  б) точка C_n совпадает с C?

   Решение

---

Даны выпуклый n-угольник с попарно непараллельными сторонами и точка O внутри его. Докажите, что через точку O нельзя провести более n прямых, каждая из которых делит площадь n-угольника пополам.

   Решение

---

В прямоугольную таблицу из m строк и n столбцов записаны mn положительных чисел. Найдём в каждом столбце произведение чисел и сложим все n таких произведений. Докажите, что если переставить числа в каждой строке в порядке возрастания, то сумма аналогичных произведений будет не меньше, чем в первоначальной. Решите эту задачу для
  а)  m = n = 2;
  б)  m = 2  и произвольного n;
  в) любых натуральных m и n.

   Решение

---

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

   Решение

---

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

   Решение

---

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

   Решение

---

Дано n точек,  n > 4.  Докажите, что можно соединить их стрелками так, чтобы из каждой точки в любую другую можно было попасть, пройдя либо по одной стрелке, либо по двум (каждые две точки можно соединить стрелкой только в одном направлении; идти по стрелке можно только в указанном на ней направлении).

   Решение

---

а) Докажите, что площадь четырехугольника, образованного серединами сторон выпуклого четырехугольника ABCD, равна половине площади ABCD.
б) Докажите, что если диагонали выпуклого четырехугольника равны, то его площадь равна произведению длин отрезков, соединяющих середины противоположных сторон.

   Решение

---

Точки A₁, B₁ и C₁ симметричны центру описанной окружности треугольника ABC относительно его сторон.
Докажите, что треугольники ABC и A₁B₁C₁ равны.

   Решение

---

В окружности радиуса 1 проведено несколько хорд. Докажите, что если каждый диаметр пересекает не более k хорд, то сумма длин хорд меньше k.

   Решение

---

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

   Решение

---

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

б) На рисунке справа девять точек лежат по три на девяти прямых, причём через каждую точку проходит по три таких прямых. Эти девять точек и девять прямых образуют знаменитую конфигурацию Паскаля. Сколькими способами можно множество наших девяти точек отобразить на себя так, чтобы каждая тройка точек, лежащая на одной из девяти наших прямых, отобразилась на тройку точек, которая тоже лежит на некоторой прямой из нашей конфигурации?

в) Тот же вопрос для конфигурации Дезарга (из десяти точек и десяти прямых), изображённой на нижнем рисунке.

   Решение

---

Решите в натуральных числах уравнение  n^x + n^y = n^z.

   Решение

---

По заданному ненулевому x значение x⁸ можно найти за три арифметических действия: x² = x · x, x⁴ = x² · x², x⁸ = x⁴ · x⁴, а x¹⁵ — за пять действий: первые три — те же самые, затем x⁸ · x⁸ = x¹⁶ и x¹⁶ : x = x¹⁶. Докажите, что

а) x¹⁶ можно найти за 12 действий (умножений и делений);

б) для любого натурального n возвести x в n-ю степень можно не более чем за 1 + 1,5 · log₂n действий.

   Решение

Темы:    [ Теория алгоритмов (прочее) ] [ Двоичная система счисления ] [ Показательные неравенства ] [ Логарифмические неравенства ]

Сложность: 6+ Классы: 9,10,11

Прислать комментарий

Условие

По заданному ненулевому x значение x⁸ можно найти за три арифметических действия: x² = x · x, x⁴ = x² · x², x⁸ = x⁴ · x⁴, а x¹⁵ — за пять действий: первые три — те же самые, затем x⁸ · x⁸ = x¹⁶ и x¹⁶ : x = x¹⁶. Докажите, что

а) x¹⁶ можно найти за 12 действий (умножений и делений);

б) для любого натурального n возвести x в n-ю степень можно не более чем за 1 + 1,5 · log₂n действий.

Решение

Заметим сначала, что степени x с показателями 2 , 4 , 8 , ... , 2^k можно вычислить за k умножений, именно: x²=x · x , x⁴=x² · x² , ... , x2^k=x2^k-1 · x2^k-1 . Отсюда следует, что xⁿ= x2^{log _{_}2 n} нельзя найти быстрее чем за l=[log _{_}2 n] операций (через [z] обозначена целая часть действительного числа z , т.е. такое целое число m , что m z<m+1 ).

а) Так как 2⁹=512<1000<1024=210 , т.е. [log _{_}2 1000]=9 , то x1000 нельзя вычислить быстрее чем за 9 действий. С другой стороны, x1000= x1024:(x16 · x⁸) , на что потребуется 11 умножений и 1 деление. Можно доказать, что этот способ вычисления самый экономный.

Замечание. В "Кванте" #11 за 1973 год была опубликована задача из книжки Е.А.Морозовой и И.С.Петракова, Международные математические олимпиады:

Дан ящик сахарного песка, чашечные весы и гирька в 1 г. Как возможно быстрее отвесить покупателю 1 кг сахару? (Указать схему уравновешиваний.)

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

б) Опишем теперь способ вычисления xⁿ . Он основывается на двоичном представлении n ₂ числа n .

Представим n в виде суммы

n=ε_l · 2^l+ε_l-1 · 2^l-1+...+ ε₁ · 2+ε₀,
где ε_j – либо 0 , либо 1 , 0 j l-1 , а ε_l=1 . Тогда двоичное представление n имеет вид:
n ₂=ε_l ε_l-1 ... ε₁ ε₀ (*)

Обозначим через E(n) число единиц среди цифр ε_j :

1 ε_l+ε_l-1+...+ε₁+ε₀= E(n) l+1,
а через H(n) – число нулей, так что H(n)=l+1-E(n) . Для нахождения xⁿ вычисляем сначала многочлены x² , x⁴ , ... , x2^l (за l умножений). Дальнейшие вычисления зависят от величины E(n) .

(1) Если 1 E(n) , то перемножим те многочлены x2^j , для которых ε_j=1 (для этого нам потребуется E(n)-1 умножений); ввиду равенства (*) , результат ранен xⁿ , общее же число умножении равно l+E(n)-1 .

Но

l+E(n)-1 l+< log _{_}2 n+1.

(2) Если <E(n) l+1 , то

H(n) .
Рассмотрим число =2^l+1-n . Очевидно, что n ₂+ ₂=10 ... 0 ( l+1 нуль) и что поэтому E () H(n)+1 . Как и в случае (1), вычислим многочлен x за l+E()-1 умножений. Затем вычислим многочлен x2^l+1 (так как многочлен x2^l уже найден, то на это потребуется еще одно умножение) и, наконец, многочлен xⁿ=x2^l+1: x (одно деление). Итак, в этом случае потребовалось l+ E () умножений и одно деление, т.е. всего l+E () +1 действий, где
l+E ()+1 l+H(n)+2 l+1 log _{_}2 n+1.

Замечание. Многочлен x1000 был вычислен нами способом(2). Однако существуют многочлены, для которых ни способ(1), ни способ(2) не являются наилучшими. Например, многочлен x170 может быть вычислен за 9 умножений (найдите такой способ сами!), хотя 170 ₂=10,101,010 , так что E(170)=H(170)=4 , [log _{_}2 170]=7 ; при способе(1) нужно 10 умножений, а при способе(2)– 11 умножений и одно деление.

Источники и прецеденты использования