Математикадан республикалық олимпиада, 2016-2017 оқу жылы, 11 сынып

Әр $i =1, 2, \ldots, 100$ үшін $1 \le x_i \le 2017$ теңсіздігі орындалатын $(x_1,x_2, \ldots,x_{100})$ барлық мүмкін натурал сандар жиынтықтарын қарастырайық. Егер барлық $i =1, 2, \ldots, 100$ үшін $y_i > z_i$ болса, онда $(y_1,y_2, \ldots,y_{100})$ жиынтығын $(z_1,z_2, \ldots,z_{100})$ жиынтығынан үлкен деп айтамыз. Ешқандай жиынтық басқа ешқандай жиынтықтан үлкен болмайтындай, тақтаға ең көп дегенде қанша жиынтықтарды жазып шығуға болады? ( Ильясов С., Аманкельды А. )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. ${{2017}^{100}}-{{2016}^{100}}$.
Решение. Назовем набор $\left( {{x}_{1}},{{x}_{2}},\ldots ,{{x}_{100}} \right)$ — единичным, если ${{x}_{i}}=1$ для какого-то $i=1,2,\ldots ,100.$ Заметим, что количество всевозможных наборов равна ${{2017}^{100}}$, а количество наборов в котором ${{x}_{i}} > 1$ для каждого $i=1,2,\ldots ,100$ равна ${{2016}^{100}}$. Тогда количество единичных наборов равна $s={{2017}^{100}}-{{2016}^{100}}$. Разобьем все единичные наборы на $s$ групп, по одному набору в каждом. Рассмотрим какой-то единичный набор $\left( {{x}_{1}},{{x}_{2}},\ldots ,{{x}_{100}} \right)$. Пусть $M=\max\left( {{x}_{1}},{{x}_{2}},\ldots ,{{x}_{100}} \right)$. Для каждого $i=1,2,\ldots ,2017-M$ добавим в эту группу набор $\left( {{x}_{1}}+i,{{x}_{2}}+i,\ldots ,{{x}_{100}}+i \right)$. Для каждой группы проделаем такую операцию. Докажем, что любой набор находится в какой-то группе. Действительно, пусть $\left( {{x}_{1}},{{x}_{2}},\ldots ,{{x}_{100}} \right)$ произвольный набор и $m=\min \left( {{x}_{1}},{{x}_{2}},\ldots ,{{x}_{100}} \right)$. Тогда она была получена из единичного набора $\left( {{x}_{1}}-m+1,{{x}_{2}}-m+1,\ldots ,{{x}_{100}}-m+1 \right)$ прибавлением $m-1$. Так как из каждой группы мы можем взять не более одного набора(по построению, внутри одной группы каждый следующий набор больше предыдущей), тогда количество наборов удовлетворяющих условию задачи не более чем количество групп, то есть не более ${{2017}^{100}}-{{2016}^{100}}$. Но если взять все единичные наборы, то легко заметить что они удовлетворяют условию задачи.