Правильно ли мое доказательство?

[TOTAL]

Xaositect в сообщении #323397 писал(а):

TOTAL в сообщении #323396 писал(а):

Почему не можем?

Потому что он должен идти на выход алгоритма.

Что ему мешает туда идти?

[Xaositect]

TOTAL в сообщении #323399 писал(а):

Что ему мешает туда идти?

Мы его выкинули -> его у нас нет, значит и на выход мы его подать не можем.

[TOTAL]

Xaositect в сообщении #323400 писал(а):

TOTAL в сообщении #323399 писал(а):

Что ему мешает туда идти?

Мы его выкинули -> его у нас нет, значит и на выход мы его подать не можем.

Весь набор $1,2,3,4,5$
Прочитано $1,2,3$
Выбрасываем $3$
После дочитывания получаем $1,2,4,5$
Медиана получившегося набора равна выкинутому элементу.
Медиана полного набора точно такая же. Какие проблемы?

[GrishinUS]

Цитата:

ИМХО, надо написать, что минимальный элемент выкинуть не можем, т.к. если все послеующие меньше и их $n-1$, то он будет медианой и его потребуется подать на выход алгоритма.

а если так:
прочитали 0, 1 , 2
$2$ выкинули,
потом дали на вход $1, 1, 1, 1$
Ваше условие выполняется, но $2$ медианой не является.

[Xaositect]

TOTAL в сообщении #323402 писал(а):

Медиана полного набора точно такая же. Какие проблемы?

Ну хорошо, надо сказать, что существует набор $x_{n+1},\dots,x_{n+m}$ такой, что медиана равна $x_i$, а значение $f(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{n+m})$, где $f$ - это функция, которую вычисляет алгоритм после выбрасывания $x_i$, не равно $x_i$. Если эта функция - не константа по $x_{n+1},\dots,x_{n+m}$, то такое значение существует, если же константа, то она не может вычислять медиану.

Вообще если лезть в детали, то надо уже формально объявлять модель вычислений
Если хотите, рассмотрим формально такую модель: Программа - последовательность операторов следующего вида:
1. $\mathrm{return}(y)$ - завершить работу и выдать значение $x$ на выход
2. $\mathrm{new}(y)$, $\mathrm{discard}(y)$ - создать новую переменную и выбросить ее соответственно. После выбрасывания переменной ее использование запрещено.
3. $y \leftarrow f(z_1,\dots,z_k)$, где $f$ - вычислимая функция, - присваивание
4. $\mathrm{if}\ p(z_1,\dots z_k)\ \mathrm{then}\ A\ \mathrm{else}\ B$, где $p(z_1,\dots z_k)$ - вычислимый предикат, а $A$ и $B$ - программы, - ветвление.

Вначале у нас есть набор переменных $x_1,\dots,x_k,\dots$, в первых $n+m$ находятся элементы коллекции, начиная с $n+m+1$ находится специальное значение $\sharp$. Все значения, кроме $\sharp$ - целые числа, для простоты.

Это, конечно, не C++, но сформулировать и доказать утверждение, соответствующее задаче, в этой модели можно.