Комбинаторная геометрия → .01 Расположение точек, отрезков и прямых

Оценка. Сдвинем точки так, чтобы они имели целые координаты от 1 до и отметим для каждого отрезка его середину. Заметим, что если у двух отрезков совпадают середины, то один из них целиком содержится в другом. Поэтому количество отрезков не превосходит количества отмеченных середин. Каждая середина имеет координату вида , где . Всего таких точек будет как раз

Пример. Отметим все отрезки длины 1 и длины 2.

Прежде всего прокомментируем условие задачи. Количество треугольников с синими вершинами равно поэтому “остальных” треугольников действительно

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

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

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

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

Если восьмерка лежит сразу в из множеств то она лежит и в третьей. Это значит, что пересечение двух множеств или пусто, или пересекается с третьим.

Чтобы найти ответ надо найти количество элементов в объединении множеств. Используя формулу включений-исключений, получаем, что

где — означает количество элементов во множестве — искомое число

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

Тогда посчитаем

Посчитаем отдельно количество тетраэдров и выпуклых угольных пирамид с

Количество тетраэдров это количество способов выбрать точки, не лежащих одновременно в одной плоскости. Тогда количество тетраэдров равняется

Найдем количество выпуклых угольных пирамид с Основание такой пирамиды лежит в плоскости а вершина — вне Тогда посчитаем количество оснований. Надо просуммировать все способы выбрать от 4 до 7 вершин без учёта порядка

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

Итоговый ответ

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

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

то есть существует ход, после которого количество точек, гарантирующих победу первому игроку будет больше, чем количество всех синих точек на плоскости.

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

Будем перебирать всевозможные четвёрки точек и для каждой четвёрки определять число остроугольных и неостроугольных треугольников, которые они образуют. Сложив количества остроугольных треугольников по всем четвёркам точек, получим некоторую сумму Таким же образом сложив количества неостроугольных треугольников по всем четвёркам точек, получим некоторую сумму Заметим, что из четырёх точек, никакие три из которых не лежат на одной прямой, хотя бы три образуют тупоугольный или прямоугольный треугольник. В самом деле, если четыре точки являются вершинами выпуклого четырёхугольника, то один из его углов не меньше если же точки таковы, что одна из них, скажем, лежит внутри треугольника, образованного оставшимися тремя точками, то один из углов тупой. Таким образом, один из треугольников всегда является неостроугольным. Итак, каждая четвёрка точек дает вклад в сумму не меньший а в сумму — не больше Отсюда следует, что Поскольку каждая тройка вершин входит в четвёрки, каждый треугольник посчитан в соответствующей сумме ( или ) ровно раза. Таким образом, имеется остроугольных и неостроугольных треугольников. Следовательно, число остроугольных треугольников не более чем в раза превосходит число неостроугольных, тем самым, число остроугольных треугольников составляет не более от общего числа треугольников.

Из данных точек выбираем такие, что треугольник с вершинами в данных точках имеет наибольшую площадь из всех треугольников с вершинами в данных точках. Пусть это будут точки (рис.). Проведём через точку прямую Каждая из точек будет лежать по ту же сторону от прямой что и треугольник ибо иначе площадь треугольника с вершиной в этой точке и основанием была бы больше площади треугольника Проведя через точку прямую и через точку прямую точно так же докажем, что все точек лежат по ту же сторону от прямых и что и точки Следовательно, все точек будут лежать внутри треугольника Площадь этого треугольника состоит из площадей четырёх равных треугольников. Поскольку площадь одного из них не превосходит единицы, то площадь всего треугольника не превосходит четырёх.

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

Для невыпуклого величина будет меньше.

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

Рассмотрим крайние точки, их Давайте посмотрим на какие-то две соседние и из них. Что значит, что каждая точка лежит в собственной части? Например, ясно, что если никакая из прямых не пересекает отрезок , то точки и будут в одной части. Всего таких отрезков а каждая из прямых пересекает не более то есть они пересекут не более отрезков. Значит, нельзя.

Пусть отмечены красные точки , синие точки , и зеленые точки .

Поскольку для каждой точки выполняется неравенство треугольника , то

Откуда .

Аналогично, просуммировав неравенства , получим .

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

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

Первый вариант:

Второй вариант: .

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

Начнем перемещать синюю точку по прямой, не содержащей красные точки. Остановимся тогда, когда она пересечет первый отрезок с концами в красных точках, но еще не дойдет до второго. Если такого момента времени не существует, значит синяя точка не лежит ни в одном красном треугольнике (любая прямая, проведенная через синюю точку, пересекла бы его стороны), и утверждение задачи очевидно. Назовем вершины пересеченного отрезка и

Сравним количество треугольников, содержащих синюю точку в исходном ее положении и после перемещения. Ясно что любой треугольник, не содержащий сторону либо содержал синюю точку оба раза, либо не содержал, так как синяя точка не пересекла на своем пути ни одну из его сторон. Рассмотрим полуплоскость относительно в которой изначально располагалась синяя точка. Утверждается, что треугольник со стороной и третьей вершиной в любой красной точке этой полуплоскости содержал синюю точку в ее исходном положении. Действительно, в противном случае отрезок, соединяющий исходное положение синей точки и точку, в которой траектория ее движения пересекает пересекает и некоторую сторону этого треугольника. Ясно, что никакой треугольник со стороной и вершиной в другой полуплоскости не содержит исходное положение синей точки. Теперь рассмотрим другую полуплоскость относительно  – в которой располагается синяя точка в момент остановки. Аналогично, треугольник со стороной и любой вершиной этой полуплоскости содержит синюю точку после перемещения.

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

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

В этой задаче возможны два случая: когда отрезки отложены от общего конца в одну сторону и когда они отложены в разные стороны.

Сначала разберем случай, когда они отложены в разные стороны. Обозначим общий конец отрезков через , вторые концы — через и (причем отрезок меньше ). Тогда точка лежит между и . Далее, обозначим середины и через и . Нам нужно найти длину отрезка . При этом точка лежит между и .

Так как  — середина , то длина . Аналогично так как  — середина , то длина . Тогда длина искомого отрезка, то есть , равна сумме .

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

Теперь, чтобы найти длину , можно из длины отрезка вычесть длину отрезка . Отрезок , равный половине , равен . Отрезок , равный половине , равен . Получаем, что .

Итак, мы разобрали оба возможных случая, в одном получили ответ , в другом — . Задача решена.

Выберем квадрат, который нельзя подвинуть (если такого нет, то у нас движимых квадрата). Проведем прямые, содержащие его диагонали. Они разобьют плоскость на части: верхнюю, нижнюю, правую и левую. Заметим, что строго внутри каждой части лежит центр некоторого квадрата (иначе исходный квадрат можно подвинуть в соответствующем направлении). Рассмотрим отдельно верхнюю часть. Выберем квадрат, центр которого является одним из самых высоких, принадлежащих верхней части. Тогда этот квадрат можно подвинуть наверх (иначе в верхней части был бы более высокий центр некоторого квадрата). Аналогично выбираем движимые квадраты в других частях. Таким, образом. движимых квадратов хотя бы

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

Расположим числа в порядке возрастания: Покажем, что медиана этого ряда - число - является искомым. Обозначим — сумма расстояний от числа до остальных чисел.

Рассмотрим число Если то сумма расстояний от до первых четырёх чисел увеличится на а до последних четырёх — уменьшится на (по сравнению с числом ), и при этом до самого числа расстояние равно то есть Если , то есть , то сумма расстояний от до всех чисел будет равна Рассуждая аналогично при получим вывод: минимальное значение достигается при При отрицательных значениях рассуждения ничем не отличаются.

Объем тетраэдра с ребром 8 есть поскольку этот тетраэдр получается если взять не соединенные ребром вершины куба с ребром Заметим, что значит если удастся тетраэдр разрезать на 64 тетраэдра с вершинами в отмеченных точках, то один из тетраэдров разбиения будет иметь объем меньше

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

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