Разбор задачи ММ128 математического марафона

================

Оценка за решение задачи ММ128 учитывается дважды в основном Марафоне и в тематическом конкурсе.

ММ128 (КГ-10) (20 баллов)

На сколько классов изополярных восьмиугольников разбиваются выпуклые восьмиугольники?

================

Решение

Очевидно, что у выпуклого восьмиугольника может быть не более одного полюса второго порядка. А из рассуждений, приведенных при разборе задачи ММ102, следует, что общее число полюсов не может превышать девяти. Поэтому число классов изополярных восьмиугольников не превышает 19.
Ниже приведены представители 17 классов изополярных восьмиугольников. Для каждого случая приводится не только рисунок, но и координаты вершин, дабы желающие (если таковые найдутся :) ) могли убедиться, что все без обмана.

1.


2.


3.


4.


5.


6.


7.


8.


9.


10.


11.


12.


13.


14.


15.


16.


17.


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

Обсуждение

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

Ясно, что, если в восьмиугольнике есть полюс второго порядка, полюса первого порядка могут быть расположены либо на пересечени двух 2-диагоналей и одной 3-диагонали, либо на пересечении трех 2-диагоналей.
Координаты вершин многоугольника с рисунка 17 были получены следующим образом:
Несколько вершин (полагаю не сложно догадаться какие) и полюсов были подобраны заранее. Положение остальных зависело от неких параметров. Затем составлялась система, позволяющая найти такие значения параметров, при которых получался бы восьмиугольник, имеющий один полюс второго порядка и пять полюсов типа 2-2-3.
Однако, полученный таким образом восьмиугольник имеет не пять, а целых восемь полюсов первого порядка (все типа 2-2-3). Учитывая, что я специально строил восьмиугольник, не обладающий какими-либо очевидными симметриями, гипотеза о том, что еще целых три полюса образовались случайно, выглядит не слишком правдоподобной :) Тем более, что картина повторяется при построении восьмиугольника с другими начальным данными.
Полагаю, эти примеры убедительно свидетельствуют: наличие одного полюса второго порядка и пяти полюсов типа 2-2-3, автоматически влечет появление еще трех таких же полюсов.
Значит, надо искать среди многоугольников имеющих полюса типа 2-2-2.

В какой-то момент времени я был близок к мысли, что мне вот-вот удастся построить восьмиугольник с характеристическим вектором (5, 1). Казалось бы, достаточно немного "пошевелить" восьмиугольник, изображенный на рисунке 18-1, и цель будет накрыта!


И я "пошевелил". Результат Вы можете видеть на рисунке 18-2. Как только вершины были подвинуты так, чтобы близкие точки пересечения диагоналей стянулись в один полюс второго порядка, четыре полюса типа 2-2-3 и один полюс типа 2-2-2, как черт и табакерки выскочил еще один полюс типа 2-2-2, на который до "шевеления" не было даже намека.


Координаты вершин возникшего восьмиугольника с характеристическим вектором (6-1), на мой взгляд, исключают гипотезу случайного появления дополнительного полюса:


Восьмиугольник с рисунка 18-2 сыграл со мной злую шутку. Изучая его, я обнаружил, что все шесть полюсов первого порядка лежат на одном эллипсе (это достоверный факт, я подставлял координаты в уравнение). После этого я решил, что для строгого обоснования невозможности случаев (5, 1) и (7, 1) надо "копать" в сторону терем Паскаля, Брианшона, Штейнера еtc. И копал...
Но вот Анатолий Казмерчук прислал "обоснование" существования восьмиугольника типа (5, 1). Он поступил аналогично тому, как поступал я, с той разницей, что не стал отыскивать требуемое значение параметра, а лишь наметил план и указал, что по соображениям непрерывности такое значение обязательно найдется.
Наученный предыдущим опытом, я не сомневался, что одновременно с пятым полюсом первого порядка образуется и шестой, и что эти шесть полюсов лягут на один эллипс.
Первая гипотеза подтвердилась. А вот вторая... Здесь и подставлять ничего не надо, достаточно взглянуть на рисунок 19.


