Геометрия, Задача

[Andrey173]

Какое наименьшее число точек достаточно отметить внутри выпуклого $n$-угольникка, чтобы внутри любого треугольника, вершины которого совпадают с вершинами этого $n$-угольника, содержалась хотя бы одна отмеченная точка?
Что скажете? С чего начать?

[Хорхе]

Начать с того, что решить задачу для $n=3,4,5,6$. А потом авось и поймете, что к чему.

[Sasha2]

А мне кажется, что на любой диагонали можно выбрать сколько угодно точек.
Или я может неправильно условие понимаю.

[ИСН]

Всё сложно.

[Andrey173]

Sasha2 в сообщении #373185 писал(а):

А мне кажется, что на любой диагонали можно выбрать сколько угодно точек.
Или я может неправильно условие понимаю.

Не совсем понял Вашу идею.

-- Ср ноя 10, 2010 22:58:46 --

Хорхе в сообщении #373168 писал(а):

Начать с того, что решить задачу для . А потом авось и поймете, что к чему.

Ну выходит что n-2. В Шестиугольнике трудновато уже)

[Sasha2]

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

[Andrey173]

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

[MrDindows]

Sasha2
При чём тут вообще "сколько угодно" ? У нас в условии наоборот говорится, что надо минимальное количество точек так, чтоб в каждом треугольнике было хотя бы по 1 точке!
Мы ж будем выбирать точки наилучшим для нас образом...а не на диагоналях)

[Andrey173]

Sasha2 должен знать) Он спец по геометрии.

[Хорхе]

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

(Оффтоп)

Если есть "маловероятно", то и "многовероятно" должно быть.

[Andrey173]

Что-то трудно для 8ого класса. Хоть и углубленное.
В указаниях написано просто - учесть что диагонали с общей вершиной делят многоугольник на n - 2 треугольника.

-- Чт ноя 11, 2010 16:17:56 --

Эта задача есть в Кванте за 1979 год. Под звездочкой:D

-- Чт ноя 11, 2010 16:20:01 --

http://www.mccme.ru/free-books/prasolov ... #ref-21.10 - вот тут какое-то смутное решение
http://nature.web.ru/db/msg.html?mid=1156412&mode=2 - Вот нормальное решение

(Оффтоп)

Надо было сразу Яндекс юзать.

[Sasha2]

Вот эти все решения, которые приведены, и в которых оперирует число $n-2$, мне кажется не совсем правильные.
Это $n-2$ совершенно из другой оперы, а именно забывают указать, что да действительно любой выпуклый (и невыпуклый тоже) n-угольник можно разрезать на $n-2$ треугольника. Однако надо тут добавить такое важное слово НЕПЕРЕСЕКАЮЩИХСЯ. Этого авторы приведенных решений почему то забывают. А треугольники, которые рассматриваются в данном случае, ну вот так на вскидку, не скажешь, что они как-то соотносятся с теми $n-2$ треугольниками. Это совершенно другие треугольники. И их во первых не $n-2$, а $C_n^{3}$.

[Andrey173]

А правильное решение Вы знаете?

[Sasha2]

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

-- Чт ноя 11, 2010 14:06:59 --

А вот из этих n-2 следует только то, что n-2 - это минимальное число точек, которые нужно обязательно проставить.
А вот можно ли этим числом обойтись трудно сказать сразу.

[Хорхе]

Andrey173 в сообщении #373411 писал(а):

http://nature.web.ru/db/msg.html?mid=1156412&mode=2 - Вот нормальное решение

А чем это решение не подходит-то? Все честно, да.