Math Problems Vault

Problem 6.2.1

(1)(2)

?

(1)

For each of 100 types of work, a company has exactly 8 specialists. An employee may be a specialist in several types of work; the assignment of specialists to types of work is known to the person who schedules days off. Each employee must be given a day off on either Saturday or Sunday. Prove that this can be done so that on both Saturday and Sunday, for each type of work, a specialist in it is at work. (This is Problem 1.6.7.)

(2)

For each of several types of work, a company has exactly 8 specialists. (Now the number of types of work need not be 100.) Each type of work shares specialists with at most 30 other types. Each employee must be given a day off on either Saturday or Sunday. Prove that this can be done so that on both Saturday and Sunday, for each type of work, a specialist in it is at work.

Problem 6.2.2

(1)(2)

?

(1)

200 students from 10 groups, each of which has 20 students, stand in a circle. Prove that one can choose a leader in each group so that no two leaders stand next to each other.

(2)

The same for 1600 students from 100 groups, each of which has 16 students.

Problem 6.2.3

(1)(2)

?

(1)

Prove that the first 8 positive integers can be colored in 2 colors so that there is no monochromatic arithmetic progression of length 3.

(2)

Prove that the first 15 million positive integers can be colored in 2 colors so that there is no monochromatic arithmetic progression of length 32.

Problem 6.2.4

(1)(2)

?

(1)

Prove that for any $M \in \mathbb {R}$ all real numbers can be colored in 2 colors so that for any $x \in \mathbb {R}$ the numbers $x$ and $x+M$ have different colors.

(2)

Prove that for any 25 distinct numbers $M_1,\ldots ,M_{25} \in \mathbb {R}$ all real numbers can be colored in 3 colors so that for any $x \in \mathbb {R}$ the numbers $x+M_1,\ldots ,x+M_{25}$ include numbers of each of the three colors.

Problem 6.2.5

Every inhabitant of a town is either healthy or sick, and also either rich or poor. Wealth and health are independent, i.e. the proportion of healthy rich inhabitants among the rich equals the proportion of healthy inhabitants among all inhabitants. It is known that there is a rich townsperson and there is a healthy townsperson. Must there be a rich healthy townsperson?

?

Problem 6.2.6

(1)(2)(3)

Are the following subsets dependent? (We call subsets dependent if they are not independent.)

?

(1)

In the set of all squares of a chessboard, the subset of squares in its first three rows and the subset of squares in its last four columns.

(2)

The subsets $\left\{ 1,2\right\} \subset \left\{ 1,2,3,4\right\}$ and $\left\{ 1,3\right\} \subset \left\{ 1,2,3,4\right\}$ .

(3)

The subsets $\left\{ 1,2\right\} \subset \left\{ 1,2,3,4,5,6\right\}$ and $\left\{ 1,3\right\} \subset \left\{ 1,2,3,4,5,6\right\}$ .

Problem 6.2.7

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

Are the following subsets of the set of integers from 1 to 105 dependent?

?

(1)

The subset of numbers divisible by 5 and the subset of numbers divisible by 7.

(2)

The subset of numbers divisible by 15 and the subset of numbers divisible by 21.

(3)

The subset of numbers divisible by 15 and the subset of numbers divisible by 5.

(4)

The subset of numbers divisible by 10 and the subset of numbers divisible by 7.

Problem 6.2.8

(1)(2)(3)

(Cf. the remark after Problem 6.2.1 (2).) Are the following subsets of the set of all colorings of the numbers $1,2,\ldots ,400$ in two colors dependent?

?

(1)

The subset of colorings for which $\left\{ 1,2,\ldots ,8\right\}$ is monochromatic and the subset of colorings for which $\left\{ 11,12,\ldots ,18\right\}$ is monochromatic.

(2)

The subset of colorings for which $\left\{ 1,2,\ldots ,8\right\}$ is not monochromatic and the subset of colorings for which $\left\{ 11,12,\ldots ,18\right\}$ is not monochromatic (cf. Problem 6.2.1 (2)).

(3)

