|
||||||||||||||||||
|
Содержание№102
Баллы, полученные за решение данной задачи учитываются дважды:
в основном Марафоне и в тематическом конкурсе. Конкурсная задача №102 (КГ-2) (9 баллов)
На какое наименьшее число частей может разбиваться диагоналями выпуклый n-угольник
при:
Примечание: Решение Будем называть диагонали, соединяющие вершины выпуклого многоугольника через одну «короткими»), через две - «средними», через три - «длинными». Точку внутри многоугольника будем называть особенностью порядка k, если в ней пересекаются k+2 диагоналей. Ясно, что особые точки могут возникать только при пересечении средних и длинных диагоналей. Ординарный n-угольник разбивается своими диагоналями на (n-1)(n-2)(n2-3n+12)/2 частей, что при интересующих нас n составляет 25, 50, 91 и 154 соответственно. Каждая особенность порядка k уменьшает количество частей разбиения на k(k+1)/2. Сумму этих чисел по всем особенностям будем называть дефектом многоугольника. Для решения задачи нужно найти максимальный дефект для каждого из данных n. a) У шестиугольника всего 3 диагонали, не являющихся короткими. Поэтому в шестиугольнике может возникнуть всего одна особенность порядка 1 (она есть, например, в правильном шестиугольнике). Соответственно максимальный возможный дефект шестиугольника - 1 и минимально возможное число частей разбиения - 24. b) У семиугольника не может быть особенностей, порядок которых больше 1, (вершин не хватает). А то, что число осбенностей первого порядка не может превышать 3, следует из рассуждений, приведенных в решении задачи ММ104. В то же время 3 особых точки возможны. На рисунке 1 приведены два способа получения семиугольника с тремя особыми точками: достроением правильного пятиугольника; удалением вершины правильноо восьмиугольника. Разумеется, существуют и подходящие семугольники никак не связанные с правильными многоугольниками. Итак, максимальный дефект семиугольника - 3, наименьшее возможное число частей разбиения - 47. c) Представляется очевидным, что максимальный возможный дефект восьмиугольника возникает (в частности) у правильного восьмиугольника. Докажем это утверждение. При наличии особенности второго порядка на средней диагонали не может быть больше двух особенностей. Это легко увидеть на рисунке 2. На средней диагонали 1-4 уже есть две особенности Y и V. Точки пересечения нашей диагонали с короткими диагоналями не могут быть особенными. Остаются два кандидата на особые точки. Это X и U. Cделать точку X особой можно за счет смещения диагонали 3-8. Но это неизбежно приведет к тому, что точка Y, а заодно и Z перестанут особыми. Аналогично обстоят дела с точкой V. Поэтому на средней диагонали восьмиугольника не может быть больше двух особых точек. Но у правильного восьмиугольника на каждой средней диагонали их ровно по две. Единственная особенность второго порядка может возникать только на пересечении всех длинных диагоналей восьмиугольника. И у правильного восьмиугольника такая особенность есть. Таким образом, правильный восьмиугольник обладает максимальным дефектом среди всех восьмиугольников: он имеет 8 особых точек первого порядка и одну особую точку второго порядка. Поэтому дефект правильного восьмиугольника - 11, а число частей разбиения 80.
d) Именно к этому пункту относилось примечание к условию. Мне удалось найти
девятигольник с дефектом 17. Я полагаю, что это максимальный возможный
дефект, но доказывать это не умею. Поэтому дефект нашего девятиугольника равен 17, а число частей разбиения - 137. Обсуждение
Представляется правдоподобной гипотеза: при четных n максимальный дефект имеют
правильные n-угольники. Другое утверждение «правильные n-угольники с нечетным
числом сторон ординарны» относительно недавно перекочевало из разряда
правдоподобных предположений в категорию теорем. Набросок доказательства
появился еще в 1936 году в статье G.Bol: Beantwoording van prijsvraag no.17,
Nieuw Archief voor WisKunde 18 (1936), p.14-66.
Но строгое доказательство было опубликовано лишь в 1998 году: см.
«The number of intersection points made by the diagonals of a regular polygon»,
B. Poonen, M. Rubinstein, SIAM J. on Discrete Mathematics, Vol. 11, No. 1
(1998), p. 135-156. Если принять гипотезу о том, что правильный десятиугольник - «наиболее дефективный» среди десятиугольников, можно получить еще одно косвенное подтверждение тому, что построенный нами девятиугольник имеет максимальный возможный дефект. Добавив к нашему девятиугольнику вершину, симметричную девятой вершине относительно центра исходного восьмиугольника (см. рис. 4), получим десятиугольник с дефектом 26, т.е. с таким же дефектом. как у правильного десятиугольника. Андрей Халявин нашел для дефекта девятиугольника некоторую оценку сверку. Но она безусловно сильно завышена (28). Анатолий Казмерчук тоже нашел было девятиугольник с дефектом 17, но при ближайшем рассмотрении этот объект оказался то ли не совсем выпуклым, то ли не совсем девятиугольником (см. рис. 5). Награды Андрей Халявин и Анатолий Казмерчук (нашедшие девятиугольники с дефеком 15) получают по 8 призовых баллов. Николай Дерюгин нарисовал девятиугольник разрезаный 137 частей и поразительно похожий на тот, что приведен на рисунке 3 (только красиво раскрашенный), но не снабдил свою картинку обоснованиями (более строгими чем «похоже, что…»). Кроме того, он не обосновал максимальность дефекта правильного восьмиугольника. Николай получает 6 призовых баллов. Эстетическая оценка задачи - 5 баллов
|
|||||||||||||||||
|
||||||||||||||||||
|