Освещение пространства

Оглавление

1. Введение…………………………………………………………………стр.

2. Освещение пространства……………………………………………….стр.

2.1. Теорема Хелли………………………………………………………...стр.

2.2. Выпуклость. Выпуклая  оболочка ……………………………..стр.

2.3. Теорема Радона…………………………………………………стр.

2.4. Конус…………………………………………………………….стр.

3. Заключение………………………………………………………………стр.

4. Список литературы…………………………………………………….   стр.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

 

Предмет исследования: выпуклые множества, бесконечные световые конусы

Цель исследования: решить задачу об освещении пространства, изучить свойства выпуклых множеств, …..

Задачи исследования:

• Найти и изучить информацию по данной теме

Освещение пространства

Пора наконец осветить пространство. «Математическая суть» нашей  задачи такова: в пространстве имеются  четыре выпуклых конуса К1, К2, К3, К4 с общей вершиной О, ни один из которых не содержит противоположно направленных лучей. Кроме того, любые три из них имеют общий луч, а пересечение всех четырех — это точка О. Нужно доказать, что объединение К конусов К1, К2, К3, К4 — это все пространство.

Упражнение 3. Сформулируйте и дока- жите аналогичный результат для освещения плоскости.

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

Сейчас мы такой тетраэдр построим. Выберем в пространстве четыре точки A_1, А2, А3, А4 следующим образом: A_i — это какая-либо отличная от О точка из пересечения трех конусов К1 с номерами j, не равными i Пусть Т — выпуклая оболочка conv (.A1, А₂, Аз, А4). Теперь надо только показать, что Т — тетраэдр, граница которого содержится в К, и что О лежит внутри Т.

Надеемся, что школьник еще не забыл принцип «разделяй и властвуй». Настало время его применить. Итак, по теореме Радона множество {0, А1, А2, Аз, А4} можно разбить на два не- пересекающихся подмножества М и N таких, что conv (М) пересекает conv (N). Для определенности будем считать, что точка О содержится в М.

Разделение произошло. Пора властвовать. Обозначим через I множество индексов i, таких, что А. содержится в М, а через J множество индексов j, таких, что А содержится в N (заметим, что I может быть пустым, a J — нет). Тогда в силу выпуклости К множество conv (М) лежит в К_j для всех j из J, a conv (N) — в Кj для всех i из I. Так как любой номер 1,..., 4 содержится либо в I, либо в J, то пересечение conv (M) и conv (N) содержится в пересечении К1, К2, К3, К4, а следователь но, состоит только из точки О. Значит, О содержится в conv (М), и тем самым в Т.

Итак, О лежит в Т. Следующий шаг состоит в том, чтобы убить сразу двух зайцев. Если мы докажем, что О не принадлежит выпуклой оболочке никаких трех точек из числа А1, ..., А₄ то тогда, во-первых, точки A1,..., A4 не лежат в одной плоскости и, тем самым, Т — тетраэдр, а во-вторых, О лежит строго внутри Т.

Спокойно! Переходим к  убийству зайцев. Предположим, что О содержится в conv (A1, A2, A3), т. e. О лежит в треугольнике с вершинами А1, А2 А3 (или на его границе). Так как О не совпадает ни с одной из точек А„ то О лежит на некотором отрезке с концами В и С на сторонах треугольника, который, в свою очередь, в силу выпуклости принадлежит К4. Тем самым К4 содержит противоположно направленные лучи ОВ и ОС, что противоречит условию.

Остался последний шаг: доказать, что граница Т содержится в К. Ну, это просто: граница состоит из четырех треугольников, каждый из которых содержится в одном из конусов Kj (действительно Кj — выпуклый конус, содержащий все Ai при i, не равном j). Следовательно, граница Т принадлежит К.

Цель достигнута, пространство освещено.

Экономить стоит

Щедрый школьник наверняка  уже задался вопросом: «Если уж речь идет о такой грандиозной задаче, как освещение всего пространства, то стоит ли экономить на прожекторах. Можно ли, например, осветить все пространство, имея пять выпуклых световых конусов с общей вершиной О, каждые четыре из которых имеют общий луч?» Ответ на этот вопрос об экономии дает знаменитая теорема Хелли:

Если в пространстве даны п выпуклых множеств, где п> 4, каждые четыре из которых пересекаются, то все п множеств также имеют общую точку.