The subset of colorings for which $\left\{ 1,2,\ldots ,8\right\}$ is monochromatic and the subset of colorings for which $\left\{ 6,7,\ldots ,13\right\}$ is monochromatic.

Problem 6.2.9

Subsets $A$ and $B$ of a finite set are independent if and only if $A$ and $\overline{B}$ are independent.

?

Problem 6.2.10

(1)(2)(3)

?

(1)

Must there be a rich, healthy, smart citizen if in a city the proportion of rich citizens is greater than $\dfrac {2}{3}$ , the proportion of healthy ones is greater than $\dfrac {2}{3}$ , and the proportion of smart ones is greater than $\dfrac {2}{3}$ ?

(2)

The same question if the city has a rich citizen, a healthy citizen and a smart citizen, wealth, health and intelligence are pairwise independent, and the proportion of rich healthy smart citizens among the rich healthy ones is the same as the proportion of smart citizens among all inhabitants. (Together with the pairwise independence condition, the latter is called mutual independence.)

(3)

The same question if more than half of the citizens are rich, more than half are healthy, more than half are smart, wealth and intelligence are independent, and health and intelligence are independent.

Problem 6.2.10 shows that the stronger the condition characterizing the independence of several sets, the smaller the proportion of each set that suffices to guarantee that their intersection is nonempty. Moreover, the most interesting result (6.2.10 (3)) is obtained in the middle'' between the extreme conditions — the complete absence of independence (6.2.10 (1)) and mutual independence (6.2.10 (2)). This often happens: the most useful considerations lie between the extreme'' points of view.

Problem 6.2.11

(1)(2)

?

(1)

Let $A_1,A_2,A_3,A_4$ be subsets of a 720-element set, each of which has more than 480 elements. If $A_k$ and $A_{k+1}$ are independent for every $k=1,2,3$ , then $A_1\cap A_2\cap A_3\cap A_4 \neq \emptyset$ .

(2)

Let $n \geqslant 2$ and let $A_1,A_2,\ldots ,A_n$ be subsets of a finite set, the proportion of each of which is greater than $1-\dfrac {1}{n-1}$ . If $A_k$ and $A_{k+1}$ are independent for every $k=1,2,\ldots ,n-1$ , then $A_1\cap A_2\cap \ldots \cap A_n \neq \emptyset$ .

For more on independence, see [KZP].

Problem 6.2.12

(1)(2)

Give an example of subsets $A, B_1, B_2$ of a finite set that are

?

(1)

pairwise independent, but such that $A$ is not independent of the collection $B_1, B_2$ ;

(2)

not pairwise independent, but such that $A$ is independent of the collection $B_1, B_2$ .

Problem 6.2.13

Denote by $M$ the family of all colorings of the set $\left\{ 1,2,\ldots ,400\right\}$ in two colors. For a subset $\alpha \subset \left\{ 1,2,\ldots ,400\right\}$ , denote by $A_\alpha \subset M$ the subset of those colorings for which $\alpha$ is monochromatic. Then $A_{\left\{ 1,2,\ldots ,8\right\} }$ is independent of the collection $\left\{ A_\alpha : \alpha \subset \left\{ 9,10,\ldots ,400\right\} \right\}$ . (Cf. the remark after Problem 6.2.1 (2).)

?

Problem 6.2.14

The following conditions on subsets $A, B_1,\ldots ,B_k$ are equivalent:

$A$ is independent of the collection $B_1,\ldots ,B_k$ ;
$\overline{A}$ is independent of the collection $B_1,\ldots ,B_k$ ;
$A$ is independent of the collection $\overline{B_1},\ldots ,\overline{B_k}$ .

?

Problem 6.2.15

(1)(2)(3)

?

(1)

The Lovász local lemma in symmetric form. Let $A_1,\ldots ,A_n$ be subsets of a finite set. If for some $d$ and every $k$ the proportion of the subset $A_k$ is at least $1-\dfrac {1}{4d}$ and there exists a collection of at least $n-d$ subsets $A_j$ of which $A_k$ is independent, then $A_1\cap \ldots \cap A_n \neq \emptyset$ .

