Банк задач по математике

Задача 1.4.1

Расставьте на шахматной доске нескольких коней, чтобы каждый бил четырёх других.

?

Задача 1.4.2

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

33 буквы русского алфавита кодируются последовательностями из нулей и единиц.

?

(1)

При каком наименьшей длине последовательности кодирование можно сделать однозначным?

(2)

Если при получении сообщения возможна ошибка в не более чем одном разряде, т.е. если коды различных букв должны отличаться по крайней мере в трёх разрядах, то 8 разрядов не хватит.

(3)

Если возможна ошибка в не более чем двух разрядах, то 10 разрядов не хватит.

(4)

Найдите наименьшее число разрядов, достаточное для кодирования из п.(2).

Задача 1.4.3

(1)(2)

?

(1)

При фиксированном $n$ число $\binom {n}{k}$ максимально при $k = \left[\dfrac {n}{2}\right]$ .

(2)

Best in their own ways. В математической олимпиаде участвовало $k$ школьников. Выяснилось, что для любых двух школьников $A$ и $B$ нашлась задача, которую решил $A$ и не решил $B$ , и задача, которую решил $B$ , но не решил $A$ . Какое наименьшее возможное количество задач могло быть при этом условии? Иными словами, найдите наименьшее возможное $n$ , для которого найдётся такое семейство из $k$ подмножеств $n$ -элементного множества, что ни одно из подмножеств семейства не содержится (собственно) в другом.

Задача 1.4.4

Имеется табло с $n$ горящими лампочками. Каждый переключатель может быть подсоединён к некоторым лампочкам. При нажатии на кнопку переключателя соединённые с ним лампочки меняют свое состояние: горящие тухнут, а не горящие загораются. Какое наименьшее число переключателей необходимо, чтобы можно было зажечь любой набор лампочек (не входящие в этот набор лампочки гореть не должны)?

?

Задача 1.4.5

В первый день своего правления король организует партии среди $n$ своих подданных. На второй день советник приносит королю список фамилий некоторых подданных (в первый день этот список неизвестен). На третий день король может выбрать несколько партий и отправить в тюрьму всех подданных, участвующих в каждой из них. Какое наименьшее число партий необходимо организовать в первый день, чтобы в третий день заведомо можно было отправить в тюрьму всех подданных из принесенного списка (и только их)?

?

Примечание.

?

Следующая важная конструкция полезна (хотя и не обязательна) для решения вышеприведённых (и многих других) задач. Нарисуем точки, соответствующие всем подмножествам множества $\mathscr {R}_n$ . При этом на $k$ -й этаж поместим точки, соответствующие $k$ -элементным множествам. Соединим стрелкой те из них, которые получаются друг из друга добавлением одного элемента. Тогда соединяемые стрелкой точки лежат на соседних этажах. Полученный граф называется $n$ -мерным кубом. Его вершины соответствуют векторам из $\mathbb {Z}_2^n$ .

Определение множества $\mathbb {Z}_2^n$ приведено в начале п.7.1.

Подмножество $L\subset \mathbb {Z}_2^n$ называется линейным подпространством, если $x+y\in L$ для любых $x,y\in L$ (не обязательно различных). Иными словами, линейное подпространство — такое семейство подмножеств $n$ -элементного множества, которое вместе с любыми двумя подмножествами содержит их симметрическую разность (т.е. сумму по модулю 2).

Задача 1.4.6

(1)(2)

?

(1)

Любое линейное подпространство содержит нулевой набор $(0,\ldots ,0)$ .

(2)

Число элементов в любом линейном подпространстве является степенью двойки.

Обозначим через $\begin{vmatrix} n \\ k \end{vmatrix}$ количество линейных подпространств в $\mathbb {Z}_2^n$ , состоящих из $2^k$ элементов (такие линейные подпространства в $\mathbb {Z}_2^n$ называют $k$ -мерными).

Задача 1.4.7

?

(1)

Найдите $\begin{vmatrix} 2 \\ k \end{vmatrix}$ для $k=0,1,2$ .

(2)

Найдите $\begin{vmatrix} 3 \\ k \end{vmatrix}$ для $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)

Найдите $\begin{vmatrix} n \\ 2 \end{vmatrix}$ .

(7)

Найдите $\begin{vmatrix} n \\ k \end{vmatrix}$ .

Для решения этой задачи нужны некоторые понятия, приведённые в начале п.7.1.

Комбинаторика булева куба