Конечно же, пять выпуклых множеств, получающиеся удалением вершины О из каждого конуса, удовлетворяют условию теоремы Хелли, и тем самым, имеют общую точку, скажем А. Но тогда луч противоположно направленный по отношению к лучу ОА, не содержится ни в одном из конусов. Пространство не удалось осветить полностью пятью прожекторами. Экономить на прожекторах стоит.

Итак, уважаемый школьник, теорема Хелли спасла нас от лишних и бесполезных затрат. Она выручает и во

многих других случаях. А кроме  того, она — яркое воплощение принципа «разделяй и властвуй». Сейчас мы это увидим.

Теорема Хелли доказывается индукцией по числу множеств п. Пусть Х1  Х2,... Х3 — выпуклые множества, удовлетворяющие условию теоремы. Если n=4, то все множества имеют общую точку по условию. Предположим, что утверждение теоремы справедливо для n—k, и докажем его для n=k+l.

Рассмотрим все множества X1, ..., Xk+1, кроме Xi. По условию каждые 4 из них пересекаются, а значит по предположению индукции эти k множеств имеют непустое пересечение. Пусть A_i — какая-либо точка из этого пересечения.

Разделяй! По теореме  Радона множество {А1, А2,..., Ak+1] можно разбить на два непересекающихся подмножества М и N такие, что conv (М) и conv (N) имеют непустое пересечение.

Властвуй! Обозначим через I множество индексов I, таких что A_i содержится в M, а через J множество индексов j, таких, что Aj содержится в N. Вспомним, что при i, не равном j, точка А, содержится в X_j. Следовательно, все точки Аi из М содержатся в каждом из множеств Xj, где j из J. И наоборот, все точки Аj из N содержатся в каждом из множеств Xi где i из I. В силу выпуклости conv (М) лежит в каждом Xj при j из J, a conv (N) лежит в каждом Xi при i из I. Таким образом, пересечение conv (М) и conv (N) содержится во всех множествах X1,..., Х_k+1, что и доказывает теорему.

Упражнение 4. Сформулируйте и докажите теорему Хелли для случая плоскости. (В справедливости теоремы Хелли для плоскости можно убедиться, наблюдая за выпуклыми пятнами света на сцене театра или арене цирка.)

Еще кое-что о выпуклости

Все, о чем мы здесь  рассказали, относится к комбинаторной геометрии выпуклых множеств. Заинтересовавшемуся школьнику рекомендуем найти и прочитать книгу И. Яглома и В. Болтянского «Выпуклые фигуры». Главы, посвященные выпуклым множествам, имеются также в 5 томе «Энциклопедии элементарной математики» и книге Д. Шклярского, Н. Чендова и И. Яглома «Геометрические оценки и задачи из комбинаторной геометрии».

Везде, где решаются задачи на максимум (минимум), естественным образом «возникают» выпуклые множества (даже если их и не было в условии задачи), а также тесно связанные с ними выпуклые функции. Подробнее об этом любознательный школьник может прочесть в книге В. Тихомирова « Рассказы о максимумах и минимумах», вышедшей в «Библиотечке «Кванта».

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

На плоскости таракан убегает от пауков-телепатов, которые в любой момент знают, в каком направлении и с какой скоростью он намерен ползти, и могут мгновенно менять свои скорости. Максимальные скорости всех насекомых одинаковы. При каких начальных условиях таракан сможет убежать, а при каких — нет?

Справившись с этой задачей, можете решить аналогичную про муху и ос в пространстве.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ОСВЕЩЕНИЕ ПРОСТРАНСТВА

Все началось с того, что мы нашли интересную задачу:

В точке пространства расположены прожектора. Каждый из них освещает часть пространства, испуская бесконечный выпуклый световой конус. При этом ни один конус не содержит противоположно направленных лучей, любые три из них имеют общий луч, а все четыре — нет. Докажи те, что тогда любая точка пространства освещена.

Но нам было не понятно, что такое «бесконечный конус» и  что такое выпуклый.

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

Так и появилась эта  исследовательская работа, в которой обсуждаются свойства выпуклых фигур, …. освещается пространство, доказывается знаменитая теорема Хелли, а также...

 

Теорема Хелли

 

Выпуклость 

