找回密码
 欢迎注册
楼主: 小铃铛

[转载] 智取“黑白配”

  [复制链接]
发表于 2021-3-3 23:02:39 | 显示全部楼层
以上都是讨论最坏情况下的胜率。

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

具体的问题描述如下:

=====
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$)相同。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-11-5 10:29:06 | 显示全部楼层
该楼只是提醒坛友们,40楼有更新。以后我会把该楼内容编辑掉,避免出现水楼。

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

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

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

更精确的结果是大于$0.810710375084$、小于$0.810710375085$,不可能达到$0.812$。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-11-17 15:41:53 | 显示全部楼层
@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\)



毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-11-17 16:09:14 | 显示全部楼层
续上 三位作者是Olivier Gossner, Penélope Hernández and Abraham Neyman。我查了他们的论文列表,都没找到那篇。看来只能直接EMAIL询问了……是因为有漏洞撤回了吗
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-11-17 16:17:46 | 显示全部楼层
找到了

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

评分

参与人数 1威望 +3 金币 +3 贡献 +3 经验 +3 鲜花 +3 收起 理由
KeyTo9_Fans + 3 + 3 + 3 + 3 + 3 链接有参考价值

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-11-18 09:08:19 | 显示全部楼层


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

pattern.png

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

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

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

只剩下【具体方案如何制定和描述,才能更优雅更简洁】的问题了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-3-22 22:02:04 | 显示全部楼层
majer 发表于 2021-11-17 15:41
@KeyTo9_Fans

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

根是0.81071037508476823739760530663472575783
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 13:57 , Processed in 0.062355 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表