Разделы 
Дополнительно
Задача по математике - 2845
2019-05-06 
а) Расположить числа от 1 до 100 таким образом, чтобы никакие 11 (не обязательно последовательных!) из этих чисел не следовали одно за другим в порядке возрастания или убывания.
б) Доказать, что в каком бы порядке ни расположить числа от 1 до 101, всегда из этих чисел можно выбрать 11 (не обязательно последовательных!) чисел, которые следуют одно за другим в порядке возрастания или убывания.
Решение:
а) Нетрудно видеть, что следующее расположение 100 первых целых чисел удовлетворяет условию задачи:
10 9 8 7 6 5 4 3 2 1 20 19 18 17 16 15 14 13 12 11
30 29 28 27 26 25 24 23 22 21 40 39 38 37 36 35 34 33 32 31
50 49 48 47 46 45 44 43 42 41 60 59 58 57 56 55 54 53 52 51
70 69 68 67 66 65 64 63 62 61 80 79 78 77 76 75 74 73 72 71
90 89 88 87 86 85 84 83 82 81 100 99 98 97 96 95 94 93 92 91.
б) Пусть $a_1^{(1)}$ есть первое (самое левое) из выписанных чисел: $a_2^{(1)}$ - первое из оставшихся, большее чем $a_1^{(1)}; a_3^{(1)}$ - первое из следующих за $a_2^{(1)}$ большее чем $a_2^{(1)}$ и т.д. Таким образом мы составим последовательность возрастающих чисел $a_1^{(1)}, a_2^{(1)}, a_3^{(1)}, \cdots, a_{i_1}^{(1)}$. Если в этой последовательности имеется больше 10 чисел (т. е. если $i_1 > 10$), то задача уже решена Если же $i_1 \leq 10$, то мы вычеркнем все эти числа и из оставшихся $101 - i_1$ чисел составим точно таким же образом новую последовательность $a_1^{(2)}, a_2^{(2)}, a_3^{(2)}, \cdots, a_{i_2}^{(2)}$, возрастающих чисел. Продолжая этот процесс, мы выделим из наших 101 чисел ряд возрастающих последовательностей. Если хотя бы одна из этих последовательностей содержит больше 10 чисел, то наша задача уже решена; таким образом, нам остается только рассмотреть случай, когда в каждой из выделенных последовательностей имеется не больше 10 чисел.
Так как у нас имеется всего 101 число, то в рассматриваемом случае общее число $k$ выделенных последовательностей возрастающих чисел не может быть меньше 11. В таком случае мы утверждаем, что в ряду из 101 числа можно выбрать 11 чисел, следующих один за другим в убывающем порядке. Эти числа мы будем выбирать с конца следующим образом. Последним из них будет последнее число $a_{i_k}^{(k)}$ последней из наших возрастающих последовательностей. Затем выберем число из предпоследней последовательности, расположенное слева от $a_{i_k}^{(k)}$ ближе всего к нему. Это число больше $a_{i_k}^{(k)}$ ибо в противном случае в процессе построения предпоследней последовательности мы бы выписали вслед за ним число $a_{i_k}^{(k)}$, в то время как на самом деле число $a_{i_k}^{(k)}$ попало в другую последовательность. Точно так же вслед за этим выписываем число из третьей от конца последовательности, расположенное слева от выбранного числа предпоследней последовательности, ближе всего к нему, и т. д. Таким образом мы построим последовательность чисел, которые идут возрастая, если их рассматривать в порядке справа налево, т. е. убывающую последовательность; число членов этой последовательности равно числу $k$ выбранных возрастающих последовательностей, т. е. не меньше 11.
Примечание. Совершенно аналогично можно доказать, что $(n-1)^2$ целых положительных чисел можно расположить так, что никакие $n$ из них не будут следовать одно за другим в порядке возрастания или убывания, но при любом расположении $k > (n-1)^2$ целых положительных чисел какие-то $n$ из этих чисел обязательно будут следовать одно за другим в порядке возрастания или убывания.
133. б) Постройте возрастающую последовательность, начиная с первого из выписанных 101 числа. Если в этой последовательности будет меньше 11 чисел, to вычеркните эти числа и построите, новую возрастающую последовательность, начинающуюся с первого оставшегося числа; если и в этой последовательности будет меньше 11 чисел, то вычеркните и ее и постройте новую возрастающую последовательность, и т. д. Если все построенные последовательности содержат меньше 11 чисел, то у нас будет не меньше 11 последовательностей; используя это обстоятельство, можно построить убывающую последовательность из 11 чисел.
а) Расположить числа от 1 до 100 таким образом, чтобы никакие 11 (не обязательно последовательных!) из этих чисел не следовали одно за другим в порядке возрастания или убывания.
б) Доказать, что в каком бы порядке ни расположить числа от 1 до 101, всегда из этих чисел можно выбрать 11 (не обязательно последовательных!) чисел, которые следуют одно за другим в порядке возрастания или убывания.
Решение:
а) Нетрудно видеть, что следующее расположение 100 первых целых чисел удовлетворяет условию задачи:
10 9 8 7 6 5 4 3 2 1 20 19 18 17 16 15 14 13 12 11
30 29 28 27 26 25 24 23 22 21 40 39 38 37 36 35 34 33 32 31
50 49 48 47 46 45 44 43 42 41 60 59 58 57 56 55 54 53 52 51
70 69 68 67 66 65 64 63 62 61 80 79 78 77 76 75 74 73 72 71
90 89 88 87 86 85 84 83 82 81 100 99 98 97 96 95 94 93 92 91.
б) Пусть $a_1^{(1)}$ есть первое (самое левое) из выписанных чисел: $a_2^{(1)}$ - первое из оставшихся, большее чем $a_1^{(1)}; a_3^{(1)}$ - первое из следующих за $a_2^{(1)}$ большее чем $a_2^{(1)}$ и т.д. Таким образом мы составим последовательность возрастающих чисел $a_1^{(1)}, a_2^{(1)}, a_3^{(1)}, \cdots, a_{i_1}^{(1)}$. Если в этой последовательности имеется больше 10 чисел (т. е. если $i_1 > 10$), то задача уже решена Если же $i_1 \leq 10$, то мы вычеркнем все эти числа и из оставшихся $101 - i_1$ чисел составим точно таким же образом новую последовательность $a_1^{(2)}, a_2^{(2)}, a_3^{(2)}, \cdots, a_{i_2}^{(2)}$, возрастающих чисел. Продолжая этот процесс, мы выделим из наших 101 чисел ряд возрастающих последовательностей. Если хотя бы одна из этих последовательностей содержит больше 10 чисел, то наша задача уже решена; таким образом, нам остается только рассмотреть случай, когда в каждой из выделенных последовательностей имеется не больше 10 чисел.
Так как у нас имеется всего 101 число, то в рассматриваемом случае общее число $k$ выделенных последовательностей возрастающих чисел не может быть меньше 11. В таком случае мы утверждаем, что в ряду из 101 числа можно выбрать 11 чисел, следующих один за другим в убывающем порядке. Эти числа мы будем выбирать с конца следующим образом. Последним из них будет последнее число $a_{i_k}^{(k)}$ последней из наших возрастающих последовательностей. Затем выберем число из предпоследней последовательности, расположенное слева от $a_{i_k}^{(k)}$ ближе всего к нему. Это число больше $a_{i_k}^{(k)}$ ибо в противном случае в процессе построения предпоследней последовательности мы бы выписали вслед за ним число $a_{i_k}^{(k)}$, в то время как на самом деле число $a_{i_k}^{(k)}$ попало в другую последовательность. Точно так же вслед за этим выписываем число из третьей от конца последовательности, расположенное слева от выбранного числа предпоследней последовательности, ближе всего к нему, и т. д. Таким образом мы построим последовательность чисел, которые идут возрастая, если их рассматривать в порядке справа налево, т. е. убывающую последовательность; число членов этой последовательности равно числу $k$ выбранных возрастающих последовательностей, т. е. не меньше 11.
Примечание. Совершенно аналогично можно доказать, что $(n-1)^2$ целых положительных чисел можно расположить так, что никакие $n$ из них не будут следовать одно за другим в порядке возрастания или убывания, но при любом расположении $k > (n-1)^2$ целых положительных чисел какие-то $n$ из этих чисел обязательно будут следовать одно за другим в порядке возрастания или убывания.
133. б) Постройте возрастающую последовательность, начиная с первого из выписанных 101 числа. Если в этой последовательности будет меньше 11 чисел, to вычеркните эти числа и построите, новую возрастающую последовательность, начинающуюся с первого оставшегося числа; если и в этой последовательности будет меньше 11 чисел, то вычеркните и ее и постройте новую возрастающую последовательность, и т. д. Если все построенные последовательности содержат меньше 11 чисел, то у нас будет не меньше 11 последовательностей; используя это обстоятельство, можно построить убывающую последовательность из 11 чисел.
