Задачи, головоломки, загадки

19-летний итальянский разработчик Габриэле Чирулли (Gabriele Cirulli) создал чрезвычайно захватывающую игру 2048, скрестив тетрис и «пятнашки».
_______

http://masterok.livejournal.com/3781345.html
Мастерок - тормоз, эта игра отгремела лет 5 назад и про нее уже все забыли.
 
Загадка происхождения. Кажется нет общенаучной темы. Поэтому здесь..
Цитаты...:
___________

Пока сёстры ждали своих результатов, они размышляли над этим вопросом. Если выводы Ancestry.com были правильными, это означало, что один из родителей семьи Плебух был, по крайней мере, частично евреем. Но какой?
__________
Как написано....(!)...:
'Ей нравится находить паттерны, скрытые в хаосе..'
=========
https://22century.ru/popular-science-publications/she-thought-she-was-irish
 
Вот вам задачка, про которую ходит миф, что сам великий Ричард Фейнман поначалу упустил ее верное решение.
20180810_152431.png
Нужно выразить радиус окружности через a, b и c наиболее простым образом.

Взято отсюда:
http://web.media.mit.edu/~walter/MAS-A12/week11.html

Осторожно! По линку есть решение.
 
Вот вам задачка, про которую ходит миф, что сам великий Ричард Фейнман поначалу упустил ее верное решение.
Посмотреть вложение 81094
Нужно выразить радиус окружности через a, b и c наиболее простым образом.

Взято отсюда:
http://web.media.mit.edu/~walter/MAS-A12/week11.html

Осторожно! По линку есть решение.
R = b

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

-----------------------
Задача: пункты А, Б на расстоянии 100км. Из обоих одновременно выезжают поезда навстречу друг другу со скоростями 50км/ч каждый.

В начальный момент времени из пункта А также вылетает муха со скоростью 70км/ч и летит пока не встретится со встречным поездом. Сразу после встречи она разворачивается и летит назад пока не встретится со встречным поездом, затем снова разворачивается и т.д.

Вопрос: какое суммарное расстояние пролетит муха пока поезда не встретятся?
-----------------------

Так вот, по легенде эту задачу когда-то рассказали Гильберту. Он так задумался на несколько секунд, и назвал правильный ответ.
Собеседник (обрадованно)
- Ну вот, наконец-то кто-то сообразил как эту задачу легко решить, а не как все стал вычислять сумму ряда.
Гильберт (удивлённо):
- А что, разве есть другой способ?!
 
ПС. Если вам показалось слишком легко, то вам должно быть не сложнее посчитать среднее число бросков до любой другой оканчивающей последовательности, например: ОРОРРОРР
 
Ну что расслабились? Сегодня задачка сложная.
Монету бросают много раз. Сколько в среднем нужно сделать бросков пока появится последовательность: О, Р, Р, О ?
Обозначим наши состояния: Х, О, ОР, ОРР, ОРРО.
(Х - пустая последовательность, остальные - частичные последовательности которые могут привести к результату).

Наша цель - найти среднее кол-во бросков для перехода X -> ОРРО. Тонкость в этой задаче заключается в том что если в определённый момент выпадает не тот результат, то мы "откатываемся" не обязательно в начало поиска.

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

X -> X или O
O -> О или ОР
OР -> О или ОРР
ОРР -> Х или ОРРО

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

N(X -> O) = 1 + 1/2 * N(X -> O)
значит:
N(X -> O) = 2

N(O -> OР) = 1 + 1/2 * N(О -> OР)
значит:
N(О -> OР) = 2

N(OР -> OРР) = 1 + 1/2 * ( N(О -> OР) + N(ОР -> OРР) ) = 2 + 1/2 * N(ОР -> OРР)
значит:
N(ОР -> OРР) = 4

N(OРР -> OРРО) = 1 + 1/2 * ( N(Х -> O) + N(О -> OР) + N(ОР -> OРР) + N(ОРР -> OРРО) ) = 5 + 1/2 * N(ОРР -> OРРО)
значит:
N(ОРР -> OРРО) = 10

