Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Выпуклые четырехугольники
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 17.05.2007, 13:14

Из некой рабочей дискуссии родилась довольно бессмысленная задача.

Как известно (вроде бы), минимальное количество выпуклых плоских четырехугольников, из которого может быть составлена замкнутая поверхность, равно шести. Получается что-то вроде куба. У него чётное число четырехугольных граней. Каково минимальное нечетное количество выпуклых плоских четырехугольников, из которых можно составить замкнутую поверхность?
Если отбросить условие выпуклости, мы можем разделить любую грань куба по диагонали на два вырожденных (в треугольники) четырехугольника, либо на выпуклый и вогнутый четырехугольники - не интересно. А вот когда только выпуклые....
Ответить с цитированием
  (#2 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 17.05.2007, 20:52

сдаётся мне, что таковых вообще не существует...
как доказать - пока не придумал.


импортирован с progz.ru
Ответить с цитированием
  (#3 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 17.05.2007, 21:37

Не понял, что мешает разделить любую грань куба не по диагонали, а линией, параллельной одному из рёбер этой грани?
Ответить с цитированием
  (#4 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 18.05.2007, 05:17

Цитата:
сдаётся мне, что таковых вообще не существует...
как доказать - пока не придумал.
Чего не существует - замкнутой поверхности из нечетного числа плоских выпуклых четырехугольников? Мне тоже сначала так казалось, но это неправда - мне привели доказательство, только оно для какого-то большого числа четырехугольников. Вот я и задумался - каково будет минимальное число?


Цитата:
Не понял, что мешает разделить любую грань куба не по диагонали, а линией, параллельной одному из рёбер этой грани?
Не может точка одного прямоугольника зависать на ребре другого. Поэтому если мы так сделаем - две соседних грани превратятся в вырожденные пятиугольники.
Ответить с цитированием
  (#5 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 18.05.2007, 13:39

Цитата:
Чего не существует - замкнутой поверхности из нечетного числа плоских выпуклых четырехугольников? Мне тоже сначала так казалось, но это неправда - мне привели доказательство, только оно для какого-то большого числа четырехугольников. Вот я и задумался - каково будет минимальное число?
Можно на это посмотреть?


импортирован с progz.ru
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 18.05.2007, 17:23

Цитата:
Как известно (вроде бы), минимальное количество выпуклых плоских четырехугольников, из которого может быть составлена замкнутая поверхность, равно шести. Получается что-то вроде куба. У него чётное число четырехугольных граней. Каково минимальное нечетное количество выпуклых плоских четырехугольников, из которых можно составить замкнутую поверхность?
Ответ простой: 7.
Берём 6 четырёхугольников, составляем из них куб, потом любой из них делим 1 прямой на 2 четырёхугольника.
Ответить с цитированием
  (#7 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 18.05.2007, 22:27

Цитата:
Ответ простой: 7.
Берём 6 четырёхугольников, составляем из них куб, потом любой из них делим 1 прямой на 2 четырёхугольника.
Цитата:
Не может точка одного прямоугольника зависать на ребре другого. Поэтому если мы так сделаем - две соседних грани превратятся в вырожденные пятиугольники.


импортирован с progz.ru
Ответить с цитированием
  (#8 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 18.05.2007, 23:05

Кошмар,
а и посмотри:


Получается, что квадратную область 3х3 из 9 ячеек можно превратить в 8 ячеек.
Минимальная замкнутая поверхность из четырехугольников - куб. Это шесть ячеек. Следующая минимальная поверхность будет состоять из 10 ячеек, и никакие 9 из них не образуют квадрата 3х3. А то бы было 9 ячеек....

Кажется, я понял.... надо взять квадрат 3х3. Свернуть его в подобие трубы треугольного сечения. Загнуть трубу так, что ее открытые торцы-треугольники стыкуются друг с другом. Получаем закрытую поверхность из 9 ячеек. Такой гипертреугольный тор.
Если провернуть на полученном геометрическом теле операцию согласно приведенной схеме, будет 8 ячеек. Это число, правда, уже четное, зато оно больше шести и меньше десяти

Цитата:
Не может точка одного прямоугольника зависать на ребре другого. Поэтому если мы так сделаем - две соседних грани превратятся в вырожденные пятиугольники.
Я так сроднился с этим условием, что уже не могу его внятно донести до людей, не имеющих отношения к.
Попробую еще раз Это задача для сеток. Сетка состоит из многоугольных элементов, в данном случае из четырехугольников. Любое полное ребро любого четырехугольника является так же полным ребром (не частью!) одного из его соседей. Любой узел (пересечение двух ребер) является так же узлом как минимум двух его соседей (иначе получаем вырожденца). Узел (вершина) не может зависать абы где, посреди ребра - в нем сходятся концы ребер.
Ответить с цитированием
  (#9 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 15.08.2007, 21:47

Ну так что?


импортирован с progz.ru
Ответить с цитированием
  (#10 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 16.08.2007, 09:35

А чего?
Ответить с цитированием
  (#11 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 16.08.2007, 11:08

остановились на 9?


импортирован с progz.ru
Ответить с цитированием
  (#12 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 16.08.2007, 12:10

Я меньше не придумал
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 16.08.2007, 13:51

на самом деле я хотел другое у тебя спросить, но потом сам понял ответ, и пришлось хоть что-нибудь спросить, что бы оправдать свой пост.


импортирован с progz.ru
Ответить с цитированием
  (#14 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,275
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 16.08.2007, 15:01

Интересная задача. Пока не придумал ничего хорошего. Но вариант "с дыркой" - как-то не очень..

Upd
Путем трех отсечений от куба вроде построил без дырки. Но все равно девять.
Ответить с цитированием
  (#15 (permalink)) Старый
batman batman вне форума
Member
 
Сообщений: 105
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2007
Talking 14.11.2007, 10:12

1)Получается что минимальное число вообще каких-либо граней ... = 6
2)Возможное число нечётных граней = 9

Сдедовательно , нужно доказать что с 7 гранями - не бывает

Основное доказательство (без деталей) :

Рассмотрим угол , образованный 4 четырёхугольниками (их общий угол) !!!
(
Вкл. пространств. воображение.
4 четырёхугольника :
1 смеж. со 2 , 2 с 3 , 3 с 4, 4 с 1; -у них есть общий угол
-кроме перечисленных , они не имеют общих рёбер между собой
)
пусть остальных 3 граней нет , тогда свободные грани 4 четырёхугольников будут
образовывать замкнутый(пространственный) контур из 8 рёбер .
если спроектировать на плоскость (номер - вершина соотв. 4-х угольника) :
...*1----*12---*2.
../......................\
*14.................*23
..\...................../
...*4----*43----*3.
(свойство (1) :вершины 1 грани расположены последовательно и не лежат в 1 плоскости)


теперь к нему нужно подсоединить остальные 3 четырёхугольника
Утверждение :
Так как фагура замкнутая ,то
оставшиеся 3 грани будут смежны между собой :
1)1 из трёх будет смежан с 2 другими . (3 последовательно)
2)1 из трёх будет смежна с 2 другими , осталные 2 смежны между собой. (3 с общим на всех углом)
Тогда количество рёбер , не задействованных в смежности этих 3 граней ,будет (сум. для всех 3 граней) :
1) = 8 (что и требуется)
2) =6 (не подходит)

Если спроестировать ребра этих 3 граней на плоскость :
...*.---.*---*.
../..../,....../....\
*...,/......./......*
..\./....../....../
...*-.--.*---*.

Рассм. грань :
...*.---.*
../...../
*...../
..\../
...*

3 последовательных вершины обязательно будут пренадлежать 1 грани (1 из 4 упомянутых в начале )
чего по св-ву (1) не допускается
Доказано : замкнутая поверхность с углом ,образованным 4 рёбрами -не канает

P.S. : Если > 4 ребер - док. аналогично но гораздо проще
Получилось , что если граней 7 , то у этого многогранника нет углов , смежных(инцедентных) больше чем с 3 рёбрами ,
А такой многогранник= 6-гранник (параллелепипед)

Update :
под "углами" подразумеваются вершины многогранника
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Выпуклые многоугольники как их делать yamamoto Smalltalk 15 05.05.2006 18:11



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов