智取“黑白配”

KeyTo9_Fans

以上都是讨论最坏情况下的胜率。

接下来我想讨论平均情况下的胜率。

具体的问题描述如下：

=====
A,B,C三人围成一圈玩手心手背游戏.

每轮游戏三人将手藏在背后，喊"1,2,3,嘿"，同时伸出一只手（手心朝上或手背朝上）.

三人出手相同为B和C赢，不同就算A赢.

该游戏一共要玩n轮（n→∞）. A要预先决定好自己n轮的出手，并单独告诉C. （A决定自己n轮出手的方法是抛n次硬币，游戏时严格按照抛硬币的结果出手，并于游戏开始前把n轮的出手告诉C.）

C在得知A的所有出手之前，就要与B商定一个策略，此后不能有任何信息交流.

游戏期间，B除了能看到A和C的出手结果（手心或手背），无法获得其它信息.

问：怎样的策略，才能确保B和C的胜率达到0.82？
=====

讨论$0.82$的胜率是为了否定平均情况下与最坏情况下的胜率极限相同，

同时也是为了否定该极限和随机序列的最长公共子序列与原序列长度之比的极限（$0.812$）相同。

KeyTo9_Fans

该楼只是提醒坛友们，40楼有更新。以后我会把该楼内容编辑掉，避免出现水楼。

#####2021-11-6####

无奈了，即使只要求平均情况的胜率最高，

最优策略的胜率竟然和要求最坏情况胜率最高时是一样的，都是$0.81071$。

更精确的结果是大于$0.810710375084$、小于$0.810710375085$，不可能达到$0.812$。

majer

@KeyTo9_Fans

根据中文翻译出版物《令你冥思苦想的数学趣题》一书，参考书目【32】 有个链接http://ratio.huji.acil/dp/dp316.pdf（但我没打开），提到一篇2007年的论文《Online Matching Pennies》（也没搜到）。

这里就是把猜黑白配，变成猜硬币的字背。

其中三位作者证明，胜率可以无限接近一个超越方程的实数根x:\[
-x\log_2x-(1-x)\log_2(1-x)+(1-x)\log_23=1
\]我没算，据说\(x≈0.8016\)

majer

续上 三位作者是Olivier Gossner, Penélope Hernández and Abraham Neyman。我查了他们的论文列表，都没找到那篇。看来只能直接EMAIL询问了……是因为有漏洞撤回了吗

majer

找到了

https://scholars.huji.ac.il/site ... files/ompdpmay6.pdf，原来是上传后排版损坏的问题……

KeyTo9_Fans

majer 发表于 2021-11-17 16:17
找到了

https://scholars.huji.ac.il/site ... files/ompdpmay6.pdf，原来是上传后 ...

这是上面这篇参考文献的主要结论：



然后我把42楼里的 $x=0.810710375084$ 代进去，发现这个等式是成立的。

（本来我还打算把方程找到，然后发表论文的，没想到早就有人发表了）

至此，楼主的问题的极限情况已经解决了。

只剩下【具体方案如何制定和描述，才能更优雅更简洁】的问题了。

xiaoshuchong

majer 发表于 2021-11-17 15:41
@KeyTo9_Fans

根据中文翻译出版物《令你冥思苦想的数学趣题》一书，参考书目【32】 有个链接http://rat ...

根是0.81071037508476823739760530663472575783