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

Задача 5.2.1

(1)(2)

В группе студентов 20 человек. Из них ровно 5 человек — специалисты по поиску в интернете, 5 — по борьбе со спамом и т.д., всего 18 видов проблем (так что, очевидно, некоторые студенты являются специалистами по нескольким проблемам). Требуется составить из этих студентов сильную команду разработчиков. При этом хочется, чтобы для каждой проблемы в команде нашелся специалист по ней и чтобы размер команды был как можно меньше (для экономии зарплаты).

?

(1)

При любом раскладе получится набрать такую команду из семи человек.

(2)

При некотором раскладе не получится набрать такую команду из пяти человек.

Задача 5.2.2

Для набора $\left\{ \left\{ 1,6\right\} ,\left\{ 1,2\right\} ,\left\{ 2,3\right\} ,\left\{ 3,4\right\} ,\left\{ 4,5\right\} ,\left\{ 5,6\right\} \right\}$ множеств найдите (1) какую-нибудь с.о.п.; (2) с.о.п. наименьшего размера.

?

Примечание.

?

Системой общих представителей (сокращённо с.о.п.) для набора $\mathscr {M}$ множеств называется любое такое множество $A$ , что $M \cap A \neq \emptyset$ для любого $M \in \mathscr {M}$ .

Задача 5.2.3

(1)(2)

?

(1)

Найдите наименьший размер с.о.п. для набора всех $k$ -элементных подмножеств множества $\mathscr {R}_{n}$ .

(2)

Сколько для него имеется с.о.п. наименьшего размера?

Примечание.

?

Минимальная с.о.п. — с.о.п. наименьшего размера для данного набора $\mathscr {M}$ . Назовём $(n,s,k)$ -набором элемент из $\binom {\binom {\mathscr {R}_{n}}{k}}{s}$ , т.е. набор $k$ -элементных подмножеств множества $\mathscr {R}_{n}$ , в котором $s$ множеств. (Этот термин не общепринят.)

Задача 5.2.4

(1)(2)

?

(1)

Постройте $\left(2n, 2\binom {n-1}{k-1}, k\right)$ -набор, для которого минимальная с.о.п. состоит из двух элементов и единственна.

(2)

При данных $n,k$ найдите наибольшее $s$ , для которого найдётся $(n,s,k)$ -набор, имеющий ровно две минимальные с.о.п.

Задача 5.2.5

Жадным алгоритмом называется следующий. Возьмём любой элемент, лежащий в максимальном количестве множеств данного набора. Добавим его в «пред-с.о.п.» и выкинем множества, которые его содержат. Аналогично возьмём элемент, лежащий в максимальном количестве оставшихся множеств, и т.д.

Постройте пример набора множеств, у которого размер минимальной с.о.п. на $k$ меньше размера любой из с.о.п., которые могут быть получены жадным алгоритмом, если (1) $k=1$ ; (2) $k=2$ ; (3) $k$ произвольно.

?

Задача 5.2.6

?

(1)

Для любого $(n,s,k)$ -набора найдется с.о.п. размера меньше

G(n,s,k) := \max \left\{ \frac{n}{k}, \frac{n}{k}\ln \frac{sk}{n}\right\} + \frac{n}{k} + 1.

(2)

Если $n \geqslant 32k$ и $60 \leqslant \dfrac {sk}{n} < e^{k}$ , то найдется $(n,s,k)$ -набор, размер любой с.о.п. которого больше $\dfrac {n}{64k}\ln \dfrac {sk}{n}$ .

(3)

Если

k \leqslant n-l \quad \text{и} \quad G\left(\binom {n}{k}, \binom {n}{l}, \binom {n-l}{k}\right) \leqslant s,

то найдется $(n,s,k)$ -набор, размер любой с.о.п. которого больше $l$ .

(4)

Для всех достаточно больших $n$ если $k^{2}l+kl^{2} < n^{1{,}8}$ , то $k < n-l$ и $\binom {n}{k}\Big/\binom {n-l}{k} < 2e^{kl/n}$ .

(5)

Для всех достаточно больших $n$ и $k$ если $101\ln \ln k < \ln \dfrac {sk}{n} < \sqrt{k} < \sqrt[4]{n}$ , то найдется $(n,s,k)$ -набор, размер любой с.о.п. которого больше $0{,}99\dfrac {n}{k}\ln \dfrac {sk}{n}$ .

(6)

Если

l \leqslant n-k \quad \text{и} \quad \binom {n}{l}\left(\binom {n}{k}-\binom {n-l}{k}\right) < \binom {\binom {n}{k}}{s},

то найдется $(n,s,k)$ -набор, размер любой с.о.п. которого больше $l$ .

Системы общих представителей