По традиции приведу координаты вершин:

Мне по-прежнему не верится в случайность попадания шести полюсов многоугольника с рисунка 18-2 на один эллипс. Возможно так будет всегда, когда полюса типа 2-2-2 оказываются напротив друг друга. (Рисунок 16 показывает, что обращение этой гипотезы места не имеет.) Я наверняка постараюсь внести ясность в этот вопрос. Хотя построение примеров - вещь довольно утомительная. Даже с применением мат. пакетов.

Попытки построения восьмиугольника с характеристическим вектором (5, 1) и тремя полюсами типа 2-2-2 привели меня лишь к вырожденным "восьмиугольникам", у которых "склеиваются" несколько вершин.

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

Алексей Волошин, единственный из участников представивший законченное описание представителей классов (с указанием координат всех вершин), отталкивался от различных правильных многоугольников. В результате, в его примерах координаты многих вершин иррациональны, в отличие от восьмиугольников, приведенных на рисунках 1-17.
Полагаю, что для произвольных выпуклых n-угольников ситуация такая же: в каждом классе изополярных многоугольников найдется представитель, у которого координаты всех вершин рациональны (если надо, то и целы).

В общем случае из изополярности восьмиугольников, разумеется, не следует их однотипность и, тем более. изотопность. Однако для восьмиугольников, насыщенных полюсами, картина иная. Так, все восьмиугольники с характеристическим вектором (8, 1), очевидно, изотопны. Восьмиугольники с характеристическим вектором (6, 1) уже могут быть не изотопны (см. рис. 18-2 и рис 19), но, по-видимому, всегда однотипны. Похоже , что однотипны, а возможно, и изотопны, будут и восьмиугольники с векторами (9, 0) и (8, 0).

Интересно, что в разбиении восьмиугольников с характеристическими векторами (8, 1), (6, 1) и (9, 0) встречаются только треугольники и четырехугольники.

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

Награды

За решение задачи ММ128 Алексей Волошин получает 18 призовых баллов, Анатолий Казмерчук - 12 призовых баллов, а Сергей Половинкин - 10 призовых баллов.

Эстетическая оценка задачи 4.8 балла

================

Разбор задачи ММ128 подготовлен Владимиром Лецко.

Разбор задачи ММ127 математического марафона

================

Оценка за решение задачи ММ127 учитывается дважды в основном Марафоне и в тематическом конкурсе.

ММ127 (КГ-9) (12 баллов)

Существуют ли однотипные, но не изополярные многоугольники?

================

Решение

Каждый полюс первого порядка уменьшает количество количество элементарных многоугольников на 1, а суммарное количество сторон элементарных многоугольников на 6. Полюс второго порядка уничтожает 3 элементарных многоугольника и 16 сторон. Поэтому, если порядок полюсов многоугольников с различными характеристическими векторами не выше 2, они не не могут быть однотипны. В самом деле, если у таких многоугольников поровну элементарных многоугольников, то тот из них, у которого больше полюсов второго порядка будет иметь большее суммарное число сторон элементарных многоугольников.
Полюс третьего порядка уничтожает 6 элементарных многоугольников и 30 сторон. Легко видеть, что n-угольники c характеристическими векторами (3, 0, 1) и (0, 3, 0) имеют поровну элементарных многоугольников (на 9 меньше, чем у соответствующего ординарного n-угольника), а также равное суммарное число сторон (на 48 меньше, чем у ординарного). Поэтому такие n-угольники могут (но, разумеется, не обязаны) быть однотипными.
Наименьшее n, при котором существуют многоугольники с приведенными выше характеристическими векторами, равно 10. Мне удалось получить довольно много пар однотипных, но не изополярных десятиугольников с указанными характеристическими векторами. Я стартовал восьмиугольника с характеристическим вектором (3, 1) и с девятиугольника с характеристическим вектором (0, 3). К первому я добавлял пару вершин так, чтобы соединяющая их диагональ проходила через полюс второго порядка (превращая его в полюс третьего порядка), а ко второму - одну вершину так, чтобы не возникало новых полюсов. Однотипности удавалось добиться, используя значительную свободу в выборе добавляемых вершин.
На рисунках 1 и 2 приведена одна из пар однотипных, но не изополярных десятиугольников.



