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

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

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

А, по-моему, из построения следует, что угол именно уменьшится: переход от АВ к АС это уменьшение исходного угла на ⦟CAB какими бы ни были отрезки (C всегда будет слева от AB раз они пересекаются). Аналогично переход от DC к DB это уменьшение исходного угла на ⦟CDB. Итого новый угол (зелёный) будет всегда меньше старого (чёрный) на величину ⦟CAB +⦟CDB.

[E.K.]

Нет, ерунда получается.. А вдруг там ещё точка заполучилась?

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

Нет, ерунда получается.. А вдруг там ещё точка заполучилась?

А что не так? Условия задачи предполагают применение искомой манипуляции ко всем пересекающимся отрезкам, в том числе и вновь "заполученным". Я так понял прочитанное.

[StarCuriosity]

А, по-моему, из построения следует, что угол именно уменьшится: переход от АВ к АС это уменьшение исходного угла на ⦟CAB какими бы ни были отрезки (C всегда будет слева от AB раз они пересекаются). Аналогично переход от DC к DB это уменьшение исходного угла на ⦟CDB. Итого новый угол (зелёный) будет всегда меньше старого (чёрный) на величину ⦟CAB +⦟CDB.

 

ABCD.JPG

 

Угол CAB,  несомненно, уменьшится. Но не может ли однвременно увеличиться какой-нибудь другой угол CAE или BDF.

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

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

Извиняюсь, теперь я не понял: угол САВ? уменьшится? Букв E и F вообще на рисунке нет...

 

Какие углы уменьшатся, какие увеличатся наглядно видно на примере ножниц:

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

 

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

 

[E.K.]

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

[E.K.]

Теперь надо с шоколадкой разбираться. Для начала простейшие случаи. "Лента" 1xN, плитка с сюрпризом где-то посередине, но не точно посередине.

 

0...00X000...0

 

Тактика простая: 1й выравнивает края, "сюрприз" остаётся точно посередине, затем первый просто повторяет укусы второго. 1й побеждает. Если же "сюрприз" сразу оказался посередине, то выигрывает второй.

 

"Сюрприз" в углу:

 

00 ... 0

...

00 ... 0

X0 ... 0

 

Этот случай уже разобран, решение: "квадратить" шоколадку и продолжать её квадратить до тех пор, пока не получится "лента" 1xN или квадрат 2x2. 1й победил.

 

"Сюрприз" второй с края:

 

000 ... 0

...

000 ... 0

0X0 ... 0

Если он по длинной стороне, то 1й квадратит, откусывая самую левую колонку. Получили квадрат с X в самом углу. 1й победил. Но если X по короткой стороне... то метод квадратов всё равно работает, просто эндшпиль немного другой:

 

Если второй оставляет первому "ленту" 1xN, то понятно - кусь всё-1 и второму 0X0 с сюрпризной плиткой посередине. Если второй оставляет первому 2xN, то он кусь и оставляет 2x2, выиграл. Если 3xN, то отдаёт второму 0X0 - тоже победил. Если же всё скатывается к четвёрке..

 

0000

0000

0000

0x00

 

То 1й всё равно побеждает. Если второй оставляет ленту 1x4, то первый ему отдаёт 0X0. Если второй оставляет 2xN, то первый возвращает ему квадрат 2x2. Иначе второй может куснуть ещё четырьмя способами:

 

0000    ....   0000    ....   0000    ....   0000    ....   0000    ....

0000 => .000   0000 => ....   0000 => ....   0000 => ....   0000 => .000

0000    .000   0000    00..   0000    ....   0000    ....   0000    .000

0x00    .x00   0x00    0x..   0x00    0x0.   0x00    0x0.   0X00    .X00

 

Так.. С углами разобрались.

[E.K.]

Теперь ещё один маловероятный случай. Плитка с сюрпризом случайно оказалась точно посередине стороны 2019. Тогда первый просто "центрует" сюрприз по стороне 2020 - всё. Второй получает ситуацию, когда сюрприз ровно по центру по обеим сторонам. Чтобы он не делал - первый просто повторяет его шаги. Вплоть до последней плитки с крысиным ядом, который достаётся второму.

 

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

 

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

 

