Условия задачи: Дан выпуклый многоугольник. Дан "нож", которым можно "разрезать" этот многоугольник. Нож - 2 бесконечные прямые, пересеченные под прямым углом.

Требуется найти: точку-где должен быть центр ножа, что бы разрезать многоугольник на 4 равные части.

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

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

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


Скажите, пожалуйста, в каком месте моя логика провальна? Знаете ли вы решение данной задачи?

задан 26 Ноя '13 19:54

изменен 26 Ноя '13 20:08

Доказательство существования такой точки в более общем случае можно найти, например, в книге "И.М.Яглом, В.Г.Болтянский. Выпуклые фигуры" (решение задачи 28 б). Что значит в данном случае "Требуется найти: точку"? Нужно явно выразить её координаты через координаты вершин многоугольника? А угол поворота "ножа" тоже нужно вычислить?

(27 Ноя '13 15:19) splen

@splen, Да и Да. Требуется вычислить координаты и угол.

(27 Ноя '13 18:18) Андрей Алексеев

@Андрей Алексеев: в таком виде, как Вы сейчас сказали, это задача фактически по программированию. Но в принципе её тоже можно было бы решить.

(27 Ноя '13 18:42) falcao

@falcao, Да, это как раз и есть задача по программированию.

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

(27 Ноя '13 18:58) Андрей Алексеев

@Андрей Алексеев: а я тоже когда писал, то "по инерции" не подумал, что общей точки для всех прямых нет. Если же говорить о программировании, то поскольку точка с нужным свойством существует, её можно найти при помощи алгоритма. Для этого пересекаем всё прямыми, параллельными осям координат и проходящими через вершины. В процессе этого надо будет какие-то трапеции поделить на части нужной площади. С поворотами чуть сложнее, но и это выполнимо с привлечением тригонометрии.

(27 Ноя '13 19:03) falcao

@falcao, да. Но, тут уже не будет сильных загвоздок в идейности. Немножко воображения и аккуратности. Спасибо за идею:)

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

Подскажите, пожалуйста.

(27 Ноя '13 19:14) Андрей Алексеев

@Андрей Алексеев: сам я к программированию имею лишь "пользовательское" отношение. Из книг на эту тему, где собраны интересные олимпиадные задачи по программированию, с подробным разбором решений, могу порекомендовать книгу Фёдора Меньшикова "Олимпиадные задачи по программированию".

(27 Ноя '13 20:24) falcao

@falcao, Спасибо! :)

(27 Ноя '13 20:31) Андрей Алексеев
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
1

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

Какое бы направление мы ни взяли, всегда имеется параллельная прямая, делящая фигуру на две части, имеющие равную площадь. Это следует из соображений непрерывности. Будем двигать прямую параллельно себе. Ясно, что существуют два таких положения, при котором часть фигуры "слева" имеет большую площадь, чем часть фигуры "справа", и наоборот. Но тогда существует и такая прямая, для которой площади частей равны. Легко также видеть, что эта прямая единственна: при сдвиге прямой в одну из сторон площадь одной части увеличится, а площадь другой уменьшится.

Проделаем описанную процедуру с произвольно выбранным направлением, а потом и с перпендикулярным ему. Фигура будет разделена на 4 части, площади которых можно обозначить через $%a$%, $%b$%, $%c$%, $%d$%, если обходить вокруг точки по часовой стрелке. По одну сторону от первой прямой находятся части площадью $%a$% и $%b$%, по другую -- $%c$% и $%d$%. Отсюда $%a+b=c+d$%. Если рассмотреть вторую прямую, то аналогичным образом выводится равенство $%a+d=b+c$%. Рассматривая полученную систему, мы видим, что $%a=c$%, $%b=d$%. Таким образом, при обходе вокруг точки площади частей будут такие: $%a$%, $%b$%, $%a$%, $%b$%. Здесь также можно заметить, что при заданных направлениях есть ровно одна точка с описанным выше свойством, когда части фигур, расположенные в противоположных четвертях, равны друг другу. Если сдвинуть точку пересечения в одну из четвертей, то в этой четверти площадь уменьшится, а в противоположной -- увеличится. Такую точку для заданных направлений далее будем для краткости называть "точкой псевдобаланса".

Рассматривая одну из таких точек, выберем по единичному вектору вдоль каждого из направлений. Пусть это будут векторы $%x$% и $%y$%. Начнём вращать эти направления, чтобы вектор $%x$% постепенно перешёл в вектор $%y$%. Точка псевдобаланса при этом будет, вообще говоря, меняться, двигаясь по непрерывной кривой и возвращаясь в конце в своё исходное положение. Следя за изменяющимся вектором $%x$%, будем сравнивать числа $%a$% и $%b$% -- площади фигур, расположенных "влево" и "вправо" от вектора $%x$%. Если изначально эти площади не были равны, то выполнялось неравенство, скажем, $%a > b$%. В процессе движения вектора, роли этих частей поменяются, и фигуры перейдут в фигуры площади $%b < a$%. Поскольку площади меняются непрерывно, из этого следует, что существует какое-то промежуточное положение, при котором площадь части фигуры "слева" от вектора будет равна площади фигуры, расположенной "справа" от него, то есть будет иметь место равенство $%a=b$% для одной из промежуточных точек псевдобаланса. При этом все четыре фигуры станут иметь одинаковые площади.

В заключение заметим, что даже если фигура имеет центр симметрии, из этого не следует, что угол расположения "ножа" не важен: Достаточно взять шестиугольник с координатами вершин $%(1;0)$%, $%(1;-1)$%, $%(0;-1)$%, $%(-1;0)$%, $%(-1;1)$%, $%(0;1)$%, разрезаемый осями координат. Площади фигур 2-го и 4-го координатных углов здесь равны $%a=1$%, а для 1-го и 3-го угла площади равны $%b=1/2$%.

ссылка

отвечен 27 Ноя '13 5:12

изменен 27 Ноя '13 9:25

1

@falcao, может я чего-то не понимаю... но если рассмотреть треугольник $%ABC$%, в котором центр масс точка $%Q$% - точка пересечения медиан... и через $%Q$% и провести прямую, параллельную стороне, то мы отсечём треугольник, площадь которого равна $%\frac{4}{9}\,S_{ABC}$%, что не является половиной...

(27 Ноя '13 7:36) all_exist

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

(27 Ноя '13 7:53) falcao
10|600 символов нужно символов осталось
0

@all_exist, скажите, пожалуйта , у вас получилось решить задачу до конца и написать код?

ссылка

отвечен 11 Сен '14 23:40

@Infinite, я не занимался решением, а просто сделал замечание по поводу уже написанного... код тоже не писал... да, и автор топика тоже не я ... :)

(14 Сен '14 15:32) all_exist
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×2,424
×972
×325
×51

задан
26 Ноя '13 19:54

показан
4851 раз

обновлен
14 Сен '14 15:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru