Магазин векторов

Natrix · Сообщение **Natrix** » 29 июн 2008, 11:42

B магазине продаются 2000 ненулевых пространственных векторов. Вася хочет купить три
некомпланарных вектора. Он поступает так: выбирает самый дешевый из них, потом самый дешевый
из неколлинеарных c первым, и, наконец, самый дешевый из некомпланарных c двумя первыми. Верно
ли, что Вася совершил самую выгодную покупку?

qwertylol · Сообщение **qwertylol** » 29 июн 2008, 12:12

Верно ли, что Вася совершил самую выгодную покупку?

Конечно нет! Bo-первых покупать векторы это уже совсем не выгодно... Bo-вторых возможно, что два остальных неколлинеарных окажутся очень дорогими. Если понять, как отличить дешёвый от дорогого, то можно показать на примере.

fynt · Сообщение **fynt** » 29 июн 2008, 15:39

Natrix писал(а):Source of the post
B магазине продаются 2000 ненулевых пространственных векторов. Вася хочет купить три
некомпланарных вектора. Он поступает так: выбирает самый дешевый из них, потом самый дешевый
из неколлинеарных c первым, и, наконец, самый дешевый из некомпланарных c двумя первыми. Верно
ли, что Вася совершил самую выгодную покупку?

Обозначим их $\vec{A},\ \ \vec{B},\ \ \vec{C}$

Три некомпланарных означает, что они не лежал в одной или параллельных плоскостях.
Вектор A - любой ибо он первый.
Вектор B - самый дешёвый который не должен быть параллелен вектору A или находитьс c нимна одной прямой.
Вектор C - тоже реально найти такой вектор который некомпланарен c A и C.

A что имеется ввид под словосочетанием "выгодная покупка"?

Natrix · Сообщение **Natrix** » 29 июн 2008, 15:41

fynt писал(а):Source of the post
Natrix писал(а):Source of the post
B магазине продаются 2000 ненулевых пространственных векторов. Вася хочет купить три
некомпланарных вектора. Он поступает так: выбирает самый дешевый из них, потом самый дешевый
из неколлинеарных c первым, и, наконец, самый дешевый из некомпланарных c двумя первыми. Верно
ли, что Вася совершил самую выгодную покупку?

Обозначим их $\vec{A},\ \ \vec{B},\ \ \vec{C}$

Три некомпланарных означает, что они не лежал в одной или параллельных плоскостях.
Вектор A - любой ибо он первый.
Вектор B - самый дешёвый который не должен быть параллелен вектору A или находитьс c нимна одной прямой.
Вектор C - тоже реально найти такой вектор который некомпланарен c A и C.

A что имеется ввид под словосочетанием "выгодная покупка"?

Видимо то, что любая другая тройка стоит дороже

fynt · Сообщение **fynt** » 29 июн 2008, 15:54

Тогда можно выбрать вектор A = C. При этом вектор A самый дешёвый.
И добавить вектр Б который будет удовлетворять условию.

По идее должно выйти дешевле...

venja · Сообщение **venja** » 29 июн 2008, 18:41

Думаю, что легко привести примеры векторов вместе c их стоимостью, когда данная стратегия приводит к оптимальному решению, a также пример, когда не приводит. Так что без большей конкретизации ответа нет.

AV_77 · Сообщение **AV_77** » 29 июн 2008, 19:14

Пусть $e_1,\ e_2,\ e_3$ - выбранные Васей векторы, то есть $$ e_1 $$

- самый дешевый, $$ e_2 $$

- самый дешевый из неколлинеарных c $$ e_1 $$

и

- самый дешевый из некомпланарных c $e_1,\ e_2$ . Обозначим через $$ S(x) $$

стоимость вектора $$ x $$

.

1) Пусть $a_1,\ a_2,\ a_3$ - набор базисных векторов минимальной стоимости $$ A $$

. Тогда существует набор базисных векторов, содержащий $$ e_1 $$

, который имеет стоимость $A' \leq A$ .
Действительно, вектор $$ e_1 $$

не лежит по крайней мере в одной из плоскостей $\langle a_1,\ a_3 \rangle$ , $\langle a_2,\ a_3 \rangle$ . Так как в противном случае мы получим $$ e_1 = x_1 a_1 + x_2 a_3 = y_1 a_2 + y_2 a_3 $$

. Это возможно только в двух случаях:
1) векторы $$ a_1, a_2, a_3 $$

, линейно зависимы, что невозможно, и
2) $e_1 = \alpha a_3$ .
Bo втором случае достаточно заменить вектор $$ a_3 $$

на

. При этом стоимость набора не увеличится.
Рассмотрим первый случай. Для определенности, пусть $$ e_1 $$

не лежит в плоскости $\langle a_2,\ a_3 \rangle$ . Ho тогда $e_1,\ a_2,\ a_3$ - базис, стоимость которого
$A' = S(e_1) + S(a_2) + S(a_3) \leq S(a_1) + S(a_2) + S(a_3) = A$ .

2) Пусть $e_1,\ a_2,\ a_3$ - набор базисных векторов минимальной стоимости $$ A $$

. Тогда существует набор базисных векторов, содержащий $e_1,\ e_2$ , который имеет стоимость $A' \leq A$ .
Действительно, вектор $$ e_2 $$

не лежит по крайней мере в одной из плоскостей $\langle e_1,\ a_2 \rangle$ , $\langle e_1,\ a_3 \rangle$ . Так как в противном случае мы получим $$ e_2 = x_1 e_1 + x_2 a_2 = y_1 e_1 + y_2 a_3 $$

. Как и выше, это возможно только в двух слйчаях:
1) векторы $$ e_1, a_2, a_3 $$

линейно зависимы, что невозможно, и
2) $e_2 = \alpha e_1$ .
Так как второй случай не возможен, то рассмотрим первый. Для определенности, пусть $$ e_2 $$

не лежит в плоскости $\langle e_1,\ a_3 \rangle$ . Ho тогда $e_1,\ e_2,\ a_3$ - базис, стоимость которого
$A' = S(e_1) + S(e_2) + S(a_3) \leq S(e_1) + S(a_2) + S(a_3) = A$ , так как, по выбору векторов $$ e_i $$

, $S(e_2) \leq S(a_2)$ .

Итак, выбранный набор должен содержать векторы $$ e_1 $$

и

. Ho тогда для минимизации стоимости необходимо для построения базиса в качестве третьего вектора взять вектор минимальной стоимости из некомпланарных c $$ e_1 $$

и

, то есть вектор $$ e_3 $$

.

Pavlovsky · Сообщение **Pavlovsky** » 05 авг 2008, 17:46

Рассмотрим систему множеств
1) всех одиночных векторов
2) всех пар неколлинеарных векторов
3) всех троек некомпланарных векторов

Эта система обладает свойствами:
1) для любого вектора всегда можно найти пару для образования неколлинеарных векторов
2) для любой пары неколлинеарных векторов всегда можно найти вектор для образования тройки некомпланарных векторов.

Значит эта система множеств является матроидом. Известно что на матроиде жадный алгоритм всегда дает оптимальное решение. Доказательство окончено!

venja · Сообщение **venja** » 05 авг 2008, 20:30

Pavlovsky писал(а):Source of the post
Значит эта система множеств является матроидом. Известно что на матроиде жадный алгоритм всегда дает оптимальное решение. Доказательство окончено!

:blink:

YURI · Сообщение **YURI** » 05 авг 2008, 22:36

По-моему искомый выбор векторов очевиден. Нужно придумать другое решение, более короткое, но доступное школьнику, как и предыдущее.

yourdomain.com