(2)

For $d > 2$ , the statement of part (1) remains true if $1-\dfrac {1}{4d}$ is replaced by $1-\dfrac {1}{e(d+1)}$ .

(3)

If $a_k=1$ for every $k\leqslant 0$ and for some $d\geqslant 2$ the inequality $a_{k+1}\geqslant a_k-\dfrac {a_{k-d}}{4d}$ holds for every $k\geqslant 0$ , then $a_k > 0$ for every $k$ .

Remark.

?

Here is a formulation of part (1) in probabilistic language, which is not used in what follows. Let a probability space be given and let $A_1,\ldots ,A_n$ be events. Suppose that for some $d$ and every $k$ the probability of the event $A_k$ is at least $1-\dfrac {1}{4d}$ and there exists a collection of at least $n-d$ events of which $A_k$ is independent. Then the probability of the event $A_1\cap \ldots \cap A_n$ is positive.

Problem 6.2.16

(1)(2)

Suppose we are given a number

?

(1)

$k \geqslant 10$ ;

(2)

$k=9$

and a family of $k$ -element subsets of a finite set $M$ . If each element of $M$ is contained in exactly $k$ subsets of the family, then there exists a coloring of $M$ in two colors for which every subset of the family contains elements of both colors. (That is, the chromatic number of any $k$ -uniform $k$ -regular hypergraph equals two for $k\geqslant 9$ . Cf. Problem 6.2.1 (2).)

Problem 6.2.17

Several subsets of a finite set are chosen. Each of them has at least 3 elements. Each of them intersects at most $a_i$ of the chosen $i$ -element subsets. If $\displaystyle \sum_i a_i2^{-i} \leqslant 1/8$ , then the elements of the given set can be colored in two colors so that every chosen subset contains elements of both colors.

?

Problem 6.2.18

(1)(2)(3)

?

(1)

For any partition of the vertex set of a cycle of length $16n$ into $n$ sets of 16 vertices each, one can choose one vertex from each set so that there are no edges between the chosen $n$ vertices.

(2)

The same for $11n$ vertices.

(3)

In a graph, the degree of every vertex does not exceed $\Delta$ . All the vertices are colored in $r$ colors. There are at least $2e\Delta +1$ vertices of each color. Then one can choose $r$ vertices of different colors, no two of which are joined by an edge.

Problem 6.2.19

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

?

(1)

Every $k$ -element arithmetic progression in $\left\{ 1,2,\ldots ,n\right\}$ is intersected by at most $k^2\left[\dfrac {n}{k-1}\right]$ other such progressions.

(2)

For every positive integer $k$ there exists a coloring of the first $\left[\dfrac {2^{k-3}(k-1)}{k^2}\right]$ positive integers in 2 colors for which there is no monochromatic $k$ -element arithmetic progression.

(3)

Every $k$ -element arithmetic progression in $\left\{ 1,2,\ldots ,n\right\}$ is intersected by at most $nk$ other such progressions.

(4)

For every positive integer $k$ there exists a coloring of the first $\left[\dfrac {2^{k-3}}{k}\right]$ positive integers in 2 colors for which there is no monochromatic $k$ -element arithmetic progression.

Problem 6.2.20

(1)(2)(3)

?

(1)

If $X\subset \mathbb {R}$ is a finite set and $m,r$ are positive integers such that $4rm(m-1)\left(1-\dfrac {1}{r}\right)^m < 1$ , then for any $m$ -element subset $M\subset \mathbb {R}$ there exists a coloring of $\mathbb {R}$ in $r$ colors such that for any $x\in X$ the set $x+M := \left\{ x+a : a\in M\right\}$ contains points of each of the $r$ colors.

(2)

The same for $X=\mathbb {Z}$ .

(3)

The same for $X=\mathbb {R}$ .

Problem 6.2.21

(1)(2)

?

(1)

If $\dbinom {n}{2}\dbinom {k}{n-2}+1 < 2^{\binom {n}{2}-1}/e$ , then $R(n,n) > k$ , where $R(n,n)$ is the Ramsey number (Sec. 4.1).

