Math Problems Vault

Problem 5.2.1

(1)(2)

A group of students consists of 20 people. Exactly 5 of them are specialists in internet search, 5 in fighting spam, etc., 18 kinds of problems in total (so, obviously, some students are specialists in several problems). It is required to form a strong team of developers from these students. One wants the team to contain a specialist in each problem and the size of the team to be as small as possible (to save on salaries).

?

(1)

Under any arrangement, it is possible to recruit such a team of seven people.

(2)

Under some arrangement, it is not possible to recruit such a team of five people.

Problem 5.2.2

For the collection $\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\}$ of sets, find (1) some SCR; (2) an SCR of the smallest size.

?

Remark.

?

A system of common representatives (SCR for short) for a collection $\mathscr {M}$ of sets is any set $A$ such that $M \cap A \neq \emptyset$ for every $M \in \mathscr {M}$ .

Problem 5.2.3

(1)(2)

?

(1)

Find the smallest size of an SCR for the collection of all $k$ -element subsets of the set $\mathscr {R}_{n}$ .

(2)

How many SCRs of the smallest size does it have?

Remark.

?

A minimal SCR is an SCR of the smallest size for a given collection $\mathscr {M}$ . We call an element of $\binom {\binom {\mathscr {R}_{n}}{k}}{s}$ an $(n,s,k)$ -collection, i.e., a collection of $k$ -element subsets of the set $\mathscr {R}_{n}$ that contains $s$ sets. (This term is not generally accepted.)

Problem 5.2.4

(1)(2)

?

(1)

Construct a $\left(2n, 2\binom {n-1}{k-1}, k\right)$ -collection for which the minimal SCR consists of two elements and is unique.

(2)

For given $n,k$ , find the largest $s$ for which there exists an $(n,s,k)$ -collection having exactly two minimal SCRs.

Problem 5.2.5

The greedy algorithm is the following one. Take any element lying in the maximum number of sets of the given collection. Add it to the ``pre-SCR'' and discard the sets that contain it. Similarly, take an element lying in the maximum number of the remaining sets, etc.

Construct an example of a collection of sets for which the size of a minimal SCR is $k$ less than the size of any of the SCRs that can be obtained by the greedy algorithm, if (1) $k=1$ ; (2) $k=2$ ; (3) $k$ is arbitrary.

?

Problem 5.2.6

?

(1)

For any $(n,s,k)$ -collection there exists an SCR of size less than

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

(2)

If $n \geqslant 32k$ and $60 \leqslant \dfrac {sk}{n} < e^{k}$ , then there exists an $(n,s,k)$ -collection every SCR of which has size greater than $\dfrac {n}{64k}\ln \dfrac {sk}{n}$ .

(3)

If

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

then there exists an $(n,s,k)$ -collection every SCR of which has size greater than $l$ .

(4)

For all sufficiently large $n$ , if $k^{2}l+kl^{2} < n^{1{,}8}$ , then $k < n-l$ and $\binom {n}{k}\Big/\binom {n-l}{k} < 2e^{kl/n}$ .

(5)

For all sufficiently large $n$ and $k$ , if $101\ln \ln k < \ln \dfrac {sk}{n} < \sqrt{k} < \sqrt[4]{n}$ , then there exists an $(n,s,k)$ -collection every SCR of which has size greater than $0{,}99\dfrac {n}{k}\ln \dfrac {sk}{n}$ .

(6)

If

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

then there exists an $(n,s,k)$ -collection every SCR of which has size greater than $l$ .