Loading [MathJax]/jax/output/SVG/jax.js

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


Определите наименьшее возможное значение |A1A2A3A4A5|, где A1,A2,A3,A4,A5 множества, одновременно удовлетоворяющие следующим условиям:
(i) |AiAj|=1 для всех 1i<j5, т.е. любые два различных множества содержат ровно один общий элемент;
(ii) AiAjAkAl= для всех 1i<j<k<l5, т.е. любые четыре различных множества не содержат общего элемента.
Здесь |S| означает количество элементов множества S.
посмотреть в олимпиаде

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

  2
4 года 1 месяца назад #

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

Например A1(1,2) A2(1,3,4) A3(1,5,6) A4(2,4,6) A5(2,3,5) тогда |A1A2A3A4A5|=(1,2,3,4,5,6)=6