Решение задачи

Задача вот отсюда.

Алисе и Бобу предлагается играть против казино в следующую игру: Казино в присутствии Боба загадывает последовательность длиной n из орлов и решек. Далее проводится n раундов. В каждом раунде Алиса и Боб одновременно называют каждый свою догадку для очередного члена последовательности (Боб, конечно, знает правильный ответ). Если обе догадки оказались правильными, то они выигрывают этот раунд, иначе выигрывает казино. Вопрос: какую стратегию им выбрать, чтобы гарантированно выигрывать 6 раундов из n=9. Дополнительный вопрос: Как максимизировать выигрыш при другом числе раундов, в том числе и при бесконечном?

 

Сначала разберёмся с асимптотическим случаем. Разбиваем всю последовательность на блоки длиной $N$. Технология будет такая: в первом блоке Боб просто сигнализирует биты второго. Конечно, он может это сделать без ощибок, но может и намеренно "ошибаться". Сейчас станет понятно зачем. Когда дело доходит до второго блока, в некоторых битах происходят "сбои": либо Алиса называет неправильный  результат, либо Боб, либо они вместе. Пусть таких битов $n$. Сколько информации может передать Боб через эти биты? Учитывая произвольность мест этих битов и три различных ситуации для каждой "ошибки", получаем ${N\choose n}\cdot 3^n$ вариантов. Если потребовать, чтобы это число было не меньше, чем $2^N$, то с помощью таких "битых" битов мы сможем передать информацию о следующем блоке. И дальше ситуация будет повторяться. Если записать $n=Nr$ и вычислить асимптотику $N\to\infty$ от функции $\ln\left[{N\choose Nr}\cdot 3^{Nr}2^{-N}\right]$, то получим $N[r \ln(3 (1- r)/r) - \ln(2(1- r))]$. Численно получаем $r=0.1892896...$. То есть, в асимптотике можно ошибаться меньше, чем в 20%.  Заметим, что на достаточно длинных конечных последовательностях к этому числу можно приближаться сколь угодно близко.

Решение для случая "6 из 9" тоже использует похожий приём. Главное, это то, что можно использовать для передачи не просто "битый" бит, а ещё и его положение.

Вот решение из того же источника:

1. Сначала определим стратегию, когда хотя бы одна из групп битов 234, 567, 89 имеет одинаковое значение. В первом бите Боб называет медианное значение группы 234.
   • Если все биты этой группы одинаковые, то они будут угаданы, а бит 5 Боб использует для передачи медианного значения группы 678. В этой группе будет угадано не меньше двух бит, а третий можно использовать для передачи бита 9.
   • Если не все биты 234 одинаковы, то в этой группе будут угаданы два бита, а третий Боб использует для передачи медианного значения группы 567.
   • Если все биты 567 одинаковы, то все три будут угаданы, а в бите 8 Боб сообщит значение бита 9.
   • Если не все биты 567 одинаковы, то два будут угаданы, а оставшимся Боб передаст значение для группы 89.
   Алиса, зная эту стратегию, следует базовому правилу: всегда называет значение, переданное последним сигнальным битом Боба.
   На этом этапе нам остались случаи, когда каждая группа 234, 567, 89 содержит оба значения. Мы должны научиться как можно раньше сигнализировать об этой ситуации отклонениями от стратегии, описанной выше. Когда Алиса видит эти отклонения, она может действовать уже не в рамках своего базового правила, см. ниже.
   Разобьем оставшиеся конфигурации на три группы:
2. бит 5 отличается от битов 67. В этом случае Боб первым битом сообщает медианное значение группы 234, как и раньше. В группе 234 он передаёт один бит, как и раньше, но ещё намеренно ошибается в одном из двух правильных битах. В каком именно --- это даёт второй бит информации, пусть, например, это будет значение бита 8. После 4 бита Алиса понимает, что Боб отклонился от основной стратегии пункта 1, причём определённым образом: правильно передал медианное значение в бите 1, но намеренно ошибся в одном из правильных битов. Это является сигналом того, что это случай 2, и тогда Алиса знает значения всех пяти оставшихся битов 56789.
3. бит 6 отличается от битов 57. Здесь мы применим другую стратегию. Боб первым битом намеренно неправильно сообщит медианное значение группы 234. В группе 234 у него тогда опять появится возможность передать два бита. После 4 бита Алиса понимает, что Боб отклонился от основной стратегии пункта 1, причём теперь уже другим образом: неправильно передал медианное значение в бите 1. Значит, как и в пункте №2 Алиса знает значения битов 56789.
4. бит 7 отличается от битов 56. Здесь Боб следует обычной стратегии вплоть до бита 4. Алиса после 4 бита знает медианное значение группы 567. Причем, в группе 234 уже угаданы два бита. Но тогда Боб может намеренно ошибиться в одном из двух битов 56, передавая посредством положения "ошибки" значение бита 8. После хода 6 Алиса видит, что комбинация может принадлежать только группе №4. Значит, она понимает, что бит 7 будет противоположен 56, а также, знает значение битов 89 (поскольку восьмой был передан, а девятый ему противоположен). Получаем два угаданных бита в группе 567 и два в группе 89.

