✓ Задача, которая сломала Трушина | Комбинаторная геометрия | Ботай со мной  

"Вроде нет, но пока я не знаю почему" - я на всех олимпиадах)

люблю перед сном смотреть видео про математику поражаюсь уму тех кто решает и это мотивирует

Треугольник подходит) Сказано "каждое второе звено || заданному направлению", ну так и нарисуй отрезок сверху вниз, второй - горизонтально, а третий будет завершающим.

Господи, как же хорош стал микрофон

Я никогда не использовал эту фразу,но нигде она так не заходит как тут : "Нuxуя не понял,но очень интересно".

БВ сломался несите нового

Супер интересная задача и понятное объяснение. Спасибо, БВ

Можно подойти через сумму углов многоугольника. При заданных условиях сумма каждых 2х углов 360 (следует из паралельности каждых вторых отрезков и из их направления), то есть сумма всех углов будет 360*n/2 = 180*n. Однако по известной формуле (которую легко вывести), сумма сторон любого многоугольника 180*(n-2). Противоречие.

Да, принцип крайнего - невероятно простая, но очень эффективная вещь! Бывает очень сложная задача, не знаешь как поступиться, но если рассмотреть какой-то "крайний" элемент, то она разваливается)

все ясно)))отличное рассуждение

Класс, красивое решение

Вооу, очень интересно

"Теперь, как аккуратно записать решение этой задачки: "

9:10 Не хрена се магия

Красивое решение )

Супер! Спасибо вам, Борис, за такие решения

вау классная задачка, но сама бы я до этого не додумалась)

очень интересно👁👄👁

Можно проще доказать. Из-за параллельности, сумма двух соседних углов равна 360 градусам, значит сумма углов этого гипотетического n-угольника (можно считать n чётным, так как легко сделать дополнительный "фиктивный" развёрнутый угол) будет равна n*180, а должно быть (n-2)*180 - значит такого не существует.

Не по уведомлению ,а по зову сердца

Мне кажется можно проще доказать, если воспользоваться утверждением о том что при обходе замкнутого самонепересекающегося контура происходит поворот ровно на 360 градусов. А если половина звеньев ориентирована в одном направлении, то развернуться не получится

А теперь таже задача только для Риманово пространства

I think that we get much easier solution if we think about "inside" and "outside" of polygon. If we look at the lowest segment then "outside" is below horizontal segment but for top segment "outside" is above horizontal segment. It is not hard to see that for horizontal segments that has connected with polygon side "outside" stay in the same side. Contradiction.

У замкнутой самонепересекающейся ломаной сумма внешних углов ("суммарный поворот при движении по ней") обязательно равна 360 градусов. Здесь же легко увидеть, что эта сумма всегда равна 0.

Бывают же такие Находки в интернете, такой прекрасный канал) давно я так свой мозг не заставлял думать)

Борис Викторович, не снижается ли концентрация (как учеников, так и учителя) к концу 9 часового интенсива, и как следствие качества? Заранее спасибо.

это векторы, один результирующий во дну сторону, другой в другую, и они не пересекутся лишь если параллельны, а так как результирующие векторы являются произведением неких других, то другие пересекутся, так как в условии есть излом, разное направление

раз каждая вторая линия идет горизонтально слева направо значит рисуем так: 1 линия сверху вниз, 2 слева направо, 3 вверх налево в начальную точку: получился прямоугольный треугольник. Вторая линия идет слева направо, фигура замкнута, задача решена. В условиях не было сказано что кривая начинается с параллельной линии

Можно доказать более конструктивно, по индукции: 1) Для замкнутого четырëхугольника наличие пересечения очевидно; 2) Для любого 2n-угольника с хотя бы одним пересечением введение двух дополнительных сторон не устранит это пересечение.

Вывод можно проще сформулировать: показанным принципом приходим к тому, что минимальная возможная ломаная (из 4 звеньев) должна соответствовать условиям задачи. А это не так. Поэтому не существует ломаной, удовлетворяющей условиям.

Вы самое нижнее звено. Прощайте.

Сочувствую, Вам, Борис. Если так ломать свой мозг, можно ведь и сломать!

Борис, здравствуйте. У вас такая хорошая доска, не подскажите на что нужно опираться при выборе ну или в принципе что посоветуете?

Мне нравится смотреть ваши видео во время завтрака. Сидел, пил кофэ и ел баранки с маком. И на поверхности баранки вроде такое провернуть получается.

Я бы доказывал немного по-другому. нужно построить все возможные случаи, ломаных из 3 звеньев и показать, что при любом расстоянии 4 линия что-нибудь пересекает в попытке замкнуться на 1й точке)) Но такое доказательство выглядит боле полно, мне нравится!

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

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

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

Данная задача легко решается на поверхности шара

По условию задачи нет требования что ломанная должны быть нарисована на плоскости. В трёхмерном пространстве можно нарисовать такую ломанную.

Аж захотел наследить в комментариях: могу нарисовать требуемую кривую на поверхности цилиндра :) З.Ы. Дико увлекательно! Молодец!

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

Можно ролик про Дедекиндовы сечения множеств? Просто это такая важная тема, а видоса нет(((

Метод бесконечного спуска ?

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

Ломай меня! Ломай меня полностью!

БВ, Вы знаете остров Аосима в Японии (остров Cat)?

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

Предлагаю такой ход решения: рассмотреть два варианта: когда диагональный отрезок рисуется вниз от предыдущей горизонтальной и второй вариант вверх. Т.к. эти варианты симметричный можно рассматривать любой из них. Пусть рассмотрим вариант первый, когда второй отрезок, после горизонтального, рисуется в диагональ вниз. Пусть ось Х направлена вдоль первого горизонтального отрезка. Начало координат - это точка первого отрезка, куда нужно вернуться, чтобы замкнуть кривую. Для выхода на начальную точку, следующий отрезок должен рисоваться в диагональ, причем координата x второй точки первого отрезка должна быть строго отрицательна, чтобы следующие отрезки, рисующийся с приращением координаты x, смог закончиться на координате 0,0. После вычерчивания второго горизонтального отрезка мы видим, что для возврата в исходную точку получаем пересечение третей линии со второй, что противоречит условию. Понятно, что нельзя прийти к началу координат за 1 отрезок, также понятно, что нельзя выйти на начало координат с помощью n отрезков, из-за пересечения последнего отрезка с номером n с отрезком n-1 и т.д.

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

Изначальное условие задачи в описании? Буду использовать для параллельных сонаправленных отрезков слово "оранжевый", а прочие будут наклонными или косыми. Подобное построение условия ваще предполагает, что начинаем рисовать мы всегда с оранжевого. Иначе просто рисуем наклонный, затем оранжевый, затем вторым наклонным замыкаем. Ну или неважно сколько нарисуем, если мы начали с наклонного, то сможем замкнуть другим наклонным, если правильно отрисуем. Вывод: задача предполагает всегда начинать с оранжевого. Тогда мы рисуем оранжевый. АВ. Дальше нам надо нарисовать любой наклонный, чтобы начать процесс рисования ломанной. Хорошо, отрисовали. ВС. Допустим вверх (угол поворота больше нуля). Опять нарисовали оранжевый. СЕ (потому что мне влом переключаться и делать латинскую Д, а АВС и Е буквы с русскими совпадают окей). И теперь главный мысль - откидывая пересечение, если взять наш наклонный, то мы больше никогда не сможем попасть в область, очерченную нашим наклонным отрезком и лучами, начинающимися в точках нашего наклонного отрезка, направленными в противоположную от "разрешённого", скажем так, движения сторону - влево. Ведь мы не можем пересекать нарисованное, а значит новый косой будет с углом поворота меньше 180 градусов, и углом больше -(180гр-СЕВ). Строго, иначе пересечемся через В или ляжем на СЕ, читай пересечем СЕ. И даже если после оранжевого отрезка СЕ мы нарисуем такой косой ЕК, чтобы К была на той же прямой, на которой лежит АВ, то ситуация просто повторится и мы НЕ СМОЖЕМ после нового оранжевого КМ нарисовать новый косой МО с углом больше или равном углу 180гр-ЕМК, или с углом меньше меньше или равном -180гр. (если что вдруг - угол поворота если положительный, то поворачиваем против часовой, отрицательный - по часовой, относительно горизонтали, да кому я тут объясняю, и так ясно же). И каждый новый косой отрезок увеличивает эту область соответственным образом (собой и параллельными оранжевому отрезку лучами из концов косого в левую сторону). А после каждого косого отрезка мы сдвигаемся строго вправо от него. И так далее. Таким образом попадание в область, в которой находится изначальная точка А невозможно, а потому и замкнуть не получится, если следовать правилам рисования без пересечения. С другой стороны нарисовать ломанную по правилам с пересечением проще простого (4 точки А В С Е, где АВ параллельно и сонаправленно СЕ, а ВС и ЕА - пересекающиеся отрезки), значит нарисованная Федей ломанная с пересечением.

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

А если решать эту задачу в трехмерном пространстве, то ответ кажется очевидным!

В рассуждениях не использовался тот факт, что первое звено (с которого мы начинаем идти по ломаной) должно быть направленное и параллельное некоторой прямой. Если в качестве первого звена брать произвольную прямую, то как отмечали ребята с комментария ниже, такая замкнутая прямая существует и образует, например, прямоугольный треугольник

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

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

задачка решается в объёме! 3 параллельные +3 скрещивающиеся отрезка

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

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

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

А по факту решается задача у которой каждое первое из двух звеньев параллельное и направленное.

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

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

Очень короткое изложение решения. Пусть AB одно из верхних звеньев а CD-одно из нижних. Вся наша ломаная находится внутри полосы из двух параллельных прямых. Из точки B по какой-то НЕПРЕРЫВНОЙ линии попадаем в точку C (именно в C, а не в D) . Но нам надо ещё из точки D попасть в точку A, непересекая нашу НЕПРЕРЫВНУЮ линию (BC), что не сможем делать--не позволяет теорема ЖОРДАНА. точки A и D находятся в разных «полуполосках»,,.

Метод бесконечного спуска!

ну.. получается, что мы должны узнать есть ли, 1-мерная (связая) цепь, которая удовлетворяет неким условиям, но при этом, границы у неё не должно быть. Чувствую, что нет такой, ведь у цикла должны быть 1-цепи, что поворачиваются в противоположную сторону..Пересечения в даном примере приводят к созданию циклов.

А может ли быть такая ломаная со счетным количеством звеньев?

А через неравентсво суммы векторов нулю это не решается?

Можно если сделать их в 2 плоскосях с объёмом, то из 3 можно сделать что бы начальная и последняя как бы ложились друг на друга, а это, наверное, можно сказать замыкало бы их, но это меняет задачу, как я понял

По цилиндру задача решается

Скорее всего, в условии пропущено, что начинать рисовать надо именно с горизонтального отрезка. Потому что без этого условия: рисуем вертикальный отрезок, затем горизонтальный слева-направо, затем замыкаем треугольник. Или, даже больше, вертикальный отрезок - затем вправо рисуем пилу и с последнего зуба замыкаем. |-------- | / | / | / | / | / | ------ | / | / | / | / | / | / | /

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

0:00 -> 0:16 естественно можно! в не евклидовом пространстве :)

Интересно, есть ли такая ломанная, если звеньев может быть бесконечное число?

Нос самой нижней из параллельного семейства соединен с хвостом самой верхней. И наоборот. А это пересечение, этого не может быть.

Задача № 2 (ПВГ 9 класс) В выражении 0 ∗ 1 ∗ 2 ∗ 3 ∗ … ∗ 99 вместо «звездочек» можно ставить знаки «+» или «-». Сколько различных положительных чисел можно получить таким образом? Решение: Если сложить все числа , то получится 4950, но если перед какими-то числами ставить "-", то мы их не только вычитаем, но и не прибавляем к изначальной сумме, то есть если мы перед каким-то числами поставили знак "-", и сумма этих чисел n, то вычли 2n из числа 4950, т.е получили число 2 * ( 2475 - n ), но тогда можно получать только четные числа в интервале от 0 до 4950, а их 2475 (0 не считается) Ответ: 2475 ОФИЦИАЛЬНЫЙ ОТВЕТ: 4950 Я не понимаю как можно его добиться, возможно организаторы имели ввиду не только положительные числа. Прошу тех, кто понимает, где ошибка в моем решении, указать на нее. БУДУ ОЧЕНЬ БЛАГОДАРЕН И ПРИЗНАТЕЛЕН! Очень хочется пройти на закл, но баллов не хватает

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

Достаточно легко понять что сумма 2 соседних внутренних углов при параллельных прямых 360 градусов. А значит у n-угольника сумма углов 180 n. А это очевидно невозможно. Ч. Т. Д.

Такая ломаная существует. Она существует на поверхности шара, то есть, в неэвклидовой геометрии: спускаемся с полюса до экватора, проходим по экватору путь, равный половине экватора, возвращаемся в полюс)) В задаче же не сказано какую геометрию использовать))

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

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

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

