Азия-тынық мұхит математикалық олимпиадасы, 2014 жыл
S={1, 2, …, 2014} болсын. S жиынының барлық бос емес T⊆S ішкі жиын үшін, оның өкілі ретінде бір элемент таңдап алынуы керек. S жиынының барлық бос емес ішкі жиындарының өкілін таңдап алудың және келесі шартты қанағаттандыратын барлық тәсілдерсанын анықта: егер қандай-да бір D⊆S ішкі жиыны, өзара қиылыспайтын бос емес A,B,C⊆S ішкі жиындарының бірігуі болса, онда D жиынының өкілі кемінде A, B, C жиындарының біреуінің өкілі болу керек.
(
Warut Suksompong
)
посмотреть в олимпиаде
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Ответ.108⋅2014!.
Решение. Для каждого подмножества X обозначим через r(X) представителя X. Положим x1=r(S). Сначала докажем следующий факт:
Заметим, что это утверждение верно и в случае, когда множество S содержит не менее 5 элементов.
Существует ровно 2014 способов выбрать x1=r(S) и для x1∈X⊆S имеем r(X)=x1. Пусть S1=S∖{x1}. Аналогично, мы можем утверждать, что существует ровно 2013 способов выбора x2=r(S1) и для x2∈X⊆S1 имеем r(X)=x2. Аналогично, продвигаясь дальше, существует ровно 2014⋅2013⋅⋯⋅5 способов выбора x1,x2,…,x2010∈S так, чтобы для всех i=1,2,…,2010, xi=r(X) для каждого X⊆S∖{x1,…,xi−1} и xi∈X.
У нас остается четырехэлементное множество Y={y1,y2,y3,y4}. Существует ровно 4 способа выбора r(Y). Пусть y1=r(Y). Тогда очевидно, что y1=r({y1,y2})=r({y1,y3})=r({y1,y4}). Только у подмножеств {y1,y2,y3}, {y1,y2,y4}, {y1,y3,y4}, {y2,y3,y4}, {y2,y3}, {y2,y4}, {y3,y4} еще не указаны представители. Их мы можем выбрать как угодно, что дает нам 34⋅23 способов.
Итак, общее число возможных назначений представителей равно 2014⋅2013⋅⋯⋅4⋅34⋅23=108⋅2014!.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.