Math Problems Vault

Problem 7.1.1

Recall that for a set $F$ one defines $F^{n} := \left\{ (a_{1}, a_{2}, \ldots , a_{n}) : a_{1}, a_{2}, \ldots , a_{n} \in F\right\}$ . The elements of this set are called vectors (or tuples, or points). If $F \in \left\{ \mathbb {Z}_{2}, \mathbb {Z}, \mathbb {Q}, \mathbb {R}\right\}$ , then vectors can be added componentwise: $(x_{1}, \ldots , x_{n}) + (y_{1}, \ldots , y_{n}) := (x_{1}+y_{1}, \ldots , x_{n}+y_{n})$ . If $F \in \left\{ \mathbb {Z}, \mathbb {Q}, \mathbb {R}\right\}$ , then a vector can be multiplied componentwise by a number $\lambda \in F$ : $\lambda (x_{1}, \ldots , x_{n}) := (\lambda x_{1}, \ldots , \lambda x_{n})$ (this can also be done for $F = \mathbb {Z}_{2}$ , but it is not interesting).

Among any $n+1$ tuples of length $n$ consisting of zeros and ones, there are several (a nonzero number of) tuples whose componentwise sum modulo two is the zero tuple.
For any $n+1$ vectors $v_{1}, \ldots , v_{n+1} \in \mathbb {Q}^{n}$ there exist rational numbers $\lambda_{1}, \ldots , \lambda_{n+1}$ , not all equal to zero, for which $\lambda_{1} v_{1} + \ldots + \lambda_{n+1} v_{n+1} = (0, \ldots , 0)$ .
The analog of theorem $(\mathbb {Q})$ holds for the real numbers, the complex numbers, and the integers.

The tuples from Problems 7.1.1 $(\mathbb {Z}_{2})$ , $(\mathbb {Q})$ are called linearly dependent — over $\mathbb {Z}_{2}$ and over $\mathbb {Q}$ , respectively. Linear independence is the negation of linear dependence. Linear (in)dependence of polynomials over $\mathbb {Z}_{2}$ and $\mathbb {Q}$ , respectively, is defined similarly.

?

Remark.

?

Remark. Similar definitions can be given in a more general situation — this leads to the notions of a ring and of a module over it. An attempt to prove (and use!) an analog of the linear dependence theorem (Problems 7.1.1 $(\mathbb {Z}_{2})$ , $(\mathbb {Q})$ ) leads to the notions of a field and of a linear space over it. (In the case of the integers, not all generalizations go through anymore.) Details can be found in a textbook on linear algebra.

The phrase $N$ elements'' (in particular, subsets) means $N$ pairwise distinct elements'' (in particular, subsets).

Problem 7.1.2

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

A linear subspace is a subset $L \subset \mathbb {Q}^{n}$ closed under vector addition and multiplication by rational numbers. A linear subspace $L$ is called $n$ -dimensional if there exist linearly independent vectors $v_{1}, \ldots , v_{n} \in L$ such that every vector $v \in L$ is a linear combination of these vectors, i.e. there exist numbers $\lambda_{1}, \ldots , \lambda_{n} \in \mathbb {Q}$ for which $v = \lambda_{1} v_{1} + \ldots + \lambda_{n} v_{n}$ . The number $n$ is called the dimension of the space $L$ .

Let $\mathscr {F}$ be a family of subsets of the set $\mathscr {R}_{n}$ .

?

(1)

If every subset in $\mathscr {F}$ has an odd number of elements and the intersection of any two subsets in $\mathscr {F}$ has an even number of elements, then $\left|\mathscr {F}\right| \leq n$ .

(2)

Construct an example where this bound is attained.

(3)

If the intersection of any two subsets in $\mathscr {F}$ has exactly $q$ elements and every subset in $\mathscr {F}$ has more than $q$ elements, then $\left|\mathscr {F}\right| \leq n$ .

(4)

If $q > 0$ and the intersection of any two subsets in $\mathscr {F}$ has exactly $q$ elements, then $\left|\mathscr {F}\right| \leq n$ .

Problem 7.1.3

(1)(2)

?

(1)

There exist $2^{k}$ subsets of a $2k$ -element set such that each of them has an even number of elements and the intersection of any two of them has an even number of elements.

(2)

There cannot be more than $2^{k}$ subsets satisfying the conditions of part (1).

Problem 7.1.4

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

The distance between points of the space $\mathbb {R}^{n}$ is defined by the formula

\left|(x_{1}, \ldots , x_{n}), (y_{1}, \ldots , y_{n})\right| := \sqrt{(x_{1}-y_{1})^{2} + \ldots + (x_{n}-y_{n})^{2}}.

?

(1)

The largest number of points in $\mathbb {R}^{n}$ with equal pairwise distances is $n+1$ .

(2)

Construct $\dfrac {n(n-1)}{2}$ points in $\mathbb {R}^{n}$ whose pairwise distances take only two distinct values.

(3)

For $a \in \mathbb {R}$ and points $v = (v_{1}, \ldots , v_{n}) \in \mathbb {R}^{n}$ , $x = (x_{1}, \ldots , x_{n}) \in \mathbb {R}^{n}$ , denote $P_{v}(x) := \left|x-v\right|^{2} - a^{2}$ . If the pairwise distances between $k$ points $u_{1}, \ldots , u_{k} \in \mathbb {R}^{n}$ are equal to $a$ , then the polynomials $P_{u_{1}}, \ldots , P_{u_{k}}$ are linearly independent over $\mathbb {Q}$ .

