Задача 1:

Назовем множество эгоцентричным (или э-множеством), если оно содержит свою мощность (число элементов). (Например, 2,3,3,5,8 – э-множества, а 3,5,2,5,8 не являются таковыми). Найти число подмножеств множества 1,2, … ,n, являющихся минимальными э-множествами, т.е. такими эгоцентричными множествами, чьи собственные подмножества – не э-множества. (Пример. 2,3 – минимальное э-множество в отличие от 1,2).

Решение: Обозначим число искомых подмножеств f_n. Выпишем минимальные э-множества при n ≤ 6: 1,2,3,2,4,2,5,2,6,3,4,5,3,4,6,3,5,6. Прямой подсчет показывает: f₁ = f₂ = 1,f₃ = 2,f₄ = 3,f₅ = 5,f₆ = 8. Возникает предположение, что для для любого натурального n f_n + 2 = f_n + 1 + f_n. Убедимся в этом.

Разобьем все мэ-подмножества множества 1,2, … ,n + 2 на два класса: множеств, содержащих число n + 2, и множеств, не содержащих это число. Всякое множество из второго класса является мэ-подмножеством множества 1,2, … ,n + 1, поэтому во втором классе f_n + 1 множеств.

Заметим, что в минимальном э-множестве, содержащем k элементов, не могут присутствовать числа меньше k (из-за минимальности), и так как множество – эгоцентрично, то число k – его элемент. Легко проверить, что верно и обратное: произвольное k-элементное множество с минимальным элементом k будет мэ-множеством.

Возьмем теперь произвольное множество из первого класса (пусть k – число его элементов; ясно, что k > 2), удалим в нем элемент n + 2, а все остальные элементы уменьшим на единицу. Получим k – 1-элементное множество с минимальным элементом k – 1 – это мэ-множество, причем максимальный элемент его не превосходит n. Установлено взаимно однозначное соответствие между множествами из первого класса и мэ-подмножествами множества 1,2, … ,n. Таким образом, первый класс содержит f_n множеств. Соотношение f_n + 2 = f_n + 1 + f_n доказано. Ответ. f_n — n-е число Фибоначчи.

Замечание. Из чисел 1,2, … ,n можно составить k-элементных минимальных э-множеств (к числу k нужно добавить еще k – 1 больших k чисел). Поэтому

В результате решения задачи получено интересное комбинаторное тождество: суммы элементов, стоящих на определенных прямых треугольника Паскаля, равны числам Фибоначчи. Это свойство известно давно: см. Н.Н.Воробьев, Числа Фибоначчи, М.,Наука, 1978 (с.20–21).

Задача 2:

Доказать, что для любого натурального числа n

Решение:

Логарифмированием получим неравенство, равносильное доказываемому:

Для его доказательства достаточно oценить площадь криволинейной трапеции, ограниченной прямыми y = 0, x = 1, x = n + 1 и кривой y = ln(2x – 1), с помощью «входящей» и «выходящей» ступенчатых фигур:

Задача 3:

Пусть x₁,x₂, … ,x_n = 1,2, … ,n. Найти как функцию от n (n > 2) наибольшее значение выражения x₁x₂ + x₂x₃ +  …  + x_n – 1x_n + x_nx₁.

Решение: Можно считать, что числа x₁,x₂, … ,x_n расположены по кругу и S_n – сумма попарных произведений соседних чисел.

Докажем по индукции следующее утверждение: если S_n максимально, то число n стоит между числами n – 1 и n – 2. База индукции (n = 3) очевидна. Индукционный шаг. Пусть утверждение справедливо при n = k. Если число k + 1 вставляется между числами a и b, то сумма попарных произведений изменяется так:  Δ _k = S_k + 1 – S_k = (k + 1)(a + b) – ab. При фиксированном a  Δ _k = (k + 1)a + b(k + 1 – a) тем больше, чем больше b. Аналогично при фиксированном b  Δ _k увеличивается с ростом a. Поэтому  Δ _k ≤ (k + 1)(k + (k – 1)) – k(k – 1) = k² + 2k – 1. По предположению индукции если S_k максимально, то числа k и k – 1 стоят рядом. Если k + 1 вставить между этими числами, то получим максимальное значение  Δ _k = k² + 2k – 1, а заодно и S_k + 1 = S_k +  Δ _k, что и требовалось доказать.