0...00000000...00

...

0...00000000...00

0...000X0000...00

0...00000000...00

...

0...00000000...00

 

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

 

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

 

0...0000X00000...0

 

Что может предпринять второй? Откусить всё с одной стороны. Отлично, включаем "перетягивание каната" по другой стороне. Он может откусить почти всё, оставив 2xN. Аналогично, переключаемся на вторую ось координат. Он оставляет три плитки. Ответ простой: 3-X-2.

 

000X00000...0 => 000X00

 

Вариант "выровнять" 00X00 не рассматривается, это сразу проигрыш. Второй может: 0X00, 000X0, 000X. В любом случае оставляем 0X и переключаемся на вторую ось координат.

[E.K.]

Итак, получили что-то вот такое типа 2xN, причём X не точно по центру!

 

0...00000000...0

0...000X0000...0

 

Ход второго:

2й откусывает верхнюю ленту => первый выравнивает края нижней ленты и выигрывает.

2й откусывает всё с одного края => первый кусь 2x2 и всё.

2й кусь почти всё с одного края, оставив 1 плитку:

 

0000...0

0X00...0

 

1й оставляет 2x2 и выигрывает.

 

2й кусь +2 с края:             1й кусь 6x2, дальше очевидно:

 

00000...0      000000

00X00...0      00X000

 

2й кусь +3 с края:            1й кусь 6x2, но наоборот:

 

000000...0     000000

000X00...0     000X00

 

2й кусь +4 с края:             1й кусь 10x2:

 

0000000...0    0000000000

0000X00...0    0000X00000

 

Далее второй либо ровняет 4-X-4, либо откусывает верхнюю ленту - и то, и другое = проигрыш; либо же загоняет себя в также проигрышную ситуацию 2x(4-X-3) => укус первого 2x(2-X-3).

[E.K.]

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

 

Что-то там как-то много вариантов.. Беру тайм-аут, да и шоколад в больших объёмах не самая диетическая закуска

[E.K.]

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

 

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

 

Алгоритм понятен? Теперь задача. Цитирую как получил:

 

Лягушка сидит на берегу реки. Хочет попасть на противоположный берег. В реке плавает N кувшинок, все кувшинки выстроены в линию между лягушкой и противоположным берегом. Лягушка прыгает на случайную кувшинку перед ней или на противоположный берег с одинаковой вероятностью. Если приземлилась на берег, то она прекращает прыгать. В противном случае делает ещё один прыжок на случайную кувшинку из оставшихся перед ней. Вопрос: сколько прыжков в среднем она совершит?

 

[E.K.]

Баш жжот:

https://bash.im/quote/460853

 

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

 

Что делать Лернейской Гидре? У которой было... "У гидры было множество голов, по разным версиям мифа 7, 9, 50 или даже 100 шей со змеиными головами вырастали из одного туловища" - Википедия.

[Fireman]

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

 

Пусть для удобства длина шеи Горыныча будет 1

 

для 1х головы все просто - она уже самоизолирована

 

для 2х голов это расстояние равно вытянутым шеям, т.е. 2м

 

если у Горыныча 3 головы - то они должны расположиться в вершинах правильного треугольника, вписанного в окружность, радиус которой равен длине шеи

 

 

расстояние между головами в этом случае будет sqrt(3)

 

если у Горыныча N голов, то они должны расположиться в вершинах правильного N-угольника, вписанного в окружность, где радиус окружности равен длине шеи (т.е. единице)

в этом случае расстояние между головами будет считаться как:

 

L = 2sin(pi / N)

 

для N = 4 L = sqrt(2)

для N = 10 L ~ 0,61

 

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

 

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

Это наступает когда

L >= 1

L = 2sin(pi/(N-1))

 

Откуда

N = 1 + pi/(pi/6) = 7

 

Т.е. когда у Горыныча 7 голов одну надо прижать

 

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

 

 

Если Горыныч живет не в 2D измерении, а в честном 3D, то для 4х голового варианта головы должны находиться в вершинах правильного тетраэдра, вписанного в сферу радиуса равного длине шеи.