Слово «выпуклый» довольно часто употребляют в жизни, так же, как и слово «вогнутый». Например, бывают плоские, выпуклые и вогнутые зеркала. Однако житейское и математическое понимание выпуклости несколько различны. В математике все (без исключения!) геометрические фигуры делятся на два класса: выпуклые и невыпуклые. Математическое понятие выпуклости на житейском языке можно выразить так: выпуклые фигуры — это фигуры, не имеющие вогнутостей. Вот точное определение:

Множество называется выпуклым, если вместе с любыми двумя точками  А и В оно содержит и соединяющий их отрезок. Пустое множество также считается выпуклым.

Если множество имеет вогнутость («ямку»), то отрезок, соединяющий ее края, принадлежит множеству не полностью, так что такое множество невыпукло.

Теперь вы можете легко  доказать, что точка, отрезок, плоскость, полуплоскость, круг, шар, куб и многие другие фигуры выпуклы, а множества на рисунке 1 — нет. А будет ли выпуклым пересечение*) круга и квадрата? Будет, причем безразлично, как они расположены друг относительно друга. Выпуклые множества обладают замечательным свойством: пересечение любого их числа — выпуклое множество. В самом деле, если А и В — две точки из пересечения, то они принадлежат каждому из множеств. А в силу выпуклости каждое из множеств содержит отрезок АВ, следовательно, и он принадлежит пересечению (рис. 2).

— Однако,— скажет въедливый школьник,— в учебнике уже даны определения выпуклого многоугольника и выпуклого многогранника. Это многоугольник (многогранник), лежащий по одну сторону от каждой прямой (плоскости), проходящей через его сторону (грань). Эквивалентны ли «школьное» и «общее* определение, то есть все ли многоугольники и многогранники, выпуклые по одному из определений, выпуклы и по другому?

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

Любой школьник сразу же заметит, что «общее» определение проще и универсальнее «школьного»: оно относится к самой фигуре, а «школьное» требует, чтобы многоугольник обязательно находился на плоскости (это нужно для понятия «по одну сторону от прямой»). Например, для грани многогранника сначала надо «провести* содержащую ее плоскость и только потом можно определить, выпукла ли грань.

Выпуклая оболочка

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

Для пространственного  тела следует поступать аналогично: засунуть это тело внутрь воздушного шарика и осторожно натянуть шарик, давая выйти воздуху.

Вот точное определение: выпуклой оболочкой множества М называется минимальное выпуклое множество, содержащее М, т. е. выпуклое множество, содержащее М и не содержащее других выпуклых множеств, содержащих М. Выпуклую оболочку множества М теоретически можно построить, взяв пересечение всех выпуклых множеств, содержащих М. Действительно, это пересечение выпукло и, кроме того, любое выпуклое множество, содержащее М, содержит и пересечение.

Как и во многих других случаях, чтобы не писать словосочетания «выпуклая оболочка множества М», придумано обозначение conv (М) (от слова convex — выпуклый).

Упражнение 1. Докажите, что:

а) М лежит в conv (М);

б) если М лежит в N, то conv (Af) лежит в conv (N);

в) conv (AUN) = conv (conv (M) U N).

Однако, как практически  найти conv (M), зная М? Рецепт достаточно прост и противоположен рецепту О. Родена получения скульптуры из глыбы мрамора постепенным отсечением всего лишнего: надо постепенно добавить все недостающее. А именно: рассмотрим множество М1 состоящее из точек всех отрезков с концами в M, затем множество M2, полученное подобным же образом из М1, и т. д. К счастью, оказывается, что этот процесс не очень долог: можно доказать, что для плоских фигур уже М2=сonv (М), а для пространственных — M₃=conv (М).

Упражнение 2 Постройте выпуклые оболочки следующих множеств: а) 4 точки на плоскости; б) 4 точки, не лежащие в одной плоскости; в) 5 точек в пространстве. Рассмотрите все возможные случаи!

Разделяй и властвуй

Недоверчивый школьник уже, конечно, засомневался: «Если отсекать лишнее от глыбы мрамора имеет прямой смысл (особенно если это делает Роден), то зачем, собственно, нужно трудиться, дополняя невыпуклое множество до его выпуклой оболочки?»