(2)

$R(n,n) \gtrsim \sqrt{2}e^{-1}n2^{n/2}$ . (Cf. Problem 4.1.5.)

Problem 6.2.22

There are several colors. To each vertex of some graph a list of at least $10d$ of these colors is assigned, where $d>1$ . For any vertex $v$ and any color from its list, there are at most $d$ neighbors of the vertex $v$ whose lists contain this color. Then one can color each vertex of the graph with some color from its list so that the endpoints of every edge have different colors.

?

Problem 6.2.23

In a directed graph, at most $\Delta$ edges enter each vertex and at least $\delta$ edges leave each vertex. Then for any positive integer $k \leqslant \dfrac {1}{1-(4\delta \Delta )^{-1/\delta }}$ there exists a directed cycle of length divisible by $k$ .

?

Problem 6.2.24

The cells of an $n\times n$ board are colored in several colors. There are at most $\dfrac {n-1}{16}$ cells of each color. Then one can place $n$ pairwise non-attacking rooks on the board so that they stand on cells of different colors.

?

Problem 6.2.25

A CNF formula is a conjunction of a collection of disjunctions of some of the variables $x_1,\ldots ,x_n$ or their negations. If each factor'' of a CNF formula has exactly $k$ summands'' and each ``factor'' has common variables with at most $2^{k-2}$ others, then the Boolean function defined by the formula is not identically zero.

?

Remark.

?

One of the central problems in computer science is the $k$ -satisfiability problem ( $k$ -SAT problem): for a given CNF formula each disjunction of which contains exactly $k$ variables, determine whether the Boolean function it defines is identically zero. For $k=2$ there is a polynomial algorithm solving it. For larger $k$ , no fast algorithms answering this question are known. Constructing such an algorithm, or proving that none exists, is equivalent to solving the famous open problem `` $\mathrm{P} \neq \mathrm{NP}$ ''.

Problem 6.2.26

(1)(2)

?

(1)

Lovász local lemma. *Let $A_1,\ldots ,A_n$ be subsets of a finite set, $J_1,\ldots ,J_n\subset \left\{ 1,\ldots ,n\right\}$ , and $\gamma_1,\ldots ,\gamma_n\in (0,1)$ . Suppose also that for any $k$

the proportion of the subset $A_k$ is at least $1-(1-\gamma_k)\displaystyle \prod_{j\notin J_k}\gamma_j$ ;
the set $A_k$ is independent of the collection $\left\{ A_j : j\in J_k\right\}$ .

Then the proportion of the intersection $\displaystyle \bigcap_{k=1}^{n}A_k$ is at least $\displaystyle \prod_{k=1}^{n}\gamma_k > 0$ .*

(2)

There exists $c>0$ such that $R(3,n) > cn\sqrt{n}$ for every $n$ .

Remark.

?

Here is a formulation of part (1) in probabilistic language, which is not used in what follows. Let a probability space be given, let $A_1,\ldots ,A_n$ be events, $J_1,\ldots ,J_n\subset \left\{ 1,\ldots ,n\right\}$ , and $\gamma_1,\ldots ,\gamma_n\in (0,1)$ . Suppose that for any $k$ the probability of the event $A_k$ is at least $1-(1-\gamma_k)\displaystyle \prod_{j\notin J_k}\gamma_j$ and the event $A_k$ is independent of the collection $\left\{ A_j : j\in J_k\right\}$ . Then the probability of the event $A_1\cap \ldots \cap A_n$ is at least $\displaystyle \prod_{j=1}^{m}\gamma_j$ .

Remark. Using more involved computations, one derives from the Lovász local lemma that $R(3,n) > c_1n^2/\ln^2 n$ . Moreover, this is the ``best'' that can be squeezed out of the Lovász local lemma. The inequality $R(3,n) > c_2n^2/\ln n$ (Kim's theorem) is also known. Its proof, instead of the Lovász local lemma, uses quasirandom graphs, sharp concentration inequalities, etc.