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

Задача 1.6.1

(1)(2)(3)(4)

?

(1)

Дано 21 девятиэлементное подмножество 30-элементного множества. Тогда какой-то элемент 30-элементного множества содержится по крайней мере в семи данных подмножествах.

(2)

Комиссия собиралась 40 раз. На каждом заседании было ровно 10 человек, любые два не были вместе больше одного раза. Тогда в комиссии хотя бы 60 человек.

(3)

В компании у любых двух знакомых друг с другом человек есть ровно 5 общих знакомых (кроме них самих). Тогда количество пар знакомых между собой людей в компании делится на 3.

(4)

Обозначим через $P_n(k)$ число перестановок множества натуральных чисел от 1 до $n$ , оставляющих ровно $k$ чисел на своём месте. Тогда $\displaystyle \sum_{k=0}^{n}k\cdot P_n(k) = n!$ .

Задача 1.6.2

(1)(2)

Пусть $\mathscr {F}$ — любое семейство $k$ -элементных подмножеств $n$ -элементного множества.

?

(1)

Если $k \geqslant l$ и каждое $l$ -элементное подмножество $n$ -элементного множества содержится в некотором подмножестве из $\mathscr {F}$ , то $|\mathscr {F}| \geqslant \dbinom {n}{l}\Big/\dbinom {k}{l}$ .

(2)

Количество $(k-1)$ -элементных подмножеств $n$ -элементного множества, целиком содержащихся хотя бы в одном из подмножеств семейства $\mathscr {F}$ , не меньше $\dfrac {k|\mathscr {F}|}{n-k+1}$ .

Задача 1.6.3

На планете Марс 100 государств объединены в блоки, в каждом из которых не больше 50 государств. Известно, что любые два государства состоят вместе хотя бы в одном блоке. Найдите минимально возможное число блоков. (Ср. с задачей 1.6.2(1).)

?

Задача 1.6.4

Ровно 19 вершин правильного 97-угольника покрашены в белый цвет, остальные вершины покрашены в чёрный. Тогда число равнобедренных одноцветных треугольников с вершинами в вершинах 97-угольника не зависит от способа раскраски. (Треугольник одноцветный, если все его вершины или белые, или чёрные.)

?

Задача 1.6.5

Даны числа $n \geqslant k$ и множество $S$ из $n$ точек на плоскости. Если любые три точки из множества $S$ не лежат на одной прямой и для любой точки $P \in S$ существуют хотя бы $k$ различных точек из множества $S$ , равноудалённых от $P$ , то $k < \dfrac {1}{2} + \sqrt{2n}$ .

?

Задача 1.6.6

В любом множестве из $n$ различных натуральных чисел найдётся подмножество из более чем $n/3$ чисел, в котором нет трёх чисел, сумма двух из которых равна третьему.

?

Задача 1.6.7

По каждому из 100 видов работ в фирме имеется ровно 8 специалистов. Каждому сотруднику нужно дать выходной в субботу или в воскресенье. Докажите, что это можно сделать так, чтобы и в субботу, и в воскресенье для каждого вида работ на работе был специалист по нему.

?

Примечание.

?

Понятно, что при данном числе $k$ специалистов (в задаче 1.6.7 $k=8$ ) для малого числа видов работ так распределить выходные всегда можно. А при большом числе $l$ видов работ это может уже не получиться. Указание ниже находит асимптотическую оценку снизу для такого числа $l$ .

Вот более учёная формулировка (обобщения) задачи 1.6.7. Имеется $l = 2^{k-1}$ подмножеств некоторого множества, в каждом из которых ровно $k$ элементов. Тогда элементы этого множества можно раскрасить в два цвета так, чтобы никакое из $l$ подмножеств не было одноцветно. Ср. с задачей 6.2.1(1).

Задача 1.6.8

(1)(2)

?

(1)

Если для некоторого чётного $n$

\left(1-2\frac{\binom {n/2}{k}}{\binom {n}{k}}\right)^l 2^n < 1,

то в $n$ -элементном множестве найдётся $l$ таких $k$ -элементных подмножеств, что при любой раскраске элементов этого множества в два цвета хотя бы одно из этих $l$ подмножеств одноцветно.

(2)

Существует такое $c>0$ , что для любого $k$ существует не более чем $ck^22^k$ таких $k$ -элементных подмножеств некоторого множества, что при любой раскраске элементов этого множества в два цвета одно из этих подмножеств одноцветно.

Подсчёт двумя способами