Итого: N(Х -> OРРО) = N(X -> O) + N(O -> ОР) + N(OР -> ОРР) + N(OРР -> ОРРО) = 2+2+4+10 = 18

Ответ: 18
 
@valdo , Решение верное, но тут фишка в том, что есть более простое решение. Во всяком случае есть способ, который позволяет посчитать даже в уме ожидаемое количество бросков для любой оканчивающей последовательности.
 
@valdo , Решение верное, но тут фишка в том, что есть более простое решение. Во всяком случае есть способ, который позволяет посчитать даже в уме ожидаемое количество бросков для любой оканчивающей последовательности.
Простого способа не вижу. Но если посмотреть на тот способ что я привёл, то в нём видна такая закономерность:

N(B->C) = 2 + N(A->B)
(имеется ввиду что из состояния B мы либо продвигаемся в C, либо откатываемся в A).

Далее мы составляем таблицу переходов, и высчитываем все значения по этой формуле.

Наша таблица переходов:

1534580157926.png

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

Далее высчитываем таблицу:

1534580333715.png

Ответ: 256

И я не имею ни малейшего понятия как это монжо посчитать в уме :)
 
Простого способа не вижу. Но если посмотреть на тот способ что я привёл, то в нём видна такая закономерность:

N(B->C) = 2 + N(A->B)
(имеется ввиду что из состояния B мы либо продвигаемся в C, либо откатываемся в A).

Далее мы составляем таблицу переходов, и высчитываем все значения по этой формуле.

Наша таблица переходов:

Посмотреть вложение 81462

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

Далее высчитываем таблицу:

Посмотреть вложение 81464

Ответ: 256

И я не имею ни малейшего понятия как это монжо посчитать в уме :)
Получилось верно. Ну не знаю, hint нужен? Попробуй еще посчитать
ОООООООО (8 орлов) там должно получиться 510, и
ОРРООРРО - 274.
 
Получилось верно. Ну не знаю, hint нужен? Попробуй еще посчитать
ОООООООО (8 орлов) там должно получиться 510, и
ОРРООРРО - 274.
Рассмотрим случай с 8 орлами. Там всё просто т.к. в случае ошибки мы откатываемся в самое начало, поэтому можно показать (не буду чтобы не было многобукаф) что для последовательности длиной n ответ: N(n) = 2 * (2^n + 1).

Если посмотреть на N(n) в бинарном виде то мы видим n единиц и в конце ноль. Т.е. 111....1110.

Легко видеть что в любом случае ответ чётный (включая сложные варианты). Так что последний бит рассматривать не будем (надо лишь в конце умножить ответ на 2).

Итак, для простого случая ответ: n-битовое число где все биты равны 1.

А что происходит в "сложных" случаях, когда откатываемся не в начало?

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

Рассмотрим на примерах. Для 8 орлов имеем:
OOOOOOOO
11111111 = 255 (ответ 255*2 = 510)


Очевидно все биты являются откатными.


Второй случай:
ОРРООРРО
10001001 = 137 (ответ 137 * 2 = 274)


Здесь у нас остаётся последний бит О (т.к. это является префиксом), бит где начинается ОРРО (что полностью совпадает с префиксом). И, разумеется первый бит (старший), он всегда остаётся (т.к. в этом случае строчка это и есть префикс)

Третий случай:
ОРОРРОРР
10000000 = 128 (ответ 128 * 2 = 256)

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

------------------------------------------
Итак, почему это работает?

Не хочу много писать, там довольно сложно объяснить, но идея в том что у нас рекурсивная формула N(n+1) = 2(N(n) + 1) - N(m), где m - состояние куда мы откатываемся в сулчае ошибки. Если внимательно посчитать откаты, и для каждого N(n) найти из каких N(m) он состоит, то можно убедиться в верности формулы.
 
Рассмотрим случай с 8 орлами. Там всё просто т.к. в случае ошибки мы откатываемся в самое начало, поэтому можно показать (не буду чтобы не было многобукаф) что для последовательности длиной n ответ: N(n) = 2 * (2^n + 1).

