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

Задача 9.1.1

(1)(2)

Суммой $A+B$ подмножеств $A, B \subset \mathbb {R}$ или $A, B \subset \mathbb {Z}_m$ называется множество $A+B := \left\{ a+b : a \in A, b \in B\right\}$ .

?

(1)

Если $A, B \subset \mathbb {Z}_4$ , $\left|A+B\right| = \left|A\right| \neq 0$ и $\left|B\right| = 2$ , то $\left|A\right| \in \left\{ 2,4\right\}$ .

(2)

Если $A, B \subset \mathbb {Z}_6$ , $\left|A+B\right| = \left|A\right| \neq 0$ и $\left|B\right| = 2$ , то $\left|A\right| \in \left\{ 3,6\right\}$ .

Задача 9.1.2

(1)(2)

Суммой $A+B$ подмножеств $A, B \subset \mathbb {R}$ называется множество $A+B := \left\{ a+b : a \in A, b \in B\right\}$ . Для любых конечных подмножеств $A, B \subset \mathbb {R}$

?

(1)

$\max \left\{ \left|A\right|, \left|B\right|\right\} \leqslant \left|A+B\right| \leqslant \left|A\right| \cdot \left|B\right|$ ;

(2)

$\left|A\right| \leqslant \left|A+A\right| \leqslant \dfrac {\left|A\right|(\left|A\right|+1)}{2}$ .

Задача 9.1.3

(1)(2)

?

(1)

Если $A = \left\{ 2^j : j = 0, 1, \ldots , n-1\right\}$ , то $\left|A+A\right| = \dfrac {n(n+1)}{2}$ .

(2)

Для любой конечной арифметической прогрессии $P \subset \mathbb {R}$ верно неравенство $\left|P+P\right| = 2\left|P\right|-1$ .

Примечание.

?

Задача 9.1.3(1) даёт пример подмножества, для которого достигается верхняя оценка в задаче 9.1.2(2). Задача 9.1.3(2) даёт пример подмножества, для которого «почти достигается» нижняя оценка в задаче 9.1.2(2). Пример подмножества, для которого эта оценка достигается — произвольное одноэлементное подмножество.

Задача 9.1.4

Теорема Кнезера для $\mathbb {R}$ . Для любых конечных подмножеств $A, B \subset \mathbb {R}$ верно неравенство $\left|A+B\right| \geqslant \left|A\right|+\left|B\right|-1$ .

Следующий $\mathbb {Z}_p$ -аналог можно использовать в дальнейшем без доказательства.

Теорема Коши--Дэвенпорта. Для любого простого числа $p$ и для произвольных двух подмножеств $A, B \subset \mathbb {Z}_p$ верно неравенство

\left|A+B\right| \geqslant \min \left\{ \left|A\right|+\left|B\right|-1, p\right\} .

?

Задача 9.1.5

(1)(2)

?

(1)

Если $A, B \subset \mathbb {R}$ и $\left|A+B\right| = \left|A\right|$ , то $\left|B\right| = 1$ .

(2)

Если $p$ простое, $A, B \subset \mathbb {Z}_p$ и $\left|A+B\right| = \left|A\right|$ , то либо $\left|B\right| \leqslant 1$ , либо $A = \mathbb {Z}_p$ .

Задача 9.1.6

Аналогично сумме множеств можно определить их разность: $A-B := \left\{ a-b : a \in A, b \in B\right\}$ .

Неравенство Ружи. Для любых конечных подмножеств $A, B, C \subset \mathbb {R}$

\left|C\right| \cdot \left|A-B\right| \leqslant \left|A-C\right| \cdot \left|B-C\right|.

?

Задача 9.1.7

(1)(2)(3)

?

(1)

Для любого непустого конечного подмножества $X \subset \mathbb {R}$ выполнено неравенство $\left|X-X\right| \leqslant \dfrac {\left|X+X\right|^2}{\left|X\right|}$ .

(2)

Для любых непустых конечных подмножеств $X, Y \subset \mathbb {R}$ выполнено неравенство $\left|X+X\right| \leqslant \dfrac {\left|X+Y\right|^2}{\left|Y\right|}$ .

(3)

Для любых конечных подмножеств $X, Y \subset \mathbb {R}$ таких, что $X \cap Y \neq \emptyset$ , выполнено неравенство $\left|X+Y\right| \leqslant \dfrac {\left|X+X\right| \cdot \left|Y+Y\right|}{\left|X \cap Y\right|}$ .

Задача 9.1.8

Для любых непустых подмножеств $A, B \subset \mathbb {R}$ следующие утверждения эквивалентны:

$\left|A+B\right| = \left|A\right| \cdot \left|B\right|$ ;
$\left|A-B\right| = \left|A\right| \cdot \left|B\right|$ ;
$\left|\left\{ (a_1,a_2,b_1,b_2) \in A \times A \times B \times B : a_1+b_1 = a_2+b_2\right\} \right| = \left|A\right| \cdot \left|B\right|$ ;
$\left|\left\{ (a_1,a_2,b_1,b_2) \in A \times A \times B \times B : a_1-b_1 = a_2-b_2\right\} \right| = \left|A\right| \cdot \left|B\right|$ ;
$\left|A \cap (\left\{ x\right\} -B)\right| = 1$ для любого $x \in A+B$ ;
$\left|A \cap (B+\left\{ y\right\} )\right| = 1$ для любого $y \in A-B$ ;
$(A-A) \cap (B-B) = \left\{ 0\right\}$ .

?

Задача 9.1.9

Сумма произвольных подмножеств $X_1, X_2, \ldots , X_n \subset \mathbb {R}$ определяется как

X_1+X_2+\ldots +X_n := \left\{ x_1+x_2+\ldots +x_n : x_i \in X_i \text{ для любого } 1 \leqslant i \leqslant n\right\} .

Для произвольного подмножества $X \subset \mathbb {R}$ и любого целого $k>0$ положим $kX := \underbrace{X+X+\ldots +X}_{k \text{ раз}}$ .

Неравенство Ружи (задача 9.1.6) можно обобщить на случай суммы $n$ множеств.

Неравенство Плюннеке--Ружи. Для любых непустых конечных подмножеств $A_1, A_2, \ldots , A_n, B \subset \mathbb {R}$

\left|A_1+A_2+\ldots +A_n\right| \leqslant \frac{\left|A_1+B\right| \cdot \left|A_2+B\right| \cdot \ldots \cdot \left|A_n+B\right|}{\left|B\right|^{n-1}}.

Для любого конечного подмножества $A \subset \mathbb {R}$ и произвольного $n \in \mathbb {N}$ верны неравенства $\left|A\right| \leqslant \left|nA\right| \leqslant \dbinom {\left|A\right|+n-1}{n}$ .

?

Задача 9.1.10

Аналогично сумме множеств можно определить их произведение: $AB := \left\{ ab : a \in A, b \in B\right\}$ .

Если $A, B \subset \mathbb {Z}_5 \setminus \left\{ 0\right\}$ , $\left|AB\right| = \left|A\right| \neq 0$ и $\left|B\right|=2$ , то $\left|A\right| \in \left\{ 2,4\right\}$ .

?

Задача 9.1.11

(1)(2)

?

(1)

Существует такое $c>0$ , что для любого конечного множества $A \subset \mathbb {R}$ выполняется неравенство $\max \left\{ \left|A+A\right|, \left|A \cdot A\right|\right\} \geqslant c\left|A\right|^{5/4}$ .

(2)

Существует такое $c>0$ , что для любой арифметической прогрессии $P \subset \mathbb {R}$ длины более 3 верно неравенство $\left|P \cdot P\right| > c\left|P\right|^{5/4}$ .

Примечание.

?

На самом деле, если $P$ — арифметическая прогрессия длины $n$ во множестве целых чисел, то можно улучшить оценку из задачи 9.1.11(2). А именно, для любого $\varepsilon \in (0,2)$ существует такое $c>0$ , что $\left|P \cdot P\right| \geqslant c\left|P\right|^{\varepsilon }$ . Доказательство этого факта использует нетривиальные теоремы из теории чисел, поэтому выходит за рамки этой книги.

Задача 9.1.12

Пусть $P$ — множество некоторых точек на плоскости, $L$ — множество некоторых прямых на плоскости. Числом инциденций $I(P,L) := \left|\left\{ (p,l) \in P \times L : p \in l\right\} \right|$ называется количество пар вида (точка на прямой, прямая), где прямая и точка взяты из соответствующих множеств.

Дано произвольное конечное непустое подмножество $A \subseteq \mathbb {R}$ . Обозначим через $\mathscr {L}$ семейство прямых на плоскости, задаваемых уравнением $y=a(x-b)$ , где $a,b \in A$ . Обозначим $\mathscr {P} := (A+A) \times (A \cdot A)$ . Докажите, что общее количество инциденций между прямыми из $\mathscr {L}$ и точками из $\mathscr {P}$ не меньше чем $\left|A\right|^3$ .

?

Аддитивная комбинаторика