Могу нарисовать замкнутую ломаную, у которой второй и все имеющиеся чётные отрезки горизонтальные и идут слева направо. Кстати, а можно считать таковой ломаную ABA?

Лучше поздно, чем никогда. В комментах не нашел, поэтому решил написать. Доказать очень просто через формулу Эйлера для плоских графов. Если правильно помню, там число Вершин * 3 - 6 = число Ребер. Если нет, то граф нельзя уложить на плоскость. Но, для этого нужно доказать, что число ребер - чётно. Здесь это следует из условий задачи. Ведь, если бы не следовало, то можно было бы нарисовать треугольник.

Делаем каждое второе звено нулевой длины (ограничения на длину нет) - задача решена

Задача легко решается на поверхности тора, например

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

Если в "ямке" есть вершина, то самое нижнее левое звено продолжаем до пересечения с левым берегом "ямки". Не очень понятно, а что мы делаем с самым нижним звеном "ямки". Мы же не можем его просто выкинуть. Без объяснения этого момента, доказательство не выглядит убедительным.

а треугольник, у которого основание - горизонтальное второе звено, а стороны - первое и третье, не подходит? и почему мы пришли к 4-угольнику, а не треугольнику?

Можно через векторы доказывать.

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

Это очевидно. Для тех наклонных что кончаются выше начальной точки вводим понятие "право". Это то что ниже и правее ее конца. Очевидно что в область "лево" нельзя попасть без самопересечений.

