Тема КОМБИНАТОРИКА

Комбинаторная геометрия → .06 Принцип крайнего, индукция и другие методы в комбигео

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторика

Разделы подтемы Комбинаторная геометрия

Расположение точек, отрезков и прямых

Пересечение отрезков и прямых

Общая точка, прямая, покрытие. Теорема Хелли

Разрезания и геометрические конструкции в текстовых

Конструктивы в комбигео

Принцип крайнего, индукция и другие методы в комбигео

Клетчатая решётка (координатная плоскость) и точки, отрезки, прямые на ней

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 41#96505Максимум баллов за задание: 7

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

Показать доказательство

Формализуем планеты и Солнце как сферы, причём радиус сферы Солнца больше любого другого радиуса. Выберем две планеты и проведем через центры этих планет и Солнца плоскость $α$ .

$PIC$

Точки в которых к сфере Солнца проходят касательные плоскости, параллельные $α,$ будем называть полярными. Полярные точки не видны с планет, центры которых находятся в плоскости $α$ , поскольку радиус Солнца больше радиуса любой из планет. Помимо планет, центры которых лежат в плоскости $α$ , осталось не более шести планет, поэтому с одной из сторон от плоскости $α$ лежит не более чем три центра планет.

Полярная точка, расположенная в том полупространстве, где находится не более трех центров планет, видна разве что с этих планет, поэтому она видна не более чем с трех планет.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 42#69992Максимум баллов за задание: 7

На клетчатую плоскость со стороной клетки, равной $1,$ произвольным образом брошена салфетка $100 ×100.$ Она накрывает некоторые узлы (узел, лежащий на границе салфетки, тоже считается накрытым). Каким наименьшим числом прямых (идущих не обязательно по линиям сетки) заведомо можно покрыть все эти узлы?

Показать ответ и решение

Покажем, что $141$ прямой покрыть узлы можно. Проекция салфетки на ось $OX$ — это отрезок, по длине не провосходящий диагонали салфетки, то есть $√ - 100 2.$ Рассмотрим вертикальные линии сетки, пересекающие проекцию салфетки. Таких прямых не больше, чем $√ - [100 2]+ 1= 142.$ Если их оказалось $141$ или меньше , цель достигнуты. Если же их ровно $142,$ то самая левая и самая правая из них содержат ровно по одному узлу, накрытому салфеткой, этот факт доказан в лемме ниже. Заменим эти две прямые на одну прямую, проходящую через упомянутые узлы. В результате все нужные точки покрыты $141$ прямой.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Если салфетку пересекают $142$ вертикальные прямые, то самая левая и самая правая из них содержат ровно по одному узлу, накрытому салфеткой.

Доказательство. Действительно, пусть проекции двух смежных сторон салфетки на горизонтальную прямую равны $a$ и $b,$ $a≥ b.$ Допустим, что на одной из крайних прямых оказалось два или более узла. Тогда эта прямая отсекает от салфетки прямоугольный треугольник $δ1$ с гипотенузой, не меньше $1.$ Высота этого треугольника не превосходит $√ - 100 2− 141.$ Треугольник $Δ1$ подобен треугольнику $Δ2,$ который отсекает от салфетки прямая, проходящая через одну из вершин квадрата – верхнюю или нижнюю в зависимости от того, у какой из них проекция правее. Гипотенуза этого треугольника не превосходит диагонали квадрата, то есть $- 100√2,$ а высота равна $a$ и $b,$ и значит, не меньше $b.$ Нам известно, что $a +b≥ 141.$ Тогда

(a− b)2 = 2(a2+ b2)− (a+b)2 ≤ 20000− 1412 = 119,

т.е. $a − b< 11$ и $b= ((a+b)−2(a−b))> 65.$ Записывая пропорциональность высот и гипотенуз в подобных треугольниках $Δ1$ и $Δ2,$ получаем $√- 16005√2 < 100-2−1-141.$ С другой стороны, $√ - 10605√2 > 16543 = 511 > 0,45> 100 2− 141$ — противоречие.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Докажем теперь, что не всегда возможно провести $140$ прямых так, чтобы они проходили через все узлы. Построим контрпример. Возьмём координатную плоскость и расположим квадрат, диагональ которого расположена на оси $0x$ от точки $(0;0)$ до $(141;0).$ Его сторона равна $14√1< 100, 2$ поэтому его можно накрыть салфеткой со стороной $100.$ Проверим, что узлы, принадлежащие квадрату, нельзя покрыть $140$ прямыми. На диагонали расположено $142$ узла. Если диагональ не лежит ни на одной из проведённых прямых, то эти узлы должны покрываться различными прямыми, что невозможно, поскольку прямых всего $140.$ Поэтому прямая $y =0$ обязательно проведена. Теперь докажем по индукции, что при $0≤k ≤69$ проведены прямые $y =±k.$ База $k= 0$ уже проверена. Установим переход от $k − 1$ к $k.$ По предположению индукции уже проведены прямые

y = 0, y =±1, ..., y = ±(k − 1)

(всего $2k − 1$ прямая). Рассмотрим очередную прямую $y = k,$ на ней лежит $142− 2k$ узлов(на каждом шаге их количество уменьшается на 2). Если она не проведена, то эти узлы покрыты различными прямыми, что невозможно, поскольку нам осталось провести $140− (2k− 1)= 141− 2k$ прямых. Значит, она проведена. Аналогично должна быть проведена и прямая $y =− k.$ Итак мы установили, что заведомо проведено $2⋅69+ 1= 139$ прямых. Но при этом точки $(70;±70)$ и $(71;±70)$ всё ещё остались непокрытыми. Они являются вершинами прямоугольника и поэтому не могут быть покрыты одной прямой.

