Math Problems Vault

Problem 1.4.1

Place several knights on a chessboard so that each of them attacks four others.

?

Problem 1.4.2

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

The 33 letters of the Russian alphabet are encoded by sequences of zeros and ones.

?

(1)

What is the least sequence length for which the encoding can be made unambiguous?

(2)

If an error in at most one digit is possible when a message is received, i.e., if the codes of different letters must differ in at least three digits, then 8 digits are not enough.

(3)

If an error in at most two digits is possible, then 10 digits are not enough.

(4)

Find the least number of digits sufficient for the encoding from part (2).

Problem 1.4.3

(1)(2)

?

(1)

For fixed $n$ , the number $\binom {n}{k}$ is maximal at $k = \left[\dfrac {n}{2}\right]$ .

(2)

Best in their own ways. $k$ schoolchildren took part in a mathematical olympiad. It turned out that for any two schoolchildren $A$ and $B$ there was a problem that $A$ solved and $B$ did not solve, and a problem that $B$ solved but $A$ did not solve. What is the least possible number of problems under this condition? In other words, find the least possible $n$ for which there exists a family of $k$ subsets of an $n$ -element set such that no subset of the family is (properly) contained in another.

Problem 1.4.4

There is a board with $n$ lit bulbs. Each switch can be connected to some of the bulbs. When the button of a switch is pressed, the bulbs connected to it change their state: lit bulbs go out and unlit ones light up. What is the least number of switches needed so that any set of bulbs can be lit (the bulbs not in this set must not be lit)?

?

Problem 1.4.5

On the first day of his reign, a king organizes parties among his $n$ subjects. On the second day, an adviser brings the king a list of surnames of some of the subjects (on the first day this list is unknown). On the third day, the king may choose several parties and send to prison all the subjects who are members of each of them. What is the least number of parties that must be organized on the first day so that on the third day it is certainly possible to send to prison all the subjects from the list brought by the adviser (and only them)?

?

Remark.

?

The following important construction is useful (though not necessary) for solving the problems above (and many others). Draw points corresponding to all subsets of the set $\mathscr {R}_n$ . Place the points corresponding to $k$ -element sets on the $k$ -th level. Join by an arrow those of them that are obtained from each other by adding one element. Then points joined by an arrow lie on adjacent levels. The resulting graph is called the $n$ -dimensional cube. Its vertices correspond to vectors from $\mathbb {Z}_2^n$ .

The definition of the set $\mathbb {Z}_2^n$ is given at the beginning of Sec.7.1.

A subset $L\subset \mathbb {Z}_2^n$ is called a linear subspace if $x+y\in L$ for any $x,y\in L$ (not necessarily distinct). In other words, a linear subspace is a family of subsets of an $n$ -element set which, together with any two subsets, contains their symmetric difference (i.e., their sum modulo 2).

Problem 1.4.6

(1)(2)

?

(1)

Every linear subspace contains the zero vector $(0,\ldots ,0)$ .

(2)

The number of elements in any linear subspace is a power of two.

Denote by $\begin{vmatrix} n \\ k \end{vmatrix}$ the number of linear subspaces of $\mathbb {Z}_2^n$ consisting of $2^k$ elements (such linear subspaces of $\mathbb {Z}_2^n$ are called $k$ -dimensional).

Problem 1.4.7

?

(1)

Find $\begin{vmatrix} 2 \\ k \end{vmatrix}$ for $k=0,1,2$ .

(2)

Find $\begin{vmatrix} 3 \\ k \end{vmatrix}$ for $k=0,1,2,3$ .

(3)

$\begin{vmatrix} n \\ 0 \end{vmatrix} = \begin{vmatrix} n \\ n \end{vmatrix} = 1$ , $\begin{vmatrix} n \\ 1 \end{vmatrix} = \begin{vmatrix} n \\ n-1 \end{vmatrix} = 2^n-1$ .

(4)

$\begin{vmatrix} n \\ k \end{vmatrix} = \begin{vmatrix} n \\ n-k \end{vmatrix}$ .

(5)

$\begin{vmatrix} n+1 \\ k+1 \end{vmatrix} = \begin{vmatrix} n \\ k+1 \end{vmatrix} + 2^{n-k}\begin{vmatrix} n \\ k \end{vmatrix}$ .

(6)

Find $\begin{vmatrix} n \\ 2 \end{vmatrix}$ .

(7)

Find $\begin{vmatrix} n \\ k \end{vmatrix}$ .

Solving this problem requires some notions introduced at the beginning of Sec.7.1.