А как быть с большим N? Тут немного сложнее, поскольку правильных многогранников можно пересчитать на пальцах одной руки

 

 

 

Что делать Лернейской Гидре? У которой было... "У гидры было множество голов, по разным версиям мифа 7, 9, 50 или даже 100 шей со змеиными головами вырастали из одного туловища"

 

Рубить Гидре головы (у нее же после каждой отрубки на месте одной вырастало 2) до тех пор, пока счетчик голов не переполнится и не обнулится (для 8-битной Гидры надо всего лишь нарастить 256 голов )

 

 

 

А теперь лягушки

 

Если я правильно понял задачу (а я ее наверное все таки не правильно понял) лягушка с вероятностью 50% выпрыгнет на берег за 4 прыжка

 

Всего имеется M кувшинок и берег, значит вероятность попасть на берег

 

1/(M-1)

 

-1 потому что на одной кувшинке лягушка все таки сидит (рассмотрим случай, что она сидит на кувшинке изначально)

 

тогда не выпрыгнуть на берег

 

1 - 1/(M-1)

 

вероятность не выпрыгнуть на берег за K прыжков

 

(1-1/(M-1))^K

 

вероятность выпрыгнуть на берег за К прыжков

 

1 - (1-1/(M-1))^K = P

 

Тогда для K получаем

 

K = log_(1-1/(M-1))(1-P)

 

Если всего 5 кувшинок и берег (M=6) и искомая вероятность 50% (P=0,5), то получаем K = 4 (K > 3,1)

 

 

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

1 - (M-1)/M*(1-1/(M-1))^(K-1) = P

 

и

 

K = 1 + log_(1-1/(M-1))((1-P)*M/(M-1))

 

 

В итоге лягушке в среднем понадобится все равно 4 прыжка (K > 3,2)

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

[Рогожников Евгений]

 

если у Горыныча N голов, то они должны расположиться в вершинах правильного N-угольника, вписанного в окружность, где радиус окружности равен длине шеи (т.е. единице)

 

 

 

Это неверно при N > 3, т.к Горыныч живет в 3-х мерном пространстве, а не в двумерном.

При N=4 головы будут в вершинахправильного тетраэдра

[barefoot]

Насчет лягушки... Она стартует на одном берегу и финиширует на другом.

Обозначим M_n матожидание количества прыжков, за которое лягушка достигает противоположного берега, при наличии n кувшинок.

Очевидно, M₀ = 1.

При n=1 у лягушки есть два равновероятных варианта - сразу на тот берег (1 прыжок), или через кувшинку (2 прыжка): M₁ = 1/2*1 + 1/2*2 = 3/2.

 

В общем случае, пусть после первого прыжка лягушка оказалась на кувшинке i (1 <= i <= n). Тогда между ней и противоположным берегом останется (n - i) кувшинок, на преодоление которых ей в среднем понадобиться M_{n - i} прыжков. Отсюда получаем:

    M_n = 1/(n + 1)*1 + 1/(n + 1)*(1 + M₀) + 1/(n + 1)*(1 + M₁) + ... + 1/(n + 1)*(1 + M_{n - 1})

После несложных преобразований получаем

    M_n = 1 + 1/(n + 1)*(M₀ + M₁ + ... + M_{n - 1})                           (1)

 

Запишем эту же формулу для M_{n + 1}:

    M_{n + 1} = 1 + 1/(n + 2)*(M₀ + M₁ + ... + M_{n - 1} + M_n)                      (2)

 

Но согласно (1)

   M₀ + M₁ + ... + M_{n - 1} = (n + 1)*(M_n - 1)

 

Подставим это значение в (2):

    M_{n + 1} = 1 + 1/(n + 2)*((n +1)*(M_n - 1) + M_n) = 1 + M_n - (n + 1)/(n + 2) = M_n + 1/(n + 2)

 

Или, что то же самое,

    M_n = M_{n - 1} + 1/(n + 1)

Или в развернутой форме

    M_n = 1 + 1/2 + 1/3 + ... + 1/(n + 1)

 

Таким образом, M_n представляет собой частичную сумму гармонического ряда. Как известно, сумма эта растет как логарифм:

    M_n -> ln(n + 1) + γ