(4)

If the pairwise distances between $k$ points in $\mathbb {R}^{n}$ take only two distinct values, then $k \leq \dfrac {(n+1)(n+4)}{2}$ .

Problem 7.1.5

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

For $n, k \in \mathbb {Z}$ , denote

V_{n,k} := \left\{ (x_{1}, \ldots , x_{n}) \in \left\{ 0,1\right\} ^{n} : \sum _{s} x_{s} = k\right\} .

?

(1)

Among any $327$ pairwise intersecting $9$ -element subsets of a $25$ -element set, there are two subsets whose intersection has exactly $3$ or exactly $6$ elements.

(2)

Among any $327$ points in $V_{25,9}$ , there are two whose scalar product lies in $\left\{ 0,3,6\right\}$ .

(3)

For any $\overrightarrow {a} \in V_{25,9}$ , expand the product

(\overrightarrow {a} \cdot (x_{1}, x_{2}, \ldots , x_{25}) - 1)(\overrightarrow {a} \cdot (x_{1}, x_{2}, \ldots , x_{25}) - 2),

where $x_{1}, x_{2}, \ldots , x_{25}$ are variables. In each of the resulting monomials, perform the following operation: for each $i$ , if the monomial contains the factor $x_{i}^{2}$ , replace this factor with $1$ . Denote the resulting polynomial by $F_{\overrightarrow {a}}(x_{1}, \ldots , x_{25})$ . Prove that if the scalar product of no two vectors among $\overrightarrow {a}_{1}, \ldots , \overrightarrow {a}_{s} \in V_{25,9}$ is divisible by $3$ , then the polynomials $F_{\overrightarrow {a}_{1}}, \ldots , F_{\overrightarrow {a}_{s}}$ are linearly independent over $\mathbb {Q}$ .

(4)

Specify $326$ polynomials whose linear combinations with rational coefficients yield every polynomial $F_{\overrightarrow {a}}$ , $\overrightarrow {a} \in V_{25,9}$ .

Problem 7.1.6

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

?

(1)

Among any $107$ five-element subsets of a $14$ -element set, there are two subsets whose intersection has exactly $2$ elements.

(2)

The same for $93$ subsets.

(3)

The same for $92$ subsets.

(4)

It is impossible to color all five-element subsets of a $14$ -element set with $21$ colors so that any two five-element subsets intersecting in exactly two elements have different colors.

Remark.

?

Cf.the remark in Problem 5.1.4. Here is an equivalent formulation. The vertices of the graph are all five-element subsets of a $14$ -element set. Its edges are the pairs of subsets intersecting in exactly two elements. Prove that this graph cannot be properly colored with $21$ colors.

Problem 7.1.7

(1)(2)(3)

?

(1)

For a prime $p$ and an integer $t$ , the number $G(t) := (t-1)(t-2)\ldots (t-p+1)$ is divisible by $p$ if and only if $t$ is not divisible by $p$ .

(2)

Let $p$ be a prime and $n = 4p$ . Denote

M = \left\{ (1, y_{2}, y_{3}, \ldots , y_{n}) : y_{k} \in \left\{ 1,-1\right\} \text{ and among } y_{2}, \ldots , y_{n} \text{ the number of minus ones is even}\right\} .

Denote $G(t) := (t-1)(t-2)\ldots (t-p+1)$ . For any $\overrightarrow {a} \in M$ , expand the brackets in the product $G(\overrightarrow {a} \cdot (1, x_{2}, \ldots , x_{n}))$ , where $x_{2}, \ldots , x_{n}$ are variables. In each of the resulting monomials, for each $i$ we replace $x_{i}^{2}$ by $1$ as long as possible. Denote the resulting polynomial by $F_{\overrightarrow {a}}(x_{2}, \ldots , x_{n})$ .

Prove that if no two vectors among $\overrightarrow {a}_{1}, \ldots , \overrightarrow {a}_{s} \in M$ have zero scalar product, then the polynomials $F_{\overrightarrow {a}_{1}}, \ldots , F_{\overrightarrow {a}_{s}}$ are linearly independent over $\mathbb {Q}$ .

(3)

There exist $n$ and a bounded subset of $\mathbb {R}^{n}$ that cannot be partitioned into $n+1$ nonempty parts of smaller diameter.

Problem 7.1.8

(1)(2)

?

(1)

If $t$ is prime, then among any $1 + \sum \limits_{j=0}^{t-1} \dbinom {n}{j}$ distinct subsets of an $n$ -element set, each of which has $k$ elements, there are two subsets whose intersection has a number of elements divisible by $t$ .

(2)

The same, except that an integer $q$ is given and is divisible by $t$'' is replaced by is congruent to $q$ modulo $t$ ''.

Problem 7.1.9

(1)(2)

?

(1)

If the edge set of the graph $K_{n}$ is the union of the edge sets of $s$ edge-disjoint complete bipartite graphs, then $s \geq n-1$ .

(2)

Construct a family of bipartite graphs for which this bound is attained.

Remark.

?

A more detailed and extended exposition can be found in [Mk, R1], and a more advanced one — in [BF].