Быки и Коровы

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

• После первого хода он всегда даёт одну корову.
• Если во втором ходе не использовать цифры первого хода, то он даст две коровы.
• Если во втором ходе использовать ровно одну цифру первого хода, то он даст одну корову.

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

---

введите число
предлагать число

№	число	бк (# ответов)	# вариантов

---

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

Телеграм-канал

 Поскольку сюда писать (пока) ленюсь, создал телеграм-канал Задачи и головоломки. Кто любит решать задачи --- подписывайтесь.

Задачки

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

Услышал вчера неплохую задачу на логику.

Есть три друга: Илья, Лёша и Стас. Илья всегда говорит правду, Лёша всегда врёт, а Стас выбирает ответ случайно.

Повстречав эту троицу и задав три вопроса типа да-нет (каждый вопрос задаётся одному человеку), как определить кто из них кто?

Задача простая, конечно.

Mathematica 12.2

В новом релизе Mathematica (12.2)  наконец-то перестал работать мой пакет LiteRed разлива 2015г. Суматошное разбирательство показало, что причина в измененной процедуре ValueQ. Выяснилось, что код

f[x]^=1;ValueQ[g[x]]

теперь даёт при вычислении True (и код x=x;ValueQ[x] тоже даёт True). В ярости написал вопрос в Mathematica Stack Exchange, и да, таки, всё правильно, как в том анекдоте.

Из любопытства прошёлся по списку багов, который я когда-то составлял. Баги №№5,8,9 всё ещё живы. Девятый я тоже запостил в Mathematica.SE. Самое смешное --- что случилось с багом №2: до версии 12.2 DiscreteRatio[Sin[Pi x], x] вычислялось в 1, а в 12.2 этот баг "исправили": теперь DiscreteRatio[Sin[Pi x], x] остаётся невычисленным. Прогресс!

Объять необъятное

Вот есть такое тождество для $0\leqslant z\leqslant 1$: $$_2F_1\left(\tfrac13, \tfrac23; 1; \tfrac{27 (-1 + z^2)^2}{(3 + z^2)^3}\right)=\frac{\left(z^2+3\right) }{\sqrt{(3-z)^3 (z+1)}}\,_2F_1\left(\tfrac{1}{2},\tfrac{1}{2};1;\tfrac{(1-z) (z+3)^3}{(3-z)^3 (z+1)}\right)$$ Я даже, если очень захочется, смогу его доказать, наверное. Но вот откуда такие монстры берутся, и как их находить, я совершенно не представляю. И если об этом думать, по-моему, можно мозг сломать. Особенно страшно становится, если записать тождество в виде $$_2F_1\left(\tfrac13, \tfrac23; 1; x\right)=t\,_2F_1\left(\tfrac{1}{2},\tfrac{1}{2};1;y\right)$$ и выяснить, что $y$ и $t$ связаны с $x$ вот такими алгебраическими уравнениями: $$\begin{gather}256 x^4 y^6-768 x^4 y^5+1536 x^4 y^4-1792 x^4 y^3+1536 x^4 y^2-768 x^4 y+256 x^4-768 x^3 y^6+2304 x^3 y^5+9216 x^3 y^4\nonumber\\-22272 x^3 y^3+9216 x^3 y^2+2304 x^3 y-768 x^3+768 x^2 y^6-2304 x^2 y^5+9792 x^2 y^4-15744 x^2 y^3+9792 x^2 y^2\nonumber\\-2304 x^2 y+768 x^2-256 x y^6+768 x y^5-888 x y^4+496 x y^3-888 x y^2+768 x y-256 x+27 y^4-54 y^3+27 y^2=0\end{gather}$$ $$\begin{equation}256 t^{12} x^4-768 t^{12} x^3+768 t^{12} x^2-256 t^{12} x+1728 t^8 x^2+432 t^8 x+27 t^8-432 t^4 x-54 t^4+27=0\end{equation}$$

Стрела времени

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

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

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

Если эту точку зрения развивать, наверное, можно утонуть в бесплодных философствованиях. И этим заниматься я не собираюсь. Но вот что я хотел подчеркнуть, это то, что геометрия нашего мира в совершенно определённом смысле не вступает в противоречие с этой самой свободой воли, в то время как могло бы быть и не так. Я, как обычно, говорю о самоочевидных вещах, но всё же мне это кажется забавным. Сравним уравнения $$(\partial_t^2-\Delta)\psi=0$$ и $$(\partial_t^2+\Delta)\psi=0$$ Первое соответствует волновому уравнению в псевдоевклидовом пространстве, а второе --- его евклидов аналог. Казалось бы, поменялась только сигнатура метрики, группы симметрии очень похожи, и даже формально совпадут при замене $t\to it$. Но в первом случае граничные условия можно ставить на пространственно-подобной поверхности, произвольно зафиксировав $\psi$ и её нормальную производную. Во втором же случае так поступать нельзя. Поэтому проявить свободу воли в пространстве с евклидовой метрикой весьма затруднительно, не сломав всё к чертям. Пространство же с псевдоевклидовой метрикой как будто специально устроено для проявления свободы воли.