Информация о задаче

Задача 78019

Темы:	[	Принцип крайнего (прочее)	]
	[	Обратный ход	]
	[	Последовательности	]

Сложность: 4
Классы: 8,9,10

Прислать комментарий

Условие

Если дан ряд из 15 чисел

a₁, a₂,..., a₁₅, (1)

то можно написать второй ряд

b₁, b₂,..., b₁₅, (2)

где b_i(i = 1, 2, 3,..., 15) равно числу чисел ряда (1), меньших a_i. Существует ли ряд чисел a_i, если дан ряд чисел b_i:

1, 0, 3, 6, 9, 4, 7, 2, 5, 8, 8, 5, 10, 13, 13?

Решение

Ответ: нет, не существует. Предположим, что требуемый ряд чисел a_i существует. При перестановке чисел a_i числа b_i переставляются точно так же. Кроме того, если числа a_i расположены в порядке возрастания, то числа b_i тоже расположены в порядке возрастания. Пусть $\alpha_{1}^{}$ , ..., $\alpha_{15}^{}$ — это числа a₁, ..., a₁₅, расположенные в порядке возрастания, а $\beta_{1}^{}$ , ..., $\beta_{15}^{}$ -- числа b₁, ..., b₁₅, расположенные в порядке возрастания, т.е. $\beta_{1}^{}$ , ..., $\beta_{15}^{}$ — это последовательность

0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 10, 13, 13.

Из того, что $\beta_{1}^{}$ = 0, $\beta_{2}^{}$ = 1, $\beta_{3}^{}$ = 2, $\beta_{4}^{}$ = 3, $\beta_{5}^{}$ = 4, $\beta_{6}^{}$ = 5 и $\beta_{7}^{}$ = 5, следует, что $\alpha_{1}^{}$ < $\alpha_{2}^{}$ < $\alpha_{3}^{}$ < $\alpha_{4}^{}$ < $\alpha_{5}^{}$ < $\alpha_{6}^{}$ = $\alpha_{7}^{}$ . В таком случае если $\alpha_{7}^{}$ = $\alpha_{8}^{}$ , то $\beta_{8}^{}$ = 5, а если $\alpha_{7}^{}$ < $\alpha_{8}^{}$ , то $\beta_{8}^{}$ = 7. А у нас $\beta_{8}^{}$ = 6. Приходим к противоречию.

Источники и прецеденты использования


олимпиада
Название	Московская математическая олимпиада
год
Номер	17
Год	1954
вариант
Класс	9
Тур	2
задача
Номер	4