Каждый из десятиугольников разбивается своими диагоналями на 120 треугольников, 80 четырехугольников, 31 пятиугольник, 5 шестиугольников и один семиугольник. Конечно, разглядеть все элементарные многоугольники затруднительно из-за недостаточного масштаба рисунков. Поэтому приведу координаты вершин десятиугольников:
десятиугольник на рисунке 1: A(80; -80), B(102; -51), C(120; 0), D(80; 80), E(0; 100), F(-80; 80), G(-100; 50), H(-100; 0), I(-1200/17; -1200/17), J(0; -100);
десятиугольник на рисунке 2: A(90; -90), B(120; 0), C(120; 60), D(72; 97), E(48; 96), F(-2750/241; 18350/241), G(-1200/23; 1200/23), H(-100; 0), I(-2400/31; -1200/31), J(-40; -80).

Обсуждение

Другие пары, построенных мной однотипных, но не изополярных многоугольников имеют векторы граней (122, 75, 34, 6, 0, 0, 0), (120, 81, 28, 8, 0, 0, 0), (118, 84, 28, 7, 0, 0, 0).
Анатолий Казмерчук построил пару десятиугольников с такими же, как в моих примерах, характеристическими векторами и общим вектором граней (118, 82, 32, 5, 0, 0, 0).

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

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

Награды

За решение задачи ММ127 Анатолий Казмерчук получает 12 призовых баллов, Сергей Половинкин - 11 призовых баллов. За ряд правильных соображений и оценок Алексей Волошин получает 4 призовых балла. Дмитрий Пашуткин получает 2 призовых балла (по одному за ошибочное решение и своевременное обнаружение собственной ошибки :) ).

Эстетическая оценка задачи 5 баллов

================

Разбор задачи ММ127 подготовлен Владимиром Лецко.

Разбор задачи ММ126 математического марафона

ММ126 (4 балла)

Есть 8 шаров, среди которых 6 заряжены нейтрально, один - положительно и один - отрицательно. Есть прибор, который, будучи поднесённым к группе шаров, покажет их общий заряд (он покажет 0 и если в группе нет ни одного заряженного шара, и если они там оба).
За какое наименьшее число измерений можно найти положительный и отрицательный шары в группе?

================

Решение

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

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

Если выбрать для него 1 или 2 шара, прибор покажет 0 в 42 или в 32 случаях. При выборе трёх шаров для первого измерения (скажем, шары 1, 2 и 3), нейтральный заряд будет зафиксирован в 26 случаях, ещё по 15 вариантов распределения зарядов среди шаров дадут положительное и отрицательное показания. Эти случаи удобно рассмотреть в виде таблицы. Кадая её ячейка – это показание прибора в случае возможной пары шаров, заряженных положительно (по вертикали) и отрицательно (по горизонтали).



Вторым измерением 26 вариантов, давших нейтральное показание, нужно разбивать на 9+9+8.

Покажем, что это невозможно. Включения шаров из групп 1-3 и 4-8 независимо влияет на количества возможных показаний прибора. Если из шаров 1-3 выбрать в измеряемую группу 0 или 3 шара, то среди исходов измерения 6 раз встретится 0, и ни разу – плюс или минус. Для краткости запишем это так: 0 (-), 0 (+), 6 (0). Если же выбрать 1 или 2 шара, то среди исходов будут 2(-), 2(+), 2 (0)

