X математическая олимпиада «Шелковый путь», 2011 год


Определите наименьшее возможное значение $|A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5|$, где $A_1, A_2, A_3, A_4, A_5$ множества, одновременно удовлетоворяющие следующим условиям:
(i) $|A_i \cap A_j|= 1$ для всех $1 \le i < j \le 5$, т.е. любые два различных множества содержат ровно один общий элемент;
(ii) $A_i \cap A_j \cap A_k \cap A_l = \emptyset$ для всех $1 \le i < j < k < l \le 5$, т.е. любые четыре различных множества не содержат общего элемента.
Здесь $|S|$ означает количество элементов множества $S$.
посмотреть в олимпиаде

Комментарий/решение:

  2
2021-03-18 03:22:56.0 #

Множество не может состоять из одного элемента, так как в таком случае будет выполнятся всегда $(ii)$ условие, два каких то множества всегда будут иметь как минимум по $3$ элемента, так как иначе найдутся два множества у которых общий элемент больше $1$, пусть это будут множества $A_{1},A_{2}$ тогда в них как минимум $5$ разных элемента, но тогда $A_{3}$ добавить как минимум $1$ элемент по условию $(i)$ но тогда всего различных элементов как минимум $5+1=6$ значит наименьшее $6$.

Например $A_{1}(1,2)\ A_{2}(1,3,4) \ A_{3}(1,5,6) \ A_{4}(2,4,6) \ A_{5}(2,3,5)$ тогда $|A_{1} \cup A_{2} \cup A_{3} \cup A_{4} \cup A_{5} | =(1,2,3,4,5,6)=6$