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

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

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

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

Ясно, что и где — количество способов выбрать пару противоположных вершин -угольника и ещё одну вершину (такие способы порождают треугольник, а не четырёхугольник).

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

Итого способов.

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

Давайте считать, что расположены против часовой стрелки. Первую сторону треугольника можно выбрать способами. Пометим параллельную сторону красным. Для выбора второй стороны отсчитываем сторон от где Помечаем параллельную сторону синим. Для выбора c остаются только стороны между красной и синей сторонами –— и вариантов выбора будет ровно Значит, всего треугольников будет (умножаем на чтобы учесть тройки, где расположены по часовой, и делим на для учёта всех перестановок между собой). Используем формулу суммы прогрессии, получаем, что всего треугольников будет

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

1.

если

2.

если

3.

если

4.

если

Равносторонний треугольник можно выбрать, если делится на Таких треугольников будет штук. Если на не делится, то их не будет.

1.

если

2.

если

Значит, у нас есть неравнобедренных, равнобедренных неравносторонних и равносторонних треугольников.

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

Значит, ответ (в общем случае при чётном ) равен:

А при ответ равен

Если — вписанный четырёхугольник, то он перейдёт в равный четырёхугольник за три операции. Любой допустимый четырёхугольник перейдёт в равный ему четырёхугольник за операций, (например, за

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

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

Тогда

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

Если — вписанный четырёхугольник, то — центр описанной окружности, и такой четырёхугольник полностью задаётся длинами сторон, их порядком и описанной окружностью. Четырёхугольник, получающийся через три операции, также вписан в ту же окружность, так как

и имеет те же стороны, что и исходный, следовательно, равен ему.

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

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

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

Трижды проведем данные операции и посмотрим на соответствующие вершинам векторы:

Четырехугольник определяется векторами сторон и порядком обхода, для исходного данные вектора равны:

а для четырехугольника полученного через три операции:

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

Покрасим прямую в два цвета: с одной стороны в красный, с другой в синий. Соответствующие полуплоскости будем именовать аналогично. При вращении сохраняется число точек в синей полуплоскости и число точек в красной полуплоскости (за исключением моментов, когда прямая проходит через две точки). Это происходит, так как когда мельница “натыкается” на некую точку допустим, из красной полуплоскости, вращаясь вокруг точки то через малое время вращения вокруг точка попадёт в красную полуплоскость.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обозначим девятиугольник как Рассмотрим четырёхугольники и Заметим, что оба прямоугольниками они быть не могут, так как он однозначно задаётся тремя точками. Значит, так как сумма углов в четырёхугольнике равна один из них будет иметь тупой угол, который и даст нам искомый треугольник.

Зафиксируем положение квадрата (временно запретим повороты) и перекрасим два его узла. Возможны два случая:

1.

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

2.

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

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

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

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

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