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

Задача 1.3.1

(1)(2)(3)

?

(1)

Если сумма $n$ действительных чисел равна $S$ , то найдётся слагаемое, не большее $S/n$ , а также слагаемое, не меньшее $S/n$ .

(2)

Если сумма $n$ целых чисел больше $kn$ для некоторого целого $k$ , то найдётся слагаемое, не меньшее $k+1$ .

(3)

Если сумма $n$ целых чисел меньше $kn$ для некоторого целого $k$ , то найдётся слагаемое, не большее $k-1$ .

Примечание.

?

Утверждение 1.3.1(1) применяется при решении задач, см., например, задачу 1.3.9. Его «дискретный аналог» утверждение 1.3.1(2) называют принципом Дирихле и часто формулируют так: при любом распределении $nk+1$ или более предметов по $n$ ящикам в каком-нибудь ящике окажется не менее $k+1$ предмета.

Методически более грамотно [MS, Словарик, раздел «оценка»] было бы назвать п.1.3 «Оценки от противного». Однако мы выбрали название, по которому большинство читателей смогут наиболее ясно представить себе содержание этого раздела.

Задача 1.3.2

(1)(2)

В мешке лежат 32 красных шара, 29 зеленых шаров, 45 синих, 17 желтых и по 30 белых, черных и серых. Какое наименьшее число шаров надо взять, чтобы среди них наверняка нашлись шары

?

(1)

всех 9 цветов?

(2)

7 цветов?

Задача 1.3.3

(1)(2)

?

(1)

Среди 7-значных чисел, заканчивающихся на 3 пятерки, существует не менее 1200 чисел, имеющих один и тот же остаток от деления на 7.

(2)

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

Задача 1.3.4

(1)(2)

?

(1)

Среди чисел, записываемых только единицами, есть число, которое делится на 1997.

(2)

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

Задача 1.3.5

(1)(2)

?

(1)

Среди любых $n$ действительных чисел найдутся два, дробные части которых различаются не более чем на $\dfrac {1}{n-1}$ .

(2)

В таблице $10\times 10$ расставлены целые числа, причем любые два числа в соседних по стороне клетках отличаются не более чем на 5. Докажите, что среди этих чисел найдутся два равных.

Задача 1.3.6

(1)(2)

Дано произвольное иррациональное число $\alpha$ .

?

(1)

Для произвольного натурального $N$ найдутся такие взаимно простые $p,q\in \mathbb {Z}$ , что $0 < q \leqslant N$ и

\left|\alpha - \frac{p}{q}\right| \leqslant \frac{1}{qN}.

(2)

Существует бесконечно много пар взаимно простых чисел $p,q\in \mathbb {Z}$ , для которых

\left|\alpha - \frac{p}{q}\right| \leqslant \frac{1}{q^2}.

Примечание.

?

Замечание. В формулировке утверждения 1.3.6(2) можно избавиться от взаимной простоты, так как для каждой дроби $\dfrac {p}{q}$ , для которой выполнено неравенство $\left|\alpha - \dfrac {p}{q}\right| \leqslant \dfrac {1}{q^2}$ , существует лишь конечное количество целых чисел $k > 0$ таких, что $\left|\alpha - \dfrac {pk}{qk}\right| \leqslant \dfrac {1}{(qk)^2}$ .

Задача 1.3.7

Натуральные числа от 1 до 101 записаны в некотором порядке. Докажите, что в этой последовательности найдется либо возрастающая, либо убывающая подпоследовательность длины 11.

?

Примечание.

?

Подпоследовательность — это то, что получается из последовательности вычеркиванием некоторых её членов.

Задача 1.3.8

(1)(2)

Имеется 10 яблок, каждое из которых весит не более 100 г, и две одинаковые тарелки. Докажите, что можно положить в тарелки

?

(1)

несколько яблок так, чтобы веса в тарелках отличались меньше чем на 1 г.

(2)

по одинаковому количеству яблок так, чтобы веса в тарелках отличались меньше чем на 2 г.

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

Задача 1.3.9

(1)(2)

Для любых $n$ векторов $v_1,\ldots ,v_n$ длины 1 на плоскости существует такой набор $\varepsilon_1,\ldots ,\varepsilon_n = \pm 1$ , что

?

(1)

$\left|\sum_{k=1}^{n}\varepsilon_kv_k\right| \leqslant \sqrt{n}$ ,

(2)

$\left|\sum_{k=1}^{n}\varepsilon_kv_k\right| \geqslant \sqrt{n}$ .

Принцип Дирихле