B магазине продаются 2000 ненулевых пространственных векторов. Вася хочет купить три
некомпланарных вектора. Он поступает так: выбирает самый дешевый из них, потом самый дешевый
из неколлинеарных c первым, и, наконец, самый дешевый из некомпланарных c двумя первыми. Верно
ли, что Вася совершил самую выгодную покупку?
Магазин векторов
Магазин векторов
Последний раз редактировалось Natrix 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Магазин векторов
Верно ли, что Вася совершил самую выгодную покупку?
Конечно нет! Bo-первых покупать векторы это уже совсем не выгодно... Bo-вторых возможно, что два остальных неколлинеарных окажутся очень дорогими. Если понять, как отличить дешёвый от дорогого, то можно показать на примере.
Последний раз редактировалось qwertylol 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Магазин векторов
Natrix писал(а):Source of the post
B магазине продаются 2000 ненулевых пространственных векторов. Вася хочет купить три
некомпланарных вектора. Он поступает так: выбирает самый дешевый из них, потом самый дешевый
из неколлинеарных c первым, и, наконец, самый дешевый из некомпланарных c двумя первыми. Верно
ли, что Вася совершил самую выгодную покупку?
Обозначим их
Три некомпланарных означает, что они не лежал в одной или параллельных плоскостях.
Вектор A - любой ибо он первый.
Вектор B - самый дешёвый который не должен быть параллелен вектору A или находитьс c нимна одной прямой.
Вектор C - тоже реально найти такой вектор который некомпланарен c A и C.
A что имеется ввид под словосочетанием "выгодная покупка"?
Последний раз редактировалось fynt 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Магазин векторов
fynt писал(а):Source of the postNatrix писал(а):Source of the post
B магазине продаются 2000 ненулевых пространственных векторов. Вася хочет купить три
некомпланарных вектора. Он поступает так: выбирает самый дешевый из них, потом самый дешевый
из неколлинеарных c первым, и, наконец, самый дешевый из некомпланарных c двумя первыми. Верно
ли, что Вася совершил самую выгодную покупку?
Обозначим их
Три некомпланарных означает, что они не лежал в одной или параллельных плоскостях.
Вектор A - любой ибо он первый.
Вектор B - самый дешёвый который не должен быть параллелен вектору A или находитьс c нимна одной прямой.
Вектор C - тоже реально найти такой вектор который некомпланарен c A и C.
A что имеется ввид под словосочетанием "выгодная покупка"?
Видимо то, что любая другая тройка стоит дороже
Последний раз редактировалось Natrix 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Магазин векторов
Тогда можно выбрать вектор A = C. При этом вектор A самый дешёвый.
И добавить вектр Б который будет удовлетворять условию.
По идее должно выйти дешевле...
И добавить вектр Б который будет удовлетворять условию.
По идее должно выйти дешевле...
Последний раз редактировалось fynt 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Магазин векторов
Думаю, что легко привести примеры векторов вместе c их стоимостью, когда данная стратегия приводит к оптимальному решению, a также пример, когда не приводит. Так что без большей конкретизации ответа нет.
Последний раз редактировалось venja 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Магазин векторов
Пусть - выбранные Васей векторы, то есть - самый дешевый, - самый дешевый из неколлинеарных c и - самый дешевый из некомпланарных c . Обозначим через стоимость вектора .
1) Пусть - набор базисных векторов минимальной стоимости . Тогда существует набор базисных векторов, содержащий , который имеет стоимость .
Действительно, вектор не лежит по крайней мере в одной из плоскостей , . Так как в противном случае мы получим . Это возможно только в двух случаях:
1) векторы , линейно зависимы, что невозможно, и
2) .
Bo втором случае достаточно заменить вектор на . При этом стоимость набора не увеличится.
Рассмотрим первый случай. Для определенности, пусть не лежит в плоскости . Ho тогда - базис, стоимость которого
.
2) Пусть - набор базисных векторов минимальной стоимости . Тогда существует набор базисных векторов, содержащий , который имеет стоимость .
Действительно, вектор не лежит по крайней мере в одной из плоскостей , . Так как в противном случае мы получим . Как и выше, это возможно только в двух слйчаях:
1) векторы линейно зависимы, что невозможно, и
2) .
Так как второй случай не возможен, то рассмотрим первый. Для определенности, пусть не лежит в плоскости . Ho тогда - базис, стоимость которого
, так как, по выбору векторов , .
Итак, выбранный набор должен содержать векторы и . Ho тогда для минимизации стоимости необходимо для построения базиса в качестве третьего вектора взять вектор минимальной стоимости из некомпланарных c и , то есть вектор .
1) Пусть - набор базисных векторов минимальной стоимости . Тогда существует набор базисных векторов, содержащий , который имеет стоимость .
Действительно, вектор не лежит по крайней мере в одной из плоскостей , . Так как в противном случае мы получим . Это возможно только в двух случаях:
1) векторы , линейно зависимы, что невозможно, и
2) .
Bo втором случае достаточно заменить вектор на . При этом стоимость набора не увеличится.
Рассмотрим первый случай. Для определенности, пусть не лежит в плоскости . Ho тогда - базис, стоимость которого
.
2) Пусть - набор базисных векторов минимальной стоимости . Тогда существует набор базисных векторов, содержащий , который имеет стоимость .
Действительно, вектор не лежит по крайней мере в одной из плоскостей , . Так как в противном случае мы получим . Как и выше, это возможно только в двух слйчаях:
1) векторы линейно зависимы, что невозможно, и
2) .
Так как второй случай не возможен, то рассмотрим первый. Для определенности, пусть не лежит в плоскости . Ho тогда - базис, стоимость которого
, так как, по выбору векторов , .
Итак, выбранный набор должен содержать векторы и . Ho тогда для минимизации стоимости необходимо для построения базиса в качестве третьего вектора взять вектор минимальной стоимости из некомпланарных c и , то есть вектор .
Последний раз редактировалось AV_77 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Магазин векторов
Рассмотрим систему множеств
1) всех одиночных векторов
2) всех пар неколлинеарных векторов
3) всех троек некомпланарных векторов
Эта система обладает свойствами:
1) для любого вектора всегда можно найти пару для образования неколлинеарных векторов
2) для любой пары неколлинеарных векторов всегда можно найти вектор для образования тройки некомпланарных векторов.
Значит эта система множеств является матроидом. Известно что на матроиде жадный алгоритм всегда дает оптимальное решение. Доказательство окончено!
1) всех одиночных векторов
2) всех пар неколлинеарных векторов
3) всех троек некомпланарных векторов
Эта система обладает свойствами:
1) для любого вектора всегда можно найти пару для образования неколлинеарных векторов
2) для любой пары неколлинеарных векторов всегда можно найти вектор для образования тройки некомпланарных векторов.
Значит эта система множеств является матроидом. Известно что на матроиде жадный алгоритм всегда дает оптимальное решение. Доказательство окончено!
Последний раз редактировалось Pavlovsky 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Магазин векторов
Pavlovsky писал(а):Source of the post
Значит эта система множеств является матроидом. Известно что на матроиде жадный алгоритм всегда дает оптимальное решение. Доказательство окончено!
:blink:
Последний раз редактировалось venja 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Магазин векторов
По-моему искомый выбор векторов очевиден. Нужно придумать другое решение, более короткое, но доступное школьнику, как и предыдущее.
Последний раз редактировалось YURI 30 ноя 2019, 12:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Алгебра и теория чисел»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 0 гостей