Банк задач по математике

Задача 1.2.1

(1)(2)(3)

Обозначим через $\varphi (n)$ функцию Эйлера, т.е. количество чисел от 1 до $n$ , взаимно простых с числом $n$ .

?

(1)

Найдите количество чисел, не превосходящих 1001 и не делящихся ни на одно из чисел 7, 11, 13.

(2)

Найдите $\varphi (1), \varphi (p), \varphi (p^2), \varphi (p^\alpha )$ , где $p$ — простое число, $\alpha > 2$ .

(3)

$\varphi (n) = n\left(1 - \dfrac {1}{p_1}\right)\ldots \left(1-\dfrac {1}{p_s}\right)$ , где $n = p_1^{\alpha_1}\cdot \ldots \cdot p_s^{\alpha_s}$ — каноническое разложение числа $n$ .

Задача 1.2.2

(1)(2)

?

(1)

На полу комнаты площадью $24\, \text{м}^2$ расположены три ковра (произвольной формы) площади $12\, \text{м}^2$ каждый. Тогда площадь пересечения некоторых двух ковров не меньше $4\, \text{м}^2$ .

(2)

На кафтане расположено пять заплат (произвольной формы). Площадь каждой из них больше половины площади кафтана. Тогда площадь общей части некоторых двух заплат больше одной пятой площади кафтана.

Задача 1.2.3

(1)(2)(3)

Рассмотрим подмножества $A_1,\ldots ,A_n$ конечного множества $U$ . Положим по определению $\left|\bigcap_{j\in \varnothing }A_j\right| := U$ .

?

(1)

Пусть число $\alpha_{|S|} := \left|\bigcap_{j\in S}A_j\right|$ зависит только от размера $|S|$ набора $S \subset \mathscr {R}_n$ индексов, а не от самого набора. Тогда

|A_1\cup \ldots \cup A_n| = \sum _{k=1}^{n}(-1)^{k+1}\binom {n}{k}\alpha _k,

|U\setminus (A_1\cup \ldots \cup A_n)| = \sum _{k=0}^{n}(-1)^k\binom {n}{k}\alpha _k.

(2)

Обозначим $M_k := \displaystyle \sum_{S\in \binom {\mathscr {R}_n}{k}}\left|\bigcap_{j\in S}A_j\right|$ . В частности, $M_0 := |U|$ . Тогда

\begin{align} |A_1\cup \ldots \cup A_n| & = M_1 - M_2 + M_3 - \ldots + (-1)^{n+1}M_n, \\ |U\setminus (A_1\cup \ldots \cup A_n)| & = M_0 - M_1 + M_2 - \ldots + (-1)^n M_n. \end{align}

(3)

Неравенства Бонферрони. Для любого $s$ , $s < \dfrac {n}{2}$ ,

\begin{align} M_1 - M_2 + M_3 - \ldots - M_{2s} & \leqslant |A_1\cup \ldots \cup A_n| \leqslant M_1 - M_2 + M_3 - \ldots + M_{2s+1}, \\ M_0 - M_1 + M_2 - \ldots + M_{2s} & \geqslant |U\setminus (A_1\cup \ldots \cup A_n)| \geqslant \\ & \geqslant M_0 - M_1 + M_2 - \ldots - M_{2s+1}. \end{align}

Примечание.

?

В этом разделе предлагаются задачи следующего типа: дано конечное множество $U$ и набор свойств (подмножеств) $A_k \subset U$ , $k=1,\ldots ,n$ . Требуется найти количество элементов, для которых выполнено хотя бы одно из свойств $A_k$ (т.е. $|A_1\cup \ldots \cup A_n|$ ), либо количество элементов, для которых не выполнено ни одно из свойств $A_k$ (т.е. $|U\setminus (A_1\cup \ldots \cup A_n)|$ ).

Для этого используется два варианта формулы включений и исключений (см. задачу 1.2.3(2)). При этом если во всех пересечениях множеств набора число элементов зависит только от количества пересекаемых множеств, формулу можно упростить (см. задачу 1.2.3(1)).

В задачах 1.2.4(1) и 1.2.5 предполагается, что ответ записывается в виде суммы (аналогично формуле включений и исключений).

Задача 1.2.4

(1)(2)

На полке стоят 10 различных книг.

?

(1)

Сколькими способами их можно переставить так, чтобы ни одна книга не осталась на своем месте?

(2)

Количество таких перестановок книг, при которых на месте остаётся ровно 4 книги, больше 50000.

Задача 1.2.5

(1)(2)

?

(1)

Сколькими способами можно расселить 20 туристов по 5 различным домикам, чтобы ни один домик не оказался пустым?

(2)

Сколько существует различных сюръекций $f: \mathscr {R}_k \to \mathscr {R}_n$ ?

Задача 1.2.6

Докажите следующую формулу:

\begin{align} n!\cdot x_1x_2\ldots x_n & = (x_1+x_2+\ldots +x_n)^n - \\ & \quad - \sum _{1\leqslant i_1 < i_2 < \ldots < i_{n-1}\leqslant n}(x_{i_1}+x_{i_2}+\ldots +x_{i_{n-1}})^n + \\ & \quad + \sum _{1\leqslant i_1 < i_2 < \ldots < i_{n-2}\leqslant n}(x_{i_1}+x_{i_2}+\ldots +x_{i_{n-2}})^n - \ldots \\ & \quad \ldots + (-1)^{n-1}\sum _{i=1}^{n}x_i^n. \end{align}

?

Формула включений и исключений