Если из шаров 4-8 для измерения брать 0 или 5 шаров, то среди сиходов будут 0 (-), 0 (+), 20 (0). Если брать 1 или 4 шара, то 4 (-), 4 (+), 12 (0). И 2 или 3 шара, включённые в измеряемую группу, покажут 6(+), 6(-), 8(0).

Таким образом, наилучшее, чего можно добиться вторым измерением – это разбитие 26 вариантов на 8+8+10, выбрав, к примеру, 1, 7 и 8 шары



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



Довольно перспективный расклад: 16(+), 16(1), 24(0). Более того, в случае нейтрального результата в измерении 1, вторым замером эти 24 варианта разбиваются на 8+8+8 (и только так, расклады 9+9+6 и 9+8+7 невозможны), взяв шары №№3, 4, 5, 6.



И в случае нейтрального результата второго измерения на подозрении остаются 8 упорядоченных пар (положительный шар; отрицательный шар): (1;2), (2;1), (3;4), (4;3), (5;6), (6;5), (7;8), (8;7), Их можно разделить на 3+3+2, замерив шары 1, 3, 5. В таком случае прибор покажет:
«+» при (1;2), (3;4) или (5;6) – здесь для 4го измерения выберем пару №№1,4,
«–» - при (2;1), (4;3) или(6;5) – и здесь тоже,
и «0» при (7;8) или (8;7) – а тут достаточно узнать знак шара №8.

Итак, оставшимся четвёртым измерением можно однозначно найти искомые заряды.

Но в случае положительного результата второго измерения на подозрении будут такие 8 пар:
(3;1), (3;2), (4;1), (4;2), (5;7), (5;8), (6;7), (6;8). Применив соображения, аналогичные доказательству невозможности разбить 26 вариантов на 9+9+8, приходим к выводу, что невозможно выбрать такую группу шаров, чтобы третьим измерением разбить эти 8 вариантов на 3+3+2.

Таким образом, 4 измерения может и не хватить. Построим метод, дающий гарантированный результат за 5 замеров. В текущей ветке 8 вариантов легко разделить трёхкратной дихотомией.

В случае же, если после первого замера будет ненулевй исход (скажем, «+»), положительный шар находится среди 4 шаров, а отрицательный – среди остальных 4 шаров. На нахождение каждого дихотомией потребуется по 2 замера – итого в 5 укладываемся.

Обсуждение

Собственно задачу я сформулировал как модификацию известной задачи о поиске радиоактивных шаров. Введение зарядов, с одной стороны, удваивает возможные расположения шаров для заданного n, а с другой – предоставляет возможность каждым измерением делить это количество не на 2, а на 3.
Однако из-за того, что не непосредственно разделяем созможные варианты ответа на группы, а посредством выбора некоторой группы шаров, точное деление на 3 оказывается возможным далеко не всегда. И основной сложностью в этой задаче является именно доказательство невозможности уложиться в 4 измерения. При этом ветка, показывающая невозможность начинается после нулевого результата первого измерения и ненулевого - второго, а не после обоих нулевых результатов, как писали некоторые участники марафона.

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

Напрашивается обобщение задачи: за сколько измерений можно найти положительный и отрицательный шар для произвольного общего количества шаров n?

Оценкой снизу для искомой функции будет , сверху в первом приближении можно взять n-1 – достаточно проверить все шары, кроме одного.

Для небольших n можно построить таблицу:


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

Награды

Виктор Филимоненков и Алексей Волошин за правильное решение задачи получают по 4 балла. Сергей Половинкин, проведя очень интересное обобщение, в доказательстве невозможности решить текущую задачу за 4 измерения, привёл пример ветки, которая на самом деле за 4 измерения решается. Таким образом, он получает 3+2 (бонус за развитие темы)=5 баллов. Анатолий Казмерчук получает 3 балла, Эдвард Туркевич получает 2 балла, Николай Дерюгин и Евгений Гужавин получают по 1 баллу.

Эстетическая оценка задачи 4.4

================

Разбор задачи ММ126 подготовлен Алексеем Изваловым.