Math Problems Vault

Problem 1.2.1

(1)(2)(3)

Denote by $\varphi (n)$ Euler's totient function, i.e. the number of integers from 1 to $n$ that are coprime to $n$ .

?

(1)

Find the number of integers not exceeding 1001 and not divisible by any of the numbers 7, 11, 13.

(2)

Find $\varphi (1), \varphi (p), \varphi (p^2), \varphi (p^\alpha )$ , where $p$ is a prime number and $\alpha > 2$ .

(3)

$\varphi (n) = n\left(1 - \dfrac {1}{p_1}\right)\ldots \left(1-\dfrac {1}{p_s}\right)$ , where $n = p_1^{\alpha_1}\cdot \ldots \cdot p_s^{\alpha_s}$ is the canonical prime factorization of $n$ .

Problem 1.2.2

(1)(2)

?

(1)

On the floor of a room of area $24\, \text{m}^2$ there are three carpets (of arbitrary shape), each of area $12\, \text{m}^2$ . Then the area of the intersection of some two carpets is at least $4\, \text{m}^2$ .

(2)

There are five patches (of arbitrary shape) on a caftan. The area of each of them is greater than half the area of the caftan. Then the area of the common part of some two patches is greater than one fifth of the area of the caftan.

Problem 1.2.3

(1)(2)(3)

Consider subsets $A_1,\ldots ,A_n$ of a finite set $U$ . By definition, put $\left|\bigcap_{j\in \varnothing }A_j\right| := U$ .

?

(1)

Suppose the number $\alpha_{|S|} := \left|\bigcap_{j\in S}A_j\right|$ depends only on the size $|S|$ of the index set $S \subset \mathscr {R}_n$ , and not on the set itself. Then

|A_1\cup \ldots \cup A_n| = \sum _{k=1}^{n}(-1)^{k+1}\binom {n}{k}\alpha _k,

|U\setminus (A_1\cup \ldots \cup A_n)| = \sum _{k=0}^{n}(-1)^k\binom {n}{k}\alpha _k.

(2)

Let $M_k := \displaystyle \sum_{S\in \binom {\mathscr {R}_n}{k}}\left|\bigcap_{j\in S}A_j\right|$ . In particular, $M_0 := |U|$ . Then

\begin{align} |A_1\cup \ldots \cup A_n| & = M_1 - M_2 + M_3 - \ldots + (-1)^{n+1}M_n, \\ |U\setminus (A_1\cup \ldots \cup A_n)| & = M_0 - M_1 + M_2 - \ldots + (-1)^n M_n. \end{align}

(3)

Bonferroni inequalities. For any $s$ , $s < \dfrac {n}{2}$ ,

\begin{align} M_1 - M_2 + M_3 - \ldots - M_{2s} & \leqslant |A_1\cup \ldots \cup A_n| \leqslant M_1 - M_2 + M_3 - \ldots + M_{2s+1}, \\ M_0 - M_1 + M_2 - \ldots + M_{2s} & \geqslant |U\setminus (A_1\cup \ldots \cup A_n)| \geqslant \\ & \geqslant M_0 - M_1 + M_2 - \ldots - M_{2s+1}. \end{align}

Remark.

?

This section offers problems of the following type: given a finite set $U$ and a collection of properties (subsets) $A_k \subset U$ , $k=1,\ldots ,n$ , it is required to find the number of elements that have at least one of the properties $A_k$ (i.e., $|A_1\cup \ldots \cup A_n|$ ), or the number of elements that have none of the properties $A_k$ (i.e., $|U\setminus (A_1\cup \ldots \cup A_n)|$ ).

For this purpose two versions of the inclusion--exclusion formula are used (see Problem 1.2.3(2)). Moreover, if in all intersections of sets of the collection the number of elements depends only on the number of sets being intersected, the formula can be simplified (see Problem 1.2.3(1)).

In Problems 1.2.4(1) and 1.2.5 it is assumed that the answer is written in the form of a sum (similar to the inclusion--exclusion formula).

Problem 1.2.4

(1)(2)

There are 10 distinct books on a shelf.

?

(1)

In how many ways can they be rearranged so that no book remains in its place?

(2)

The number of permutations of the books in which exactly 4 books remain in place is greater than 50000.

Problem 1.2.5

(1)(2)

?

(1)

In how many ways can 20 tourists be accommodated in 5 distinct cabins so that no cabin is empty?

(2)

How many distinct surjections $f: \mathscr {R}_k \to \mathscr {R}_n$ are there?

Problem 1.2.6

Prove the following formula:

\begin{align} n!\cdot x_1x_2\ldots x_n & = (x_1+x_2+\ldots +x_n)^n - \\ & \quad - \sum _{1\leqslant i_1 < i_2 < \ldots < i_{n-1}\leqslant n}(x_{i_1}+x_{i_2}+\ldots +x_{i_{n-1}})^n + \\ & \quad + \sum _{1\leqslant i_1 < i_2 < \ldots < i_{n-2}\leqslant n}(x_{i_1}+x_{i_2}+\ldots +x_{i_{n-2}})^n - \ldots \\ & \quad \ldots + (-1)^{n-1}\sum _{i=1}^{n}x_i^n. \end{align}

?