Сколько различных пар непересекающихся подмножеств имеет множество, состоящее из $n$ элементов?
Подробнее
Множество X состоит из $n$ элементов. Для двух подмножеств $A_{1}, A_{2} \subset X$ сосчитано число элементов множества $A_{1} \bigcap A_{2}$. Доказать, что сумма всех полученных чисел равна $n \cdot 4^{n-1}$.
Подробнее
Про числа $n > 3, k = \left [ \frac{1}{6} n(n+1) \right ]$ и множество $X_{n}$, состоящее из $n(n + 1)/2$ элементов, известно, что $k$ элементов этого множества имеют синий цвет, $k$ элементов - красный цвет, а все остальные элементы - белый цвет. Доказать, что множество $X_{n}$ можно разбить на $n$ попарно непересекающихся подмножеств $A_{1}, \cdots, A_{n}$ так, чтобы для любого значения $m = 1, \cdots, n$ подмножество $A_{m}$ имело ровно $m$ элементов и причем одного цвета.
Подробнее
Для каждого значения $n \in \mathbf{N}$ найти наибольшее число $k \in \mathbf{N}$, обладающее следующим свойством: в множестве, состоящем из $n$ элементов, можно выбрать $k$ различных подмножеств, любые два из которых имеют непустое пересечение.
Подробнее
Пусть в конечном множестве X выбрано 50 подмножеств $A_{1}, \cdots, A_{50}$, каждое из которых содержит больше половины элементов множества X. Доказать, что можно найти подмножество $B \subset X$, содержащее не более 5 элементов и имеющее хотя бы один элемент, общий с каждым из множеств $A_{1}, \cdots, A_{50}$.
Подробнее
Дано 1978 множеств, каждое из которых имеет по 40 элементов. Известно, что любые два из этих множеств имеют ровно один общий элемент. Доказать, что существует элемент, принадлежащий всем 1978 множествам.
Подробнее
Множество из $2^{n}$ элементов разбито на попарно непересекающиеся подмножества. Рассматривается операция, состоящая в переводе некоторых элементов из одного подмножества в другое, причем число переводимых элементов должно совпадать с числом элементов во втором множестве (которое должно содержать элементов не больше, чем первое). Доказать, что с помощью конечного числа таких операций можно получить подмножество, совпадающее с исходным множеством.
Подробнее
Пусть M – подмножество множества всех пар натуральных чисел $i < k$, не превосходящих заданного натурального числа $n \geq 2$. При этом, если пара $i < k$ принадлежит множеству M, то никакая пара $k < m$ ему не принадлежит. Какое наибольшее число пар может быть в множестве М?
Подробнее
Множество X состоит из $n$ элементов. Какое наибольшее число трехэлементных подмножеств можно выбрать в X так, чтобы любые два из них имели ровно один общий элемент?
Подробнее
В множестве, состоящем из $n \geq 5$ элементов, выбрано $n + 1$ различных трехэлементных подмножеств. Доказать, что найдутся два выбранных подмножества, имеющих ровно один общий элемент.
Подробнее
Множество X разбито на попарно непересекающиеся подмножества $A_{1}, \cdots, A_{n}$, а также разбито на попарно непересекающиеся подмножества $B_{1}, \cdots, B_{n}$. Известно, что объединение $A_{i} \bigcup B_{j}$ любых непересекающихся подмножеств $A_{i}, B_{j}(1 \leq i \leq n, 1 \leq j \leq n$) содержит не менее $n$ элементов. Доказать, что число элементов множества X не меньше $n^{2}/2$. Может ли оно быть равным $n^{2}/2$?
Подробнее
В зале находится $n \geq 2$ человек.
Докажите, что в зале найдутся два человека, которые имеют
среди присутствующих одинаковое число знакомых (предполагаем, что, если $A$ — знакомый $B$, тогда $B$ — знакомый $A$; не считаем никого знакомым самому себе).
Подробнее
В Простоквашинской начальной школе учится 20 детей. У любых двух из них есть общий дед. Докажите, что у одного из дедов в этой школе учится не менее 14 внуков. (Замечание: любой ребёнок не может иметь более двух дедушек.)
Подробнее
Король решил устроить проверку своим ста мудрецам и сообщил, что на следующий день он выстроит всех с завязанными глазами в очередь и наденет каждому чёрный или белый колпак.
После того, как глаза будут развязаны, каждый, начиная с последнего в очереди, назовёт предполагаемый цвет своего колпака. Если он при этом не угадает, то будет казнён. У мудрецов ещё есть время договориться, как они будут действовать завтра. Скольким мудрецам наверняка удастся спастись?
Подробнее
В игре «Десант» две армии захватывают страну. Они ходят по очереди, каждым ходом занимая один из свободных городов. Первый свой город армия захватывает с воздуха, а каждым следующим ходом она может захватить любой город, соединённый дорогой с каким-нибудь уже занятым этой армией городом. Если таких городов нет, армия прекращает свои боевые действия (при этом, возможно, другая армия свои действия продолжает). Найдётся ли такая схема городов и дорог, что армия, ходящая второй, сможет захватить более половины всех городов, как бы ни действовала первая армия? (Число городов конечно, каждая дорога соединяет ровно два города.)
Подробнее