Условие
На плоскости даны точки A = (1, 2), B = (5, 2), C = (1, 4), D = (5, 4).
а) Запишите E = (1, 3) как выпуклую линейную комбинацию точек A, B, C и D.
б) Запишите F = (3, 3) как выпуклую линейную комбинацию точек A, B, C и D всеми возможными способами.
в) Можно ли записать G = (6, 3) как выпуклую линейную комбинацию точек A, B, C и D?
г) Сколькими способами можно записать H = (4, 3) как выпуклую линейную комбинацию A, B, C и D?
д) Сколькими способами можно записать I = (4, 3) как выпуклую линейную комбинацию A, B и D?
е) Сколькими способами можно записать J = (4, 2) как выпуклую линейную комбинацию A, B, C и D?
ж) Сколькими способами можно записать K = (4, 2) как выпуклую линейную комбинацию A, C и D?
Напомним: выпуклая комбинация — это w1P1 + … + wkPk, где все веса wi ≥ 0 и w1 + … + wk = 1.
Решение источника
а) E = 0,5A + 0·B + 0,5C + 0·D.
б) Например, F = 0,5B + 0,5C = 0,5A + 0,5D = 0,25A + 0,25B + 0,25C + 0,25D. Чтобы найти все способы, решается система αA + βB + γC + δD = F, α + β + γ + δ = 1. После приведения: β + δ = 1/2, γ + δ = 1/2, α − δ = 0. Все способы: F = αA + (0,5 − α)B + (0,5 − α)C + αD, где α ∈ [0; 0,5].
в) Нельзя, так как G не лежит в выпуклой оболочке точек A, B, C, D.
г) Бесконечно много способов.
д) Один способ: из системы I = t1A + t2B + (1 − t1 − t2)D получаем I = 0,25A + 0,25B + 0,5D.
е) Один способ: J = 0,25A + 0,75B.
ж) Ни одного.
Редакционное объяснение
Одна параметризация на все пункты. Обозначим веса вершин wA, wB, wC, wD. У точек B и D абсцисса 5, у A и C — 1; у C и D ордината 4, у A и B — 2. Поэтому для точки P = (x, y):
x = 1 + 4(wB + wD), y = 2 + 2(wC + wD).
Возьмём t = wD за параметр. Тогда
wB = (x − 1)/4 − t, wC = (y − 2)/2 − t, wA = 1 − (x − 1)/4 − (y − 2)/2 + t.
Свобода в один параметр объясняется тем, что четыре точки на плоскости аффинно зависимы: A + D = B + C = (6, 6). Добавление к весам вектора (s, −s, −s, s) не меняет ни точку, ни сумму весов. Остаётся выяснить, при каких t все четыре веса неотрицательны.
- а) E = (1, 3): wB = −t, значит, t = 0 и E = 0,5A + 0,5C. Это единственный способ: E лежит на стороне AC, и любой положительный вес у B или D сдвинул бы абсциссу вправо от 1. Источник приводит этот ответ, но не отмечает единственность.
- б) F = (3, 3): wA = t, wB = wC = 1/2 − t, wD = t, где 0 ≤ t ≤ 1/2. Совпадает с ответом источника (α = t). Концы отрезка дают комбинации 0,5B + 0,5C и 0,5A + 0,5D — середины двух диагоналей, которые совпадают с центром прямоугольника F.
- в) G = (6, 3): wB + wD = 5/4 > 1, что невозможно: у любой выпуклой комбинации абсцисса не больше 5. Ответ: нельзя.
- г) H = (4, 3): wA = t − 1/4, wB = 3/4 − t, wC = 1/2 − t, wD = t. Все веса неотрицательны при t ∈ [1/4; 1/2] — бесконечно много способов. Например, t = 1/4 даёт H = 0,5B + 0,25C + 0,25D, а t = 1/2 даёт H = 0,25A + 0,25B + 0,5D.
- д) I = (4, 3) через A, B, D: требуем wC = 0, то есть t = 1/2. Получаем единственный способ I = 0,25A + 0,25B + 0,5D — правый конец отрезка из пункта «г». Три точки A, B, D аффинно независимы, поэтому барицентрические координаты в треугольнике ABD однозначны.
- е) J = (4, 2): wC = −t, значит, t = 0, и J = 0,25A + 0,75B. Способ единственный: J лежит на стороне AB.
- ж) K = (4, 2) через A, C, D: требуем wB = 0, откуда t = 3/4, но тогда wC = 0 − 3/4 < 0. Способов нет. Геометрически: треугольник ACD лежит над диагональю AD (прямая y = 2 + (x − 1)/2, при x = 4 она проходит на высоте 3,5), а K находится ниже.
Проверка. Подстановка: 0,25A + 0,25B + 0,5D = (0,25 + 1,25 + 2,5; 0,5 + 0,5 + 2) = (4, 3); 0,25A + 0,75B = (0,25 + 3,75; 0,5 + 1,5) = (4, 2). Все семь ответов проверены точным решением систем в рациональных числах.
Типичные ошибки. Забыть условие «сумма весов равна 1» и решать только координатные уравнения; путать линейную и выпуклую комбинацию (точку G можно получить линейной комбинацией, но не выпуклой); в пункте «ж» найти решение системы и не заметить отрицательный вес.
Что не следует из ответа
Из того, что точка лежит в выпуклой оболочке четырёх точек, не следует, что представлений бесконечно много: у точек на сторонах прямоугольника (E, J) оно единственное, а у вершин тем более. Бесконечное множество способов появляется только тогда, когда допустимый отрезок для параметра t имеет ненулевую длину, то есть для внутренних точек прямоугольника. Единственность в пунктах «д» и «е» держится на аффинной независимости используемых точек (или на положении точки на границе), а не на количестве точек.
Борис Демешев · «Задачки по методам оптимальных решений», задача 1.3 «Выпуклые комбинации четырёх точек» · Исходное задание и решение · CC0 1.0. Адаптация: формулы переписаны без LaTeX; в системе пункта «б» исправлена опечатка (справа должна стоять F, а не E); добавлены общая параметризация весов, доказательство единственности в пунктах «а», «д», «е» и проверка всех ответов.