$PIC$

Ответ:

$141$

Ошибка.
Попробуйте повторить позже

Задача 43#97455Максимум баллов за задание: 7

На плоскости даны точки $A ,A ,...,A 1 2 n$ и точки $B ,B ,...,B . 1 2 n$ Докажите, что точки $B i$ можно перенумеровать так, что для всех $i⁄= j$ угол между векторами $−−−→ AiAj$ и $−−−→ BiBj$ – острый или прямой.

Источники: Всеросс., 2003, РЭ, 11.4(см. math.ru)

Показать доказательство

Выберем на плоскости начало координат $O$ и рассмотрим сумму $S =∑n OA--⋅OB--. k=1 k k$ Выберем такую нумерацию точек $B, i$ чтобы соответствующая сумма $S$ была максимальна. Рассмотрим теперь нумерацию точек $B,$ в которой $Bi$ и $Bj$ обозначены $Bj$ и $Bi,$ и ее сумму $′ S .$ По предположению $′ S ≥S ,$ но

′ ---- ---- -------- ---- ---- -------- S− S =OAi ⋅OBi+ OAj ⋅OBj −OAi ⋅OBj − OAj ⋅OBi ≥0

---- ---- ---- ---- (OAi −OAj)(OBi− OBj)≥ 0

Последнее неравенство выполняется для любых $i,j$ с максимальной суммой $S,$ что равносильно условию задачи.

Ошибка.
Попробуйте повторить позже

Задача 44#98987Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1

Попробуем восстановить исходный многоугольник. Неясно, как найти произвольную диагональ, поэтому полезно применить принцип крайнего при выборе диагонали.

Подсказка 2

Рассмотрим ту из стёртых диагоналей, которая отсекала наименьшее число вершин. Внутри отсечённого ею многоугольника диагоналей не проводилось, значит, отсечён треугольник, а у вершины против диагонали написана единица.

Показать ответ и решение

Рассмотрим ту из стёртых диагоналей, которая отсекала наименьшее число вершин. Внутри отсечённого ею многоугольника диагоналей не проводилось, значит, отсечён треугольник, и у вершины против диагонали написана единица.

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

Ответ:

Можно

Ошибка.
Попробуйте повторить позже

Задача 45#91943Максимум баллов за задание: 7

Дан остроугольный треугольник $A B C . 0 0 0$ Пусть точки $A , 1$ $B , 1$ $C 1$ — центры квадратов, построенных на сторонах $B C , 0 0$ $C A , 0 0$ $A0B0.$ С треугольником $A1B1C1$ делаем то же самое. Получаем треугольник $A2B2C2$ и т.д. Доказать, что $Δ$ $An+1Bn+1Cn+1$ пересекает $Δ$ $AnBnCn$ ровно в 6 точках.

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Предположим, что мы знаем, что все треугольники остроугольные. Рассмотрим (n-1)-ый и n-ый треугольники и шестиугольник, образованный их вершинами. Можно ли доказать, что он выпуклый?

Подсказка 3

Конечно! Стороны этого шестиугольника являются биссектрисами квадратов, построенных на сторонах (n-1)-го треугольника, тогда диагонали этого шестиугольника лежат внутри его углов. Тогда задача решена. А как доказать, что все треугольники остроугольные?

Подсказка 4

Конечно, надо действовать по индукции! Ранее мы использовали только остроугольность (n-1)-го треугольника. Можно ли теперь вновь использовать утверждение, которое мы уже доказали?

Подсказка 5

Можно! Мы уже знаем, что из n-го и (n-1)-го треугольника легко появляется выпуклый шестиугольник. Как из этого получить нужное утверждение?

Показать доказательство

Докажем, что если $△A B C n−1 n−1 n−1$ остроугольный, то $A B C n n n$ пересекает его в шести точках. Заметим, что $∘ ∠BnAn −1Bn−1 = ∠CnAn−1Bn−1 = 45 .$ Тогда лучи $An−1Bn−1$ и $An−1Cn −1$ лежат внутри угла $BnAn−1Cn.$ Аналогичное утверждение верно для вершин $Bn−1$ и $Cn−1.$ Таким образом, $An−1CnBn−1AnCn−1Bn$ — выпуклый шестиугольник. Тогда, действительно, $△An −1Bn−1Cn−1$ и $△AnBnCn$ пересекаются в $6$ точках.

Докажем теперь, что $AnBnCn$ — остроугольный треугольник. Доказательство проведем по индукции. База верна по условию. Пусть $△An −1Bn−1Cn−1$ — остроугольный. Тогда у нас уже есть доказанное утверждение о том, что $An− 1CnBn −1AnCn −1Bn$ — выпуклый шестиугольник. Тогда $∘ ∠CnAnBn < ∠Bn−1AnCn −1 = 90 .$ Таким образом, $∠CnAnBn$ — острый. Аналогично для остальных углов треугольника $AnBnCn.$ Тогда, действительно, треугольник $AnBnCn$ остроугольный.

$PIC$

Предыдущая подтема

Следующая подтема