Геометрическая задача. Дополнено важными условиями.

По сути нужно доказать, что невозможна ситуация с построением невыпуклой незаполненной области. Возможно, достаточно рассмотреть все несколько ситуаций взаимного расположения пяти прямоугольников и показать, что невозможна расстановка с невыпуклой незаполненной областью. А затем показать, что случаи с бОльшим количеством прямоугольников сводятся к случаям с пятью.

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

Блин, ну привели Вам доказательство же... что неясно?

Там доказать самому легче, чем описать тут на форуме.

Начни с того, что если область не прямоугольная, то у неё непременно есть угол 270 градусов. Этот угол образуется каким-то одним прямоугольником. Если начать отсюда плясать, не забывая, что область должна быть неуменьшаемая, то все легко получается.

В ту тему не могу, зачем ты её ограничил? 16.04 ff46

http://savepic.ru/9728914.png

Формализовать данное доказательство достаточно просто. От противного - допустим, при заполнении останется дырка невыпуклой формы. Легко видеть, что для того, чтобы конструкция оставалось жесткой, каждая сторона ограничивающих дырку прямоугольников должна опираться как минимум на один соседний прямоугольник.При обходе дырки по периметру в любом направлении видно, что данное условие невыполнимо - в случае невыпуклой фигуры как минимум одна сторона не опирается ни на что, кроме дырки. Следовательно, дырки могут быть только выпуклой формы - то есть прямоугольные. ЧТД

Не понял. В какую ты тем и ЧТО не можешь? Что я и как ограничил?

Классное доказательство, тянет на ответ )

http://s019.radikal.ru/i600/1605/d9/8697ca8ed966.jpg

N прямоугольников. Максимально увеличь каждый. Стороны или упирается в сторону другого прямоугольника или двигается неограничено. Остаются только прямоугольники. Добавляешь красный. Пересечение прямоугольника и конечного множеста прямоугольников = конечное множество прямоугольников. Всё.

Не работает для бесконечного N.

Если на правой картинки самый правый прямоугольник растянуть вверх до предела, то он примкнёт к самому верхнему прямоугольнику на этой картинке и останется прямоугольное пятно.

Если на правой картинки самый правый прямоугольник растянуть вверх до предела, то он примкнёт к самому верхнему прямоугольнику на этой картинке и останется прямоугольное пятно.

Ну,собственно это и иллюстрирует картинка. В общем, (и тут Остапа понесло ;) ) совсем строгое доказательство. Снова от противного: Пусть существует красная дырка невыпуклой формы с N вершинами из которых M - выпуклые. Она ограничена прямоугольниками, которые касаются ее своими ребрами. Общее количество ребер касания - K. Легко видеть, что всегда M<=N<=K. Ребро касания закреплено жестко и не может двигаться, если оно опирается как минимум на одну выпуклую вершину красной дырки. То есть, вся конструкция будет жесткой только при строгом равенстве M=N=K т.е. все вершины выпуклые - дырка имеет прямоугольную форму. ЧТД

Как твоё решение описывает этот случай? Интересует невыпуклая вершина.

https://sketch.io/render/sk-573b4fac77530.png

Как твоё решение описывает этот случай?

Да никак. Этот случай не подходит под условие задачи. Неравенство M<=K справедливо только для «предельных» устойчивых конструкций, когда каждое ребро красного многоугольника полностью покрыто ребрами окружающих прямоугольников. «Непредельные» случай (один из которых изображен на рисунке) Кэп отбрасывает, поскольку легко видеть, что если хотя бы одно ребро красной фигуры не касается полностью ребер черных, то ребра, прилегающие к его вершинам неустойчивы

Этот случай не подходит под условие задачи.

В каком месте?

В каком месте?

Неравенство N<=K справедливо только для «предельных» устойчивых конструкций, когда каждое ребро красного многоугольника полностью покрыто ребрами окружающих прямоугольников. «Непредельные» случай (один из которых изображен на рисунке) Кэп отбрасывает, поскольку легко видеть, что если хотя бы одно ребро красной фигуры не касается полностью ребер черных, то ребра, прилегающие к его вершинам неустойчивы

Мы ведь пытаемся доказать для устойчивых состояний, не так ли?

Мы ведь пытаемся доказать для устойчивых состояний, не так ли?

Нет. Для всех.

Нет. Для всех.

Значит, кто-то из нас двоих неправильно понял условие задачи и этот кто-то - явно не я. Ибо

ЗАДАЧА Доказать, что любая система чёрных может отработать так, что либо закроет красный целиком, либо оставит на нём прямоугольные дырки - одну или более.

То есть, если принимать во внимание все непредельные случаи, когда черным есть куда расширяться дальше, то вообще задача теряет смысл - таких случаев можно придумать overдофига и дырки будут самой разнообразной формы. Я, конечно, не рассматриваю вариант, что вы все прекрасно понимаете, а просто троллите меня. ;)

