Комбинаторная геометрия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если же помечены не все строки и не все столбцы, то всего отмечено не более строк и не более столбцов:

Отсюда следует ответ

Применим принцип крайнего: выберем среди всех троек точек треугольник с самым большим углом

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

При этом не может лежать внутри треугольника , иначе .

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

получаем противоречие. То же работает для случая, когда лежит между лучами и .

Оставшиеся два случая (когда и лежат в разных полуплоскостях относительно ) рассматриваются аналогично: в них

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

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

Вопрос о целых точках на треугольнике, получается, стоит так: при каких целых система:

имеет решения , удовлетворяющие условиям выше.

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

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

Проецируем треугольник на — получается треугольник на плоскости с вершинами Внутрь него точки попадут такие:

Решаем систему, состоящую из двух первых уравнений:

Получаем следующие решения:

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

то есть должна быть чётной. Из кандидатов подойдут только .

Плюс точки на сторонах, и всего точек на треугольнике

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

Раскрасим узлы в 10 цветов так, чтобы узлы одного цвета образовывали сетку из квадратов со стороной . Например, пусть цвет узла с координатами ( ) определяется остатком от деления числа на 10 (считаем, что деревья растут в центрах квадратов):

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

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

Будем доказывать утверждение задачи индукцией по

База. Для треугольника утверждение задачи очевидно.

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

Переход. Докажем утверждение для Рассмотрим триангуляцию нашего -угольника. Найдем в нем “ухо” и пока забудем об этом треугольнике триангуляции. Оставшийся -угольник можно раскрасить в три цвета правильным образом по предположению индукции. Вернем наше “ухо”. Оставшаяся вершина -угольника, которая принадлежит только “уху” из треугольников триангуляции, соседствует только с вершинами. Значит, ее можно спокойно покрасить в оставшийся цвет. Переход доказан.

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

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

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

Перед нами задача вида “оценка пример”. Сперва докажем оценку. По индукции по будем доказывать, что наибольшее возможное значение не превосходит

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

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

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

Проделаем следующую процедуру: для отрезка с важностью эти две вершины склеим в одну вершину и для каждой вершины важностью будем считать равной важности Докажем, что многоугольник удовлетворяет первому условию и “ослабленному” второму, т.e. важности всех его сторон и диагоналей образуют отрезок или натурального ряда без пропусков. Действительно, для любого подходящего треугольника нового многоугольника, если ни одна из вершин не была склеена с другой, то требование на важности сторон не изменилось. Если же какая-то вершина (без ограничения общности, вершина ) была склеена из вершин и то, как было показано ранее, распределение важностей в треугольнике будет таким же, как в треугольниках и в каждом из которых первое условие было выполнено, а значит, оно не нарушилось и после склейки. Второе, "ослабленное"условие также будет выполнено, т.к. после склейки из набора важностей будет удалено

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

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

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

Оценка. Для начала докажем, что больше самопересечений быть не может. Назовём звенья одного направления горизонтальными, а звенья второго направления — вертикальными. Расположим плоскость так, чтобы горизонтальные звенья действительно стали горизонтальными. Заметим сразу две вещи:

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

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

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

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

Пример. Пронумеруем и вертикальные звенья тоже. Пусть -е вертикальное ребро соединяет и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья.

Аналогичный пример для -звенной ломаной на картинке ниже:

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

(b) Докажем, что если проведено прямых, то число треугольников не меньше

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