Математическое и загадочное

[Soft]

Всё верно, посты склеились. Адрес сообщения #1269 

[Ig0r]

Всё верно, посты склеились. Адрес сообщения #1269 

Они не склеиваются у Е.К., но адрес правильный 

[E.K.]

Ой, сорри, увидел.. Приношу извинения!

[E.K.]

2) На плоскости есть 2n точек, никакие две точки не совпадают, никакие три не лежат на одной прямой. Точки соединены n отрезками: первая соединена со второй, третья - с четвертой и т.д. Мы можем взять любую пару пересекающихся отрезков AB и CD и заменить их на пару отрезков AC и BD (общее количество отрезков не изменится). Всегда ли мы можем такими манипуляциями добиться того, что у нас останется n отрезков, никакая пара из которых не пересекается?

Что-то я к этой загадке даже как подступиться не понимаю.. Помогайте, SOS.

[E.K.]

Ой, а решение-то совершенно простейшее.. Что-то у меня на фоне пандемий-эпидемий и домашней работы (в смысле карантина дома) совсем мозги ослабли.

 

Переформулирую задачку. Можно ли 2n точек (не совпадают, три не на прямой) соединить отрезками таким образом, чтобы отрезки не пересекались?

 

Элементарно. Берём все "внешние точки", то есть строим выпуклый многогранник, внутри которого лежат все остальные точки. Соединяем "внешние точки" попарно отрезками (если остаётся лишняя - оставляем её, потом пригодится). Поскольку за пределами многогранника точек нет, то ни при каких условиях эти отрезки не смогут пересекаться с другими отрезками. Выкидываем эти точки с отрезками. Повторяем действие до тех пор пока не останется только пара точек. Торжественно бьём в барабаны, наливаем шампанское, соединяем их отрезком - всё. Задача решена.

[E.K.]

Однажды под новый 2020й год злые модераторы фанклуба напились пива, забанили двух фанклубней и заставили их есть огромную шоколадку размером 2019x2020 плиток. Все плитки одинаковые, обычные, коричневые, но среди них есть одна тёмно-коричневая (её видно) с "вкусным" сюрпризом (чили, пурген, крысиный яд или типа того). Фанклубни поочерёдно отламывают шоколадку по линии слома и съедают отломанную часть.

 

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

 

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

[santax]

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

Например как бы я рассуждал, играя вторым игроком.

В конце, чтобы я выиграл перед ходом первого игрока шоколадка должна иметь вид

 

1) OXO или 2) XO

OO

 

Для первого варианта плитка X может быть где угодно, кроме углов шоколада. Второй вариант - любое расположение плитки X.

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

Поэтому пока отбросим (временно или навсегда?) идею превращения плитки в вариант #1.

 

Смотрим теперь разные ходовки:

1. Плитка X находится в углу шоколадки.

A. Первый игрок отломил 2018/2019 рядов шоколадки и оставил один ряд с плиткой X на конце. Я отламываю плитку X и отдаю её второму игроку, оставив себе вкусный шоколад. Допустимо, но маловероятный расклад.

Б. Первый игрок отломил 2017/2018 рядов, оставив 2 ряда с плиткой X на конце. Я ломаю шоколад до квадрата 2*2 и привожу к варианту #2.

В. Игрок ломает N (от 1 до 2016/2017) рядов с любой стороны. В этом случае нам нужно не попасть самим на место первого игрока в позиции А и Б. Поэтому мы доламываем шоколадку по этой же линии сломв, что и первый игрок, оставив для него шоколадку из 3х рядов с плиткой X на конце. Теперь у первого игрока есть несколько вариантов: ломать шоколадку в этом же ряду, тогда он опять попадёт в позиции А и Б. Либо ломать шоколадку по противоположному ряду: если он ломает шоколадку по максимуму, оставив 3*1, то он проиграл (позиция А).

 

-- сам уже запутался в терминологии, а вы?

 

Если ломает шоколадку до 3*2, то я ломаю шоколадку до вида 2*2 и вновь выигрываю.

Если ломает шоколадку до вида 3*3, то проигрываю Я!!! Значит вариант В НУЖно пересмотреть!!!

 

=======

А вот кстати и стратегия вырисовывается: нужно всегда стараться шоколадку привести к квадратному виду с плиткой X в углу! Тогда мы в любом случае сможем заставить игрока съесть плитку X.

 

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

 

1. Плитка X ,находится в углу шоколада изначально. => я делаю шоколад квадратным и выигрываю!

2. Плитка X на длинном краю шоколада (2020 плиток), но не в углу, а вторая с краю. => я делаю шоколад квадратным с плиткой X в углу и выигрываю.

3. Плитка X на длинном краю шоколада где-то там => Думаю, думаю... Думаю.. А что я думаю-то!!!

 

Я просто независимо от того, где расположена плитка X, делаю шоколад всегда квадратным и выигрываю!

 

То есть выиграет первый игрок, если всегда будет из шоколада делать квадрат (N*N плиток) во время своего хода. В этом случае плитка X достанется второму игроку.

Изменено 7 апреля, 2020 пользователем santax

[StarCuriosity]

Переформулирую задачку. Можно ли 2n точек (не совпадают, три не на прямой) соединить отрезками таким образом, чтобы отрезки не пересекались?

Хм. Любопытное решение, сам по-другому решал. А почему это задача эквивалентна?

[E.K.]

Хмм... Да, действительно. Почему эквивалентно?.. Ведь алгоритм оптимизации отрезков вдруг возьмёт да и зациклится? Тогда вот так:

 

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

[E.K.]

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

 

000000

000X00

[santax]

Про шоколадку я уже выше решил

Изменено 8 апреля, 2020 пользователем santax

[E.K.]

Нет. "Квадратить" не всегда работает. А вдруг плитка в позиции 1000x10, а второй отламывает 2019x50? Чтобы это "оквадратить" надо кусать с двух сторон.

[santax]

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

[Борис Прокофьев]

2) На плоскости есть 2n точек, никакие две точки не совпадают, никакие три не лежат на одной прямой. Точки соединены n отрезками: первая соединена со второй, третья - с четвертой и т.д. Мы можем взять любую пару пересекающихся отрезков AB и CD и заменить их на пару отрезков AC и BD (общее количество отрезков не изменится). Всегда ли мы можем такими манипуляциями добиться того, что у нас останется n отрезков, никакая пара из которых не пересекается?

А вот если такая мысль:

Процедура замены AB и CD на AC и BD уменьшает угол между ними. То есть если получившиеся AC и BD снова пересечь, то угол между ними будет меньше, чем между исходными AB и CD. Если эту процедуру (заменять и пересекать) применять к одним и тем же отрезкам бесконечно, то угол между ними будет стремиться к 0, а отрезки к тому, чтобы наложиться друг на друга.

Соответственно если у нас на плоскости n отрезков и мы будем последовательно заменять все пересекающиеся пары, то отрезки постепенно будут выравниваться относительно друг друга (стремиться к тому, чтобы стать параллельными). А поскольку мы имеем дело именно с отрезками (т.е. конечной длины) то обязательно наступит момент когда они перестанут пересекаться.   

[StarCuriosity]

А вот если такая мысль:

Процедура замены AB и CD на AC и BD уменьшает угол между ними. То есть если получившиеся AC и BD снова пересечь, то угол между ними будет меньше, чем между исходными AB и CD.

 

Насколько я понял, неизвествно, что будет с другими углами при замене AB и CD на AC и BD. Вдруг они вырастут; соответственно, неочевидно (для меня, по крайней мере), что эта процедура закончится.

Изменено 10 апреля, 2020 пользователем StarCuriosity