2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Рациональная площадь
Сообщение20.04.2017, 09:46 


29/07/08
536
Докажите:
1. Площадь многоугольника, вершины которого лежат в узлах координатной сетки, имеет целое или полуцелое значение.
2. Площадь многоугольника, вершины которого имеют рациональные координаты, также будет иметь рациональное значение.

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 10:56 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Если сделать нарезку многоугольника на треугольники, посчитать площади по координатным формулам и сложить, получим оба пункта. Предполагались какие-то ограничения на уровень знаний? (или в чём олимпиадность?)

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 11:33 


29/07/08
536
Конечно ограничения на уровень знаний предполагалось! Мне показалось, что уровню школьников это подойдет.

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 12:48 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Побережный Александр в сообщении #1210978 писал(а):
Мне показалось, что уровню школьников это подойдет.
А школьники в каком классе? Они поймут, что речь идёт о выпуклом многоугольнике? Если они знают, что существуют невыпуклые, то такая задача им вряд ли по силам. (Хорошо хоть о самопересечениях здесь не нужно думать.)

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

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 13:33 


29/07/08
536
grizzly в сообщении #1210996 писал(а):
Да, для треугольника можно без всяких формул показать (полу)целость площади -- достроив нужным образом окаймляющий прямоугольник вырезав из него при необходимости другой. Предполагалось примерно такое решение?

Именно такое решение и предполагалось.

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

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 13:36 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Побережный Александр в сообщении #1211006 писал(а):
Для невыпуклых многоугольников все тоже работает, вроде...
Конечно (в отличие от самопересекающихся). Я сделал оговорку, поскольку уровень сложности этих задач несопоставим: доказать (полу)целостность площади и доказать, что невыпуклый многоугольник можно триангулировать. Или Вы знаете школьное решение для такой триангуляции?

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 13:48 


29/07/08
536
Я сам многоугольник не разбивал на треугольники.
Сначала надо построить прямоугольник, содержащий данный многоугольник и стороны которого лежат на координатной сетке.
Затем вся область, которая не является многоугольником, разбивается на прямоугольные треугольники и прямоугольники, катеты и стороны которых лежат на координатной сетке.
Соответственно, площадь многоугольника равна разности площади большого прямоугольника и всех треугольников и маленьких прямоугольников.

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 14:24 
Заслуженный участник


26/05/14
981
grizzly в сообщении #1211010 писал(а):
Побережный Александр в сообщении #1211006 писал(а):
Для невыпуклых многоугольников все тоже работает, вроде...
Конечно (в отличие от самопересекающихся). Я сделал оговорку, поскольку уровень сложности этих задач несопоставим: доказать (полу)целостность площади и доказать, что невыпуклый многоугольник можно триангулировать. Или Вы знаете школьное решение для такой триангуляции?

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

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 14:47 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Побережный Александр в сообщении #1211014 писал(а):
Затем вся область, которая не является многоугольником, разбивается на прямоугольные треугольники и прямоугольники
Это нужно доказывать. Вообще говоря, эта область может быть устроена достаточно сложно.

-- 20.04.2017, 14:52 --

slavav в сообщении #1211038 писал(а):
Полуцелой является площадь трапеции у которой три стороны параллельны осям. Из таких трапеций составляется любой многоугольник, хотя иногда придётся вычетать площади.
Вершины всех трапеций имеют целочисленные координаты, конечно? А как доказать, что любой многоугольник допускает такую "трапециляцию"?

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 16:27 
Заслуженный участник


26/05/14
981
grizzly в сообщении #1211049 писал(а):
Вершины всех трапеций имеют целочисленные координаты, конечно? А как доказать, что любой многоугольник допускает такую "трапециляцию"?

Это не нужно. Между любой стороной и осью абсцисс строите такую трапецию. Если сторона идёт "слева-направо" берёте её площадь с минусом, иначе с плюсом. Сумма площадей - есть площадь многоугольника (со знаком).
Как доказать это доказать? Разрежем всю плоскость на единичные клетки. Если клетка не целиком внутри или снаружи по отношению к многоугольнику, то разрежем её на несколько частей - одни целиком внутри, другие снаружи. Докажем что если "клетка" внутри многоугольника, то есть ровно нечётное число трапеций которые её содержат, причём положительных на одну больше чем отрицательных. Если клетка снаружи, то таких трапеций чётное число, половина с плюсом, половина с минусом.
К сожалению, моё доказательство привлекает понятие "внутри", которое без топологии строго не определишь. Но можно обойтись "очевидным" заменителем: будем говорить что точка внутри многоугольника, если вертикальный направленный вниз луч пересекает границу многоугольника нечётное число раз. Это дырявое определение, но дыры можно закрыть на школьном уровне.

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 17:30 
Заслуженный участник
Аватара пользователя


09/09/14
6328
slavav
Спасибо, это рассуждение достойно олимпиадного.

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

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 17:41 
Заслуженный участник


26/05/14
981
Вы правы. Площадь со знаком можно определить для любой замкнутой ломаной. Определить и придать некоторый "физический" смысл. Такая площадь будет отвечать всем аксиомам обычной площади, кроме неотрицательности.

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 17:49 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
slavav в сообщении #1211089 писал(а):
Как доказать это доказать?
Сколько ни видел решений школьных олимпиадных задач, нигде подобных утверждений не доказывали. Везде писали "очевидно". Это другой уровень строгости, чужой для духа школьных олимпиад.

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 18:49 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
У самопересекающихся будет две разных площади, одинаково естественные: аналоги "even-odd rule" и "nonzero rule". Для одной из них прокатывает без изменений рассуждение о трапециляции. Для другой нет.

 Профиль  
                  
 
 Re: Рациональная площадь
Сообщение20.04.2017, 19:07 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
ИСН в сообщении #1211150 писал(а):
Для другой нет.
Для другой само утверждение (первое) перестаёт быть верным. Это легко видеть, если сообразить, что площадь самопересечения можно сделать сколь угодно малой.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group