Если посмотреть на N(n) в бинарном виде то мы видим n единиц и в конце ноль. Т.е. 111....1110.

Легко видеть что в любом случае ответ чётный (включая сложные варианты). Так что последний бит рассматривать не будем (надо лишь в конце умножить ответ на 2).

Итак, для простого случая ответ: n-битовое число где все биты равны 1.

А что происходит в "сложных" случаях, когда откатываемся не в начало?

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

Рассмотрим на примерах. Для 8 орлов имеем:
OOOOOOOO
11111111 = 255 (ответ 255*2 = 510)


Очевидно все биты являются откатными.


Второй случай:
ОРРООРРО
10001001 = 137 (ответ 137 * 2 = 274)


Здесь у нас остаётся последний бит О (т.к. это является префиксом), бит где начинается ОРРО (что полностью совпадает с префиксом). И, разумеется первый бит (старший), он всегда остаётся (т.к. в этом случае строчка это и есть префикс)

Третий случай:
ОРОРРОРР
10000000 = 128 (ответ 128 * 2 = 256)

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

------------------------------------------
Итак, почему это работает?

Не хочу много писать, там довольно сложно объяснить, но идея в том что у нас рекурсивная формула N(n+1) = 2(N(n) + 1) - N(m), где m - состояние куда мы откатываемся в сулчае ошибки. Если внимательно посчитать откаты, и для каждого N(n) найти из каких N(m) он состоит, то можно убедиться в верности формулы.
Все верно, вечером постараюсь написать как до всего этого можно дойти в уме используя вероятностный подход вместо комбинаторного.
 
Все верно, вечером постараюсь написать как до всего этого можно дойти в уме используя вероятностный подход вместо комбинаторного.
Жду с нетерпением. Потому что я себя худо-бедно смог убедить что это правильно (из соображений того кто кого сколько раз в себе имеет), но не уверен что смогу убедить кого-то другого.

Но задача - супер! Давно таких красивых не видел.
 
Такие задачи обычно легко решаются с помощью подходящего мартингала. Покажем решение на примере строки ОРОР.
Представим казино в котором каждый час происходит розыгрыш подбрасыванием монетки. На N-ом шаге в казино входит человек с одним рублем в кармане и делает ставку в 1 рубль на О. Если выиграл, то на следующем шаге он ставит 2 рубля на Р, если выиграл, то далее ставит 4 рубля на О и так далее постоянно удваивая ставку и ставя на следующую букву нашей последовательности и так до конца нашей последовательности. Если на любом шаге человек проиграл, то он банкрот и выбывает из игры. Каков ожидаемый выигрыш? Если выпадет ОРОР (с вероятностью 1/16) то выигрыш составит 1+2+4+8=15 рублей, во всех остальных 15-ти случаях человек проигрывает 1 рубль, значит ожидаемый выигрыш равен 0 при подобной системе.
Теперь представим, что в казино на каждом шаге входит новый человек и начинает свою игру (которая для него продолжается максимум 4 шага). Совокупный ожидаемый выигрыш всех вошедших очевидно тоже должен быть равен нулю,
а значит является мартингалом.

Теперь как это все используется для вычисления ожидаемого количества шагов N до выпадения ОРОР.
Допустим на N-ом шаге впервые выпало ОРОР. Это значит, что первые N-4 вошедших игроков проиграли по рублю и их совокупный выигрыш равен 4-N. (N-3) -й игрок очевидно выиграл 15 рублей. (N-2)-й проиграл рубль, (N-1)-й выиграл 1+2=3 рубля, и N-й проиграл рубль. То есть совокупный выигрыш всех N игроков равен:
4 - N + 15 -1 + 3 - 1 = 20 - N.
Однако, ожидаемый совокупный выигрыш должен быть равен нулю, значит 20 - N = 0, откуда ожидаемый N = 20.
Этот метод легко обобщается для произвольной строки, и если посмотреть как мы считаем совокупный выигрыш, то понятно что нужно для каждого суффикса, который является префиксом добавить 2^k, где k это длина суффикса.