Теперь легко найти S_n. S₂ = 1 • 2 + 2 • 1 = 4. При n > 2

Ответ. .

Задача 4:

Для произвольной квадратной матрица A определим  sin A с помощью степенного ряда:

Существует ли такая 2 × 2 матрица A, что

Решение:

Определив с помощью степенного ряда  cos A:

нетрудно доказать, что для произвольной квадратной матрицы A  sin ²A +  cos ²A = I, где I – единичная матрица соответствующей размерности. Если бы существовала матрица A, о которой говорится в условии задачи, то для нее выполнялись бы следующие равенства: , . Покажем, что не существует такой матрицы , что , где t ≠ 0. Действительно, из системы уравнений

последовательно получаем: |a| = |d|, a + d ≠ 0, c = 0, d = 0, a = 0, приходя к противоречию. Таким образом, ответ к задаче будет отрицательным даже при замене числа 1996 на любое ненулевое число.

Задача 5:

Для строки S, состоящей из единиц и нулей, обозначим через  Δ (S) разность числа единиц и нулей. Например,  Δ (1001001) =  – 1. Назовем строку S сбалансированной, если для любой подстроки T (последовательных символов) S  – 2 ≤  Δ (T) ≤ 2. Так, строка 1001001 не является сбалансированной, так как содержит подстроку 00100. Найти число сбалансированных строк длины n.

Решение:

Во-первых, из условия следует, что (сбалансированная) строка не содержит трех одинаковых подряд идущих символов. Во-вторых, если в строке встретилось подряд две единицы, то следующим повторяющимся символом может быть только ноль (и наоборот); при этом четность номеров позиций первых из пар повторяющихся символов будет одинаковой. Поэтому всякая сбалансированная строка полностью задается следующими условиями:

• первый символ;
• номера позиций первых элементов пар повторяющихся символов (это числа одной четности).

Количество способов выбрать нечетные номера совпадает с числом непустых подмножеств множества 1,3,5, …  ⊂ 1,2, … ,n – 1. Поскольку данное множество содержит [n/2] чисел, то в нем 2^[n/2] – 1 непустых подмножеств. Аналогично подсчитывается количество способов выбрать четные номера: . Если учесть случай отсутствия пар повторяющихся символов, то получим, что количество способов выбрать места для расположения пар одинаковых символов равно . Ответ. Число сбалансированных строк длины n равно

Задача 6:

Пусть  – радиус-векторы вершин выпуклого многоугольника, внутри которого находится начало координат. Доказать, что существуют такие положительные числа x и y, что

Решение: Введя в качестве новых переменных натуральные логарифмы от старых и обозначая их по-прежнему x и y, переформулируем задачу так: Доказать, что существуют такие числа x и y (не обязательно положительные), что Нетрудно видеть, что последнее уравнение определяет стационарную точку функции Заметим, что (скалярное произведение векторов), где Пусть — полярные координаты точек (a_i,b_i)(i = 1, … ,n) и (x,y) соответственно;  ρ  =  min r_i. Упорядочим векторы по возрастанию полярного угла ; наибольший угол между соседними векторами обозначим  θ , ввиду условия задачи  θ  <  π . Для любого вектора r найдется такой вектор r_i, что . Введя обозначение: p =  ρ  cos  θ /2, cкалярное произведение этих векторов оценим снизу: Отсюда вытекает равномерная оценка для функции f:

Поэтому во всех точках окружности достаточно большого радиуса с центром в начале координат функция будет принимать значения, большие любого наперед заданного числа, в том числе n. Так как функция f непрерывна и f(0,0) = n, отсюда следует, что в некоторой внутренней точке круга указанного радиуса f достигает минимума; из дифференцируемости f вытекает, что точка минимума является стационарной точкой данной функции. Задача решена.