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

[GrishinUS]

Цитата:

Suppose we wish to find the median of a collection of values. Assume that we have read some of the values so far, and that we have no idea how many values remain to be read. Prove that we cannot afford to discard any of the values that we have read. Hint: One proof strategy is to assume that we can discard a value, and then find values for the unread—and therefore unknown—part of our collection that would cause the median to be the value that we discarded.

Мое док-во:
Допустим, мы считали величины $1, 1 $и $3$. Величиниу $3$ не стали добавлять в коллекцию, т.о. в коллекции сейчас $1$ и $1$.
Дальше мы считали 4 и 5, на этом ввод закончен, добавили их в коллекцию.
Всего в коллекции $4, 1, 1, 5$ в произвольном порядке.
После сортировки $1, 1, 4, 5$ именно в таком порядке.
Медианное значение $(1 + 4)/2 = 2.5$ что не соответствует действительности потому как медианное значение для коллекции $3,1,1,4,5$ ($1,1,3,4,5$ упорядоченная коолекция) равно $3$.

И еще нескромный вопрос:
по каким признакам можно определить верность (достаточность) того или иного док-ва?

[Xaositect]

Вы дали доказательство того, что если при нахождении медианы однопроходным алгоритмом мы в начале считали 1, 1, 3, то мы не можем выкинуть из памяти значение 3.
А надо доказать, что из любого набора нельзя выкинуть ни одно значение

Т.е. у Вас не доказательство не для общего случая, а для одного примера.

[GrishinUS]

Допустим, мы считали значения $x1, x2, x3, ..., xn$ в коллекцию.
Отбросили xn.
Дальше считываются значения $x(n+1), x(n+2), x(n+3), ..., x(n+m)$.
Всего элементов в коллекции $K=n+m-1.$
Упорядочиваем коллекцию по неубыванию.
При этом, значение медианы в неполной коллекции:
1) равна $x(K/2)$ если количество элементов в коллекции нечетно
2) равна $[x(K/2) + x(1+K/2)]/2$

Количество элементов полной коллекции $M=n+m$
В то же время, медиана полной коллекции:
3) равна $x(M/2)$ если количество элементов в коллекции нечетно
4) равна $[x(M/2) + x(1+M/2)]/2$

в общем случае,
$x([n+m-1]/2) != x([n+m]/2) [x([n+m-1]/2) + x([1+(n+m-1)/2])]/2 != [x([n+m]/2) + x([1+(n+m)/2])]/2$

[Xaositect]

По-моему, Вы не понимаете.
То, что медиана укороченной последовательности отличается от медианы полной, Вы доказали. Но это не доказывает того, что мы, убрав один элемент, не можем вычислить медиану исходной последовательности, не зная этого элемента: ведь от оставшихся элементов мы можем вычислять не только медиану - вдруг какая-то другая комбинация подойдет.

Вам нужно доказать, что в некоторых случаях медиана последовательности зависит от заданного элемента (а точнее равна ему), когда другие не меняются:

Цитата:

One proof strategy is to assume that we can discard a value, and then find values for the unread—and therefore unknown—part of our collection that would cause the median to be the value that we discarded.

[GrishinUS]

Каким образом медиана последовательности из которой удален элемент может указывать на этот удаленный элемент? Мне кроме сравнения медианы укороченной последовательности и полной последовательности ничего не пришло в голову.
И еще мне недоступен смысл, который Вы вложили во фразу:

Цитата:

когда другие не меняются

какая разница меняются другие или нет?

[TOTAL]

Непрочитанные числа больше прочитанных, их больше, они различны и составляют арифметическую прогрессию. (Правда, я не знаю, что такое медиана.)

[GrishinUS]

Цитата:

Непрочитанные числа больше прочитанных, их больше, они различны и составляют арифметическую прогрессию.

такого условия в задаче нет, непрочитанные числа могут быть и меньше.
Медиана -- это серединный элемент упорядоченной последовательности если в посл-ти нечетное кол-во элементов, или среднее арифметическое двух серединных элементов если кол-во эл-тов посл-ти четное.

[TOTAL]

GrishinUS в сообщении #321773 писал(а):

Цитата:

