Пусть l₁, l₂, ..., l_n — несколько прямых на плоскости, не все из которых параллельны. Докажите, что можно единственным образом выбрать на каждой из этих прямых по точке X₁, X₂, ..., X_n так, чтобы перпендикуляр, восставленный к прямой l_k в точке X_k (для любого натурального k < n), проходил через точку X_{k + 1}, а перпендикуляр, восставленный к прямой l_n в точке X_n, проходил через точку X₁.

Попробуйте сформулировать и доказать аналогичную теорему в пространстве.

   Решение

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

   Решение

(Число разбиений; предлагалась на Всесоюзной олимпиаде по программированию 1988 года) Пусть P(n) — число разбиений целого положительного n на целые положительные слагаемые (без учёта порядка, 1 + 2 и 2 + 1 — одно и то же разбиение). При n = 0 положим P(n) = 1 (единственное разбиение не содержит слагаемых). Построить алгоритм вычисления P(n) для заданного n.

   Решение

Страница: << 1 2 3 4 5 >> [Всего задач: 23]      

Перечислить все последовательности длины 2n, составленные из n единиц и n минус единиц, у которых сумма любого начального отрезка неотрицательна, --е число минус единиц в нём не превосходит числа единиц. (Число таких последовательностей называют числом Каталана)

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

Решение

(Число разбиений; предлагалась на Всесоюзной олимпиаде по программированию 1988 года) Пусть P(n) — число разбиений целого положительного n на целые положительные слагаемые (без учёта порядка, 1 + 2 и 2 + 1 — одно и то же разбиение). При n = 0 положим P(n) = 1 (единственное разбиение не содержит слагаемых). Построить алгоритм вычисления P(n) для заданного n.

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

Решение

В предложенном в предыдущей задаче алгоритме используется сравнение двух массивов (x <> last). Устранить его, добавив булевскую переменную l и включив в инвариант соотношение последовательность x - последняя.

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

Решение

Перечислить все возрастающие последовательности длины k из чисел 1..n в лексикографическом порядке. (Пример: при n=5, k=2 получаем: 12 13 14 15 23 24 25 34 35 45.)

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

Решение

Представляя по-прежнему разбиения как невозрастающие последовательности, перечислить их в порядке, обратном лексикографическому (для n=4, например, должно быть 4, 3+1, 2+2, 2+1+1, 1+1+1+1).

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

Решение

Страница: << 1 2 3 4 5 >> [Всего задач: 23]