Дело в том, что дополнение множества до его выпуклой оболочки — процесс естественный. Это, например, подтверждает жизнь в стране Флатландии (впрочем, и в стране Спейсландии жизнь не лучше). Жители Флатландии, а проще — плоскости, одержимы манией к захвату территорий. Стоит нескольким жителям окружить какую-нибудь территорию, как они считают ее своей. Считается, что точка окружена, если нельзя провести прямую, относительно которой эта точка и точки А _и А₂,..., Аk, в которых находятся захватчики, лежат строго в разных полуплоскостях. Можно доказать, что окруженная территория — это выпуклая оболочка точек А1, А2 …,  А_к

Теперь знакомый с историей школьник понимает, что в точности означает выражение «находиться в кольце врагов»...

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

Верный способ избежать превращения Флатландии в империю — поссорить захватчиков. Они разделятся на враждующие группировки и забудут про захват территорий. Этот древний принцип называется «разделяй и властвуй». Из-за чего могут поссориться захватчики? Ну, конечно, из-за территорий: если две • группировки претендуют на одну и ту же территорию, ссоры не избежать. Школьник наших дней не ощущает недостатка в примерах.

Итак, принцип «разделяй  и властвуй» состоит в том, что нужно разбить множество точек A1, А2,..., A_k на два подмножества так, чтобы их выпуклые оболочки пересекались. (Тогда захватчики из обоих подмножеств будут претендовать на точки из пересечения.) Осуществимость принципа «разделяй и властвуй» первым доказал математик Радон, вот теорема его имени:

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

Проницательный школьник, конечно, заметил справедливость теоремы Радона, выполняя упражнение 1. Доказательство достаточно провести для четырех (пяти) точек, а остальные точки присоединить к любому из двух полученных множеств. Для четырех точек на плоскости доказательство видно из рисунка 5. Флатландия спасена.

Займемся пространством. Рассмотрим в нем точки А1,..., А5. Если какието четыре из них лежат в одной плоскости, то задача сводится к теореме Радона для плоскости, поэтому допустим, что А1,..., А4 в одной плоскости не лежат. Тогда conv (А1,..., А4) — тетраэдр с вершинами в них. Если он содержит А₅, то {А1, ..., А4) и {А₅} — нужное разбиение Предположим теперь, что А₅ не принадлежит тетраэдру. Плоскость, проходящая через три вершины тетраэдра, делит пространство на два полупространства,

одно из которых содержит тетраэдр. Тетраэдр — пересечение  четырех таких полупространств, следовательно, Л? не принадлежит какому-то из них — например, определяемому точками А₁ А₂ и А₃. Тогда отрезок A₄A₅ переcекает эту плоскость в некоторой точке В. Применив к точкам A1, A2, A3, В теорему Радона для плоскости, получим два множества, выпуклые оболочки которых пересекаются. Заменив точку В в одном из них на пару точек А4 и А5, получим требуемое разбиение.

Принцип «разделяй и властвуй» скоро нам понадобится, а тем временем мы узнали о выпуклости достаточно, чтобы заняться освещением пространства. Осталось только разобраться с тем, что такое конус.

Конус — это шаг  от малого к большому

Бывалый школьник не раз  видел пучок света от отдаленного прожектора. Поэтому он уже догадался, что математическое определение конуса таково:

Кону сом (бесконечным) называется множество, состоящее из точек лучей, выходящих из одной  и той же точки, называемой вершиной, конуса.

Само определение подсказывает, как построить примеры конусов: нужно взять лучи, выходящие из точки О и проходящие через какое-либо множество М. (Говорят, что такой конус порожден множеством М.) Если в качестве М взять круг в пространстве, не содержащий О, то получится круговой конус, а если многоугольник — то многогранный. Если лучи заменить отрезками, то получатся соответственно «школьный» круговой конус и пирамида. А что получится, если О лежит внутри круга? А если на его граничной окружности?

«Маленькое» множество может породить «большой» конус. Вот важный пример: если точка О лежит строго внутри тетраэдра Т (т. е. не на его границе), то все пространство — это конус, порожденный границей тетраэдра Т. «Маленький» тетраэдр породил бесконечное пространство.

Можно сконструировать  несметное количество конусов, воспользовавшись следующими свойствами конусов с общей вершиной: непустое пересечение таких конусов — конус, объединение — тоже конус.

Дочитавший до этого  места школьник знает, что выпуклый конус — это конус, являющийся выпуклым множеством. Например, если конус порожден выпуклым множеством, то он тоже выпуклый. Заметим при этом, что если у выпуклого конуса, не содержащего противоположно направленных лучей, удалить его вершину, то оставшееся множество будет по-прежнему выпукло.