Непрочитанные числа больше прочитанных, их больше, они различны и составляют арифметическую прогрессию.

такого условия в задаче нет, непрочитанные числа могут быть и меньше.

Значит, Вы не понимаете, что надо доказать. Не могли бы Вы своими словами пересказать услоие задачи?

[Xaositect]

GrishinUS в сообщении #321761 писал(а):

Каким образом медиана последовательности из которой удален элемент может указывать на этот удаленный элемент? Мне кроме сравнения медианы укороченной последовательности и полной последовательности ничего не пришло в голову.
И еще мне недоступен смысл, который Вы вложили во фразу:

Цитата:

когда другие не меняются

какая разница меняются другие или нет?

То, что медиана не может указывать, Вы доказали. Вопрос в том, а не может ли указывать какая-то другая фукция от маленькой последовательности.

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

А в задаче нахождения медианы так сделать нельзя, потому что для любого $i$ существуют такие переменные $x_{n+1},\dots,x_{n+m}$, что медиана равна именно $x_i$, поэтому медиану нельзя разделить на часть, зависящую только от $x_1,\dots,x_n$ и остальную, а значит, и выкинуть ни одну из $x_1,\dots,x_n$.

[GrishinUS]

Цитата:

Значит, Вы не понимаете, что надо доказать. Не могли бы Вы своими словами пересказать услоие задачи?

Нужно доказать что нельзя отбросить некоторый элемент $xi$ из уже считанной последовательности, если ничего неизвестно о том сколько осталось считать и какие элементы остались, т.к. может получиться так, что медиана итоговой последовательности указывает на отброшенный элемент.

[ИСН]

Ну дак и докажите. "Допустим, элемент был вот такой - третий в пятом ряду, волосы голубые, глаза рыжие. Мы его выкинули. Теперь представьте, что остальные элементы подобрались такие, что как раз его-то и не хватает."

[TOTAL]

GrishinUS в сообщении #321847 писал(а):

Нужно доказать что нельзя отбросить некоторый элемент $xi$ из уже считанной последовательности, если ничего неизвестно о том сколько осталось считать и какие элементы остались, т.к. может получиться так, что медиана итоговой последовательности указывает на отброшенный элемент.

Сформулируйте условие, что требуется доказать! (А про намёки, типа что там может получиться, ничего не добавляйте.)

[GrishinUS]

Цитата:

Ну дак и докажите. "Допустим, элемент был вот такой - третий в пятом ряду, волосы голубые, глаза рыжие. Мы его выкинули. Теперь представьте, что остальные элементы подобрались такие, что как раз его-то и не хватает."

Допустим, был элемент $xi$, мы его выкинули. Теперь представьте, что остальные элементы подобрались такие, что медиана указывает как раз на $xi$, т.е. для гарантированного нахождения медианы его выкидывать нельзя.
Но это ж очевидно и, в общем-то, следует из условия!

Цитата:

Сформулируйте условие, что требуется доказать! (А про намёки, типа что там может получиться, ничего не добавляйте.)

Требуется доказать то, что медиана -- функция зависящая от всех элементов посл-ти(?)

И всет-таки, я никак не могу понять что от меня хотят. С одной стороны все и так ясно, а с другой это нужно как-то показать на бумаге. Где критерий достаточности док-ва?

[GrishinUS]

Не сочтите за наглость, но хотелось бы получить ответы на свои вопросы (это в пятницу-то вечером!).
Делаю для себя, так что разобраться хотелось бы.

[Xaositect]

Я, возможно, придираюсь на самом деле и Вам все нужно более просто, но дело в том, что как раз в таких базовых вещах часто находятся хитрые заковыки :)

По сути, Вам нужно доказать, что ни один алгоритм, который, считав начальный отрезок $x_1,\dots,x_n$, после этого никак не использует $x_i$ независимо от значений $x_{n+1},\dots,x_{n+m}$, не может вычислять медиану.

А задача доказательства того, что ни один алгоритм не обладает каким-то свойством, достаточно сложная. Тут нельзя отговориться тем, что "очевидно, если мы выкинем $x_i$, то медиана изменится" - а вдруг существует какой-то хитрый алгоритм, который делает все неочевидным образом и в результате получается то, что надо (про быстрое умножение слышали?).