ты кажется всë усложнил)

Интересно, справедливо ли это на шаре/торе, или только на плоскости?

Тут можно уничтожить с помощью высшей математики. Пусть существует такая ломаная. Тогда по крайне (не)очевидной теореме Жордана она делит плоскость на 2 компоненты связности, причём одна из них ограничена, она и будет многоугольником, ограниченным этой ломаной. Затем тоже по (не)очевидной теореме о триангуляции этот многоугольник разбивается диагоналями на n-2 треугольника, значит сумма его углов (n-2)*180 градусов. Можно считать звенья ломаной наклонными (те, которые не сонаправленны по условию), иначе просто три подряд горизонтальных ребра можно объёдинить в одно. Сумма углов многоугольника у наклонного ребра 180 или 540 градусов из параллельности и сонаправленности смежных сторон. Число звеньев чётно, если оно не делится на 4, т.е. равно 4k+2, то сумма углов 4k*180 градусов, с другой стороны это сумма 2k+1 числа, каждое из которых 180 или 540 градусов, то есть нечётное число * 180 градусов. Противоречие. Если число звеньев кратно 4, то просто изменим ломаную в любом угле - добавим 2 звена (фиксируем вершину, она удалена от всех звеньев, кроме 2, на положительное расстояние (расстояние между точкой и компактом - объединением всех звеньев, кроме 2), затем в окрестности радиуса меньше этого расстояния заменяем два звена ломаной x, y - по x «не доходим до вершины», затем поворачиваем параллельно y, проходим немного и поворачиваем параллельно x и доходим до y. Новая ломаная всё ещё удовлетворяет условию, но количество звеньев у неё уже не кратно 4. Противоречие.

На цилиндре рисовать такие ломаные проще простого.=)

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

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

А почему нельзя просто сказать, что у замкнутой ломаной сумма внешних углов должна быть 360°, и горизонтальные сегменты всегда эту суммы возвращают к 0°, а другие не могут добавить более чем 180°

А якщо площина замкнута?