Очевидно, что черным всегда есть,куда расширяться дальше.

В моём примере можно легко добавить еще 2 прямоугольника, ограничивая движение.

В моём примере можно легко добавить еще 2 прямоугольника, ограничивая движение.

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

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

У тебя с логикой проблемы.

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

У меня всё.

Если это такой достойный слив, то я оценил. :-D

У тебя с логикой проблемы.

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

И что? Я привел решение задачи. Этот пример иллюстрирует неправильность решения мбк. Это не контрпример для задачи.

это не решение, если не соответствует условию.

это не решение, если не соответствует условию.

Ты хоть сам понял, что написал?

Решение вот тут: Геометрическая задача. Дополнено важными условиями. (комментарий)

Не так выразился, я имел ввиду что твоя картинка адресованная МВК не соответствует условию.

В каком месте? Есть 3 черных прямоугольника, 1 красный. Черные не пересекаются.

ЗАДАЧА Доказать, что любая система чёрных

Любая система

Можно хоть N = 1 взять, но этот случай тривиален.

Но в условиях они могут расширяться, покрывая красный. После расширения тонкого прямоугольника вниз, условно можно сказать что черные соприкасаются со всеми гранями красного и получается как у МВК

Она ограничена прямоугольниками, которые касаются ее своими ребрами. > Общее количество ребер касания - K. Легко видеть, что всегда M<=N<=K. > Ребро касания закреплено жестко и не может двигаться, если оно опирается как минимум на одну выпуклую вершину красной дырки. То есть, вся конструкция будет жесткой только при строгом равенстве M=N=K т.е. все вершины выпуклые - дырка имеет прямоугольную форму. ЧТД

Но в условиях они могут расширяться, покрывая красный.

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

После расширения тонкого прямоугольника вниз,

Это должно описывать решение задачи, а не ты, чтобы подогнать под «решение».

Пусть расширяются.

Дак тогда решение МВК правильное.

Это должно описывать решение задачи, а не ты, чтобы подогнать под «решение».

так я и написал, что ты привел не правильную картинку, не соответствующую первоначальному заданию.
Что и до этого сказал МВК

Как твоё решение описывает этот случай?

Да никак. Этот случай не подходит под условие задачи.

Решение вот тут:

Эээээ... Где тут решение?

N прямоугольников. Максимально увеличь каждый. Стороны или упирается в сторону другого прямоугольника или двигается неограничено. Остаются только прямоугольники. Добавляешь красный. Пересечение прямоугольника и конечного множеста прямоугольников = конечное множество прямоугольников. Всё.

Не работает для бесконечного N.

На самом деле это просто формулировка топиковой задачи другими словами. А решения тут никакого нет. Тем более вы ж сами писали

Максимально увеличь каждый.

Ваша картинка даже ему не соответствует - как минимум пара прямоугольников увеличивается до закрытия красного - т.е. не максимально. Мое же докозательство именно для случая максимального увеличения.

Дак тогда решение МВК правильное.

Как оно описывает поведение невыпуклого угла? Никто мне так и не ответил на этот вопрос.

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

Приведи цитату из первоначального поста, которое запрещает такое размещение.

Как твоё решение описывает этот случай?

Да никак. Этот случай не подходит под условие «РЕШЕНИЯ».

У вас проблемка в голове, господа. Вы не можете понять, что вы так и не доказали, что любой случай из задачи сводится к ««предельным» устойчивым конструкциям», которые являются лишь частным случаем.

Ясно. Человек, который не понимает, что такое начальные условия, мне что-то рассказывает.

А, вон оно что

У вас проблемка в голове, господа. Вы не можете понять, что вы так и не доказали, что любой случай из задачи сводится к ««предельным» устойчивым конструкциям», которые являются лишь частным случаем.

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

Впрочем

Приведи цитату из первоначального поста, которое запрещает такое размещение.

запросто

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

Нарисованная вами система может отработать так, Кэп гарантирует это - чтд

Более того, если внимательно перечитат ваше «доказательство», можно увидеть безумную чушь:

Пересечение прямоугольника и конечного множеста прямоугольников = конечное множество прямоугольников

Вы ж своим примером эту свою фразу опровергаете - пересечение красного прямоугольника и черных прямоугольников у вас явно не «конечное множество прямоугольников» Или вы подразумевали «фигура, образованная объединением конечного множества прямоугольников»? Так такого точно в условии нет :-D))

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

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

Я не понял, что ты подразумеваешь под «предельной устойчивой конструкцией», так как у тебя ребро ограничивает только одну дырку, хотя это может быть не так. Твоё решение локально, и, скорее всего, его можно доработать.

Вполне себе глобально. Еще раз поясняю - ребро закреплено устойчиво если оно хотя бы в одной выпуклой вершине упирается в другой прямоугольник - что тут не так? В невыпуклой вершине ей просто некуда упираться - со всех сторон там черных прямоугольников нет по определению.

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

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