Республиканская олимпиада по математике, 2017 год, 11 класс

Рассмотрим всевозможные наборы натуральных чисел $(x_1,x_2, \ldots,x_{100})$ такие, что $1 \le x_i \le 2017$ для каждого $i =1, 2, \ldots, 100$. Будем говорить, что набор $(y_1,y_2, \ldots,y_{100})$ больше набора $(z_1,z_2, \ldots,z_{100})$, если $y_i > z_i$ для каждого $i =1, 2, \ldots, 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}}$. Но если взять все единичные наборы, то легко заметить что они удовлетворяют условию задачи.