智取“黑白配”

小铃铛

13Y9:  分组  1,234,5678,9abc,d    （修正版）
A在后12轮中共有4096种选择，其中高3位相同的有1024种，可以达成3+9Y6,所以还剩3072种
其中高3位2:1，接着4位相同的有384种，可以达成2+4+5Y3,所以还剩2688种
其中高3位2:1，接着4位是3:1，后5位是3:1+1的有768种，可以达成2+3+3+1，所以还剩1920种
其中高3位2:1，接着4位是3:1，后5位是4:0+1的有192种，可以达成2+3+4,所以还剩1728种

1728种中只包含了下面三种类型：
一.高3位2:1，接着4位是3:1，后5位是2:2+1的有576种
二.高3位2:1，接着4位是2:2，后5位是3:1+1的或是4:0+1有720种
三.高3位2:1，接着4位是2:2，后5位是2:2+1的有432种

2:2的形式可分3种：eeff,efef,effe（ef=10或01）

在一.中即：高3位2:1，接着4位是3:1，后5位是2:2+1.
对后5位是eeff+d这种类型，C只需在第9轮和第10轮减赢1轮，以表示后5轮=eeff+d，用减赢轮次的不同来提示不同的d就可以了，2+3+3+1=9，即可再排除192种

在二.中即：高3位2:1，接着4位是2:2，后5位是3:1+1或是4:0+1
这种类型C只需在5678=eeff时在第5,6轮减赢1轮，指示A5678=eeff,前后减赢，指示出9abc,从而拿定5678中3轮+9abc中4轮或9abc中(3轮+d)的4轮，即 2+3+4=9
        C只需在5678=efef时在第234轮减赢1轮，指示A5678=efef,错轮指示e，前后减赢，指示出9abc，从而拿定5678，再加上9abc中4轮或9abc中(3轮+d)的4轮，  即 1+4+4=9
        C只需在5678=effe时在第234轮利用反信息来减赢1轮，前错轮提示5678中的e，从而拿定5678的4轮。后错轮提示出9abc，就能赢取9abc中4轮或9abc中(3轮+d)的4轮，即 1+4+4=9

在三.中即：高3位2:1，接着4位是2:2，后5位是2:2+1
这种类型C只需在9abc=eeff时，5678的2:2通过56轮的1种减赢和234轮的2种不同的减赢手法，指示A5678的不同的2:2组合，最终拿定前8轮中的5轮并提供出一个信息，这个信息用来指向        
9abc=eeff中的e，这个策略会和二.中的9abc=3:1或是4:0时重合，其区别就在第9，a轮，在三.中它会需要减赢一轮，前后减赢，指示d轮，从而拿定9abc=eeff中的3轮加d轮，即5+3+1=9，可再排除144种

小计：还可以排除144+192+720=1056种，还剩下672种，其中包括下面几种类型：

1.  高3位2:1，接着4位是3:1，后5位是efef+d或后5位是effe+d的有384种
2.  高3位2:1，接着4位是2:2，后5位是efef+d或后5位是effe+d的有288种

接着就是13赢9的关键，策略上是可以有重合，只需要C有不同的变化就可以。其实，A也是可以加以利用的。

在所有策略中，5678轮都没有出现过不使用减赢手法的2:2，下面到了使用它的时候：
分组  1,234,5678,9abc,d
2.  高3位2:1，接着4位是2:2，后5位是efef+d或后5位是effe+d
  234的错轮指向第9位的e。这对接下来的5678轮都没影响，都会产生2赢2输的结果。前输轮指向第b轮,后输轮指向d。
  B能发现在5678轮中没有减赢动作，即表示9abc=efef或effe，第9轮的e和第b轮的指示都有了，还有了d，就确定了后5轮。即2+2+5=9

现在还剩下唯一的一种类型：
1.高3位2:1，接着4位是3:1，后5位是efef+d或后5位是effe+d的有384种

小铃铛

最后的这种类型留待感兴趣的坛友自己去挖掘，兴许会有完全不同的思路和解法。
13Y9只是热身，为推出第二问作铺垫：
问二：怎样的策略，才能确保 B 和 C 在 18 轮游戏中赢取 13 轮？
这相当于2个9Y6组合上再多赢1轮！

dlpg070

KeyTo9_Fans 发表于 2018-5-2 16:23
对于$13$局赢$9$局的问题，我的猜想是无解。

证明无解的大致思路如下：

KetTo9_Fans的证明和an等计算是此问题理论研究的开创性结果
可能带来求解策略全新思路,解决n较大时的难题,例如: (25 赢 18),等
希望重新整理证明,去掉推理中的错误数据,
提供an的计算代码,谢谢
实际原题有附加题,难度比18赢13 难得多,尚未见解答
As a bonus question: when n goes to infinity, can they do better?
What is the maximal probability they can guarantee in the worst case?
KetTo9_Fans的证明和an等计算也许有助于回答此问题


为了学习,我做了3项验算工作,
1 利用KetTo9_Fans 前20项列表扩展到996项 记为maxwin
  得到许多新的难题
(1 赢 0),
(2 赢 1),
(3 赢 1),
(4 赢 2),
(5 赢 3),
(6 赢 3),
(7 赢 4),
(8 赢 5),
(9 赢 6),
(10 赢 6),
(11 赢 7),
(12 赢 8),
(13 赢 9),
(14 赢 9),
(15 赢 10),
(16 赢 11),
(17 赢 12),
(18 赢 13),
(19 赢 13),以下为新难题
(20 赢 14),
(21 赢 15),
(22 赢 16),
(23 赢 17),
(24 赢 17),
(25 赢 18),
(26 赢 19),
(27 赢 20),
(28 赢 21),
(29 赢 21),
(30 赢 22),
(31 赢 23),
(32 赢 24),
(33 赢 25),
(34 赢 25),

2 比较A213854和maxwin (100项中,前33项相同,通项神奇的相似)
3 an 192项 和 知乎白无妨31项 互相印证,理论证明和计算an的公式可信

下面列出几个重要的数据列表
1 an列输出 ,192项
an k  n   m   m/n
{1,1,(2 赢 1),0.5}
{2,2,(5 赢 3),0.6}
{3,3,(9 赢 6),0.666667}
{4,4,(13 赢 9),0.692308}
{5,5,(18 赢 13),0.722222}
{6,6,(23 赢 17),0.73913}
{7,7,(28 赢 21),0.75}
{8,8,(33 赢 25),0.757576}
{9,9,(38 赢 29),0.763158}
{10,10,(43 赢 33),0.767442}
{11,11,(48 赢 37),0.770833}
{12,12,(53 赢 41),0.773585}
{13,13,(58 赢 45),0.775862}
{14,14,(63 赢 49),0.777778}
{15,15,(68 赢 53),0.779412}
{16,16,(73 赢 57),0.780822}
{17,17,(78 赢 61),0.782051}
{18,18,(83 赢 65),0.783133}
{19,19,(88 赢 69),0.784091}
{20,20,(94 赢 74),0.787234}
{21,21,(99 赢 78),0.787879}
{22,22,(104 赢 82),0.788462}
{23,23,(109 赢 86),0.788991}
{24,24,(114 赢 90),0.789474}
{25,25,(119 赢 94),0.789916}
{26,26,(125 赢 99),0.792}
{27,27,(130 赢 103),0.792308}
{28,28,(135 赢 107),0.792593}
{29,29,(140 赢 111),0.792857}
{30,30,(145 赢 115),0.793103}
{31,31,(150 赢 119),0.793333}
{32,32,(156 赢 124),0.794872}
{33,33,(161 赢 128),0.795031}
{34,34,(166 赢 132),0.795181}
{35,35,(171 赢 136),0.795322}
{36,36,(176 赢 140),0.795455}
{37,37,(182 赢 145),0.796703}
{38,38,(187 赢 149),0.796791}
{39,39,(192 赢 153),0.796875}
{40,40,(197 赢 157),0.796954}
{41,41,(203 赢 162),0.79803}
{42,42,(208 赢 166),0.798077}
{43,43,(213 赢 170),0.798122}
{44,44,(218 赢 174),0.798165}
{45,45,(223 赢 178),0.798206}
{46,46,(229 赢 183),0.799127}
{47,47,(234 赢 187),0.799145}
{48,48,(239 赢 191),0.799163}
{49,49,(244 赢 195),0.79918}
{50,50,(250 赢 200),0.8}
{51,51,(255 赢 204),0.8}
{52,52,(260 赢 208),0.8}
{53,53,(265 赢 212),0.8}
{54,54,(270 赢 216),0.8}
{55,55,(276 赢 221),0.800725}
{56,56,(281 赢 225),0.800712}
{57,57,(286 赢 229),0.800699}
{58,58,(291 赢 233),0.800687}
{59,59,(297 赢 238),0.801347}
{60,60,(302 赢 242),0.801325}
{61,61,(307 赢 246),0.801303}
{62,62,(312 赢 250),0.801282}
{63,63,(318 赢 255),0.801887}
{64,64,(323 赢 259),0.801858}
{65,65,(328 赢 263),0.801829}
{66,66,(333 赢 267),0.801802}
{67,67,(339 赢 272),0.80236}
{68,68,(344 赢 276),0.802326}
{69,69,(349 赢 280),0.802292}
{70,70,(354 赢 284),0.80226}
{71,71,(359 赢 288),0.802228}
{72,72,(365 赢 293),0.80274}
{73,73,(370 赢 297),0.802703}
{74,74,(375 赢 301),0.802667}
{75,75,(380 赢 305),0.802632}
{76,76,(386 赢 310),0.803109}
{77,77,(391 赢 314),0.803069}
{78,78,(396 赢 318),0.80303}
{79,79,(401 赢 322),0.802993}
{80,80,(407 赢 327),0.80344}
{81,81,(412 赢 331),0.803398}
{82,82,(417 赢 335),0.803357}
{83,83,(422 赢 339),0.803318}
{84,84,(428 赢 344),0.803738}
{85,85,(433 赢 348),0.803695}
{86,86,(438 赢 352),0.803653}
{87,87,(443 赢 356),0.803612}
{88,88,(449 赢 361),0.804009}
{89,89,(454 赢 365),0.803965}
{90,90,(459 赢 369),0.803922}
{91,91,(464 赢 373),0.803879}
{92,92,(470 赢 378),0.804255}
{93,93,(475 赢 382),0.804211}
{94,94,(480 赢 386),0.804167}
{95,95,(485 赢 390),0.804124}
{96,96,(491 赢 395),0.804481}
{97,97,(496 赢 399),0.804435}
{98,98,(501 赢 403),0.804391}
{99,99,(506 赢 407),0.804348}
{100,100,(512 赢 412),0.804688}
{101,101,(517 赢 416),0.804642}
{102,102,(522 赢 420),0.804598}
{103,103,(527 赢 424),0.804554}
{104,104,(533 赢 429),0.804878}
{105,105,(538 赢 433),0.804833}
{106,106,(543 赢 437),0.804788}
{107,107,(548 赢 441),0.804745}
{108,108,(554 赢 446),0.805054}
{109,109,(559 赢 450),0.805009}
{110,110,(564 赢 454),0.804965}
{111,111,(570 赢 459),0.805263}
{112,112,(575 赢 463),0.805217}
{113,113,(580 赢 467),0.805172}
{114,114,(585 赢 471),0.805128}
{115,115,(591 赢 476),0.805415}
{116,116,(596 赢 480),0.805369}
{117,117,(601 赢 484),0.805324}
{118,118,(606 赢 488),0.805281}
{119,119,(612 赢 493),0.805556}
{120,120,(617 赢 497),0.805511}
{121,121,(622 赢 501),0.805466}
{122,122,(627 赢 505),0.805423}
{123,123,(633 赢 510),0.805687}
{124,124,(638 赢 514),0.805643}
{125,125,(643 赢 518),0.805599}
{126,126,(648 赢 522),0.805556}
{127,127,(654 赢 527),0.80581}
{128,128,(659 赢 531),0.805766}
{129,129,(664 赢 535),0.805723}
{130,130,(669 赢 539),0.80568}
{131,131,(675 赢 544),0.805926}
{132,132,(680 赢 548),0.805882}
{133,133,(685 赢 552),0.805839}
{134,134,(690 赢 556),0.805797}
{135,135,(696 赢 561),0.806034}
{136,136,(701 赢 565),0.805991}
{137,137,(706 赢 569),0.805949}
{138,138,(712 赢 574),0.80618}
{139,139,(717 赢 578),0.806137}
{140,140,(722 赢 582),0.806094}
{141,141,(727 赢 586),0.806052}
{142,142,(733 赢 591),0.806276}
{143,143,(738 赢 595),0.806233}
{144,144,(743 赢 599),0.806191}
{145,145,(748 赢 603),0.80615}
{146,146,(754 赢 608),0.806366}
{147,147,(759 赢 612),0.806324}
{148,148,(764 赢 616),0.806283}
{149,149,(769 赢 620),0.806242}
{150,150,(775 赢 625),0.806452}
{151,151,(780 赢 629),0.80641}
{152,152,(785 赢 633),0.806369}
{153,153,(790 赢 637),0.806329}
{154,154,(796 赢 642),0.806533}
{155,155,(801 赢 646),0.806492}
{156,156,(806 赢 650),0.806452}
{157,157,(812 赢 655),0.80665}
{158,158,(817 赢 659),0.80661}
{159,159,(822 赢 663),0.806569}
{160,160,(827 赢 667),0.80653}
{161,161,(833 赢 672),0.806723}
{162,162,(838 赢 676),0.806683}
{163,163,(843 赢 680),0.806643}
{164,164,(848 赢 684),0.806604}
{165,165,(854 赢 689),0.806792}
{166,166,(859 赢 693),0.806752}
{167,167,(864 赢 697),0.806713}
{168,168,(869 赢 701),0.806674}
{169,169,(875 赢 706),0.806857}
{170,170,(880 赢 710),0.806818}
{171,171,(885 赢 714),0.80678}
{172,172,(890 赢 718),0.806742}
{173,173,(896 赢 723),0.80692}
{174,174,(901 赢 727),0.806881}
{175,175,(906 赢 731),0.806843}
{176,176,(912 赢 736),0.807018}
{177,177,(917 赢 740),0.806979}
{178,178,(922 赢 744),0.806941}
{179,179,(927 赢 748),0.806904}
{180,180,(933 赢 753),0.807074}
{181,181,(938 赢 757),0.807036}
{182,182,(943 赢 761),0.806999}
{183,183,(948 赢 765),0.806962}
{184,184,(954 赢 770),0.807128}
{185,185,(959 赢 774),0.807091}
{186,186,(964 赢 778),0.807054}
{187,187,(969 赢 782),0.807018}
{188,188,(975 赢 787),0.807179}
{189,189,(980 赢 791),0.807143}
{190,190,(985 赢 795),0.807107}
{191,191,(991 赢 800),0.807265}
{192,192,(996 赢 804),0.807229}
-----------------------------------
2 maxwin(扩展到996项)=
{0,1,1,2,3,3,4,5,6,6,7,8,9,9,10,11,12,13,13,14,
15,16,17,17,18,19,20,21,21,22,23,24,25,25,26,27,
28,29,29,30,31,32,33,33,34,35,36,37,37,38,39,40,
41,41,42,43,44,45,45,46,47,48,49,49,50,51,52,53,
53,54,55,56,57,57,58,59,60,61,61,62,63,64,65,65,
66,67,68,69,69,70,71,72,73,74,74,75,76,77,78,78,
79,80,81,82,82,83,84,85,86,86,87,88,89,90,90,91,
92,93,94,94,95,96,97,98,99,99,100,101,102,103,
103,104,105,106,107,107,108,109,110,111,111,112,
113,114,115,115,116,117,118,119,119,120,121,122,
123,124,124,125,126,127,128,128,129,130,131,132,
132,133,134,135,136,136,137,138,139,140,140,141,
142,143,144,145,145,146,147,148,149,149,150,151,
152,153,153,154,155,156,157,157,158,159,160,161,
162,162,163,164,165,166,166,167,168,169,170,170,
171,172,173,174,174,175,176,177,178,178,179,180,
181,182,183,183,184,185,186,187,187,188,189,190,
191,191,192,193,194,195,195,196,197,198,199,200,
200,201,202,203,204,204,205,206,207,208,208,209,
210,211,212,212,213,214,215,216,216,217,218,219,
220,221,221,222,223,224,225,225,226,227,228,229,
229,230,231,232,233,233,234,235,236,237,238,238,
239,240,241,242,242,243,244,245,246,246,247,248,
249,250,250,251,252,253,254,255,255,256,257,258,
259,259,260,261,262,263,263,264,265,266,267,267,
268,269,270,271,272,272,273,274,275,276,276,277,
278,279,280,280,281,282,283,284,284,285,286,287,
288,288,289,290,291,292,293,293,294,295,296,297,
297,298,299,300,301,301,302,303,304,305,305,306,
307,308,309,310,310,311,312,313,314,314,315,316,
317,318,318,319,320,321,322,322,323,324,325,326,
327,327,328,329,330,331,331,332,333,334,335,335,
336,337,338,339,339,340,341,342,343,344,344,345,
346,347,348,348,349,350,351,352,352,353,354,355,
356,356,357,358,359,360,361,361,362,363,364,365,
365,366,367,368,369,369,370,371,372,373,373,374,
375,376,377,378,378,379,380,381,382,382,383,384,
385,386,386,387,388,389,390,390,391,392,393,394,
395,395,396,397,398,399,399,400,401,402,403,403,
404,405,406,407,407,408,409,410,411,412,412,413,
414,415,416,416,417,418,419,420,420,421,422,423,
424,424,425,426,427,428,429,429,430,431,432,433,
433,434,435,436,437,437,438,439,440,441,441,442,
---
795,795,796,797,798,799,800,800,801,802,803,804}

3 maxwin直观列输出(n m loss,(n应m) m/n)=(共996项,摘录前101项)
{1,0,1,(1 赢 0),0.}
{2,1,1,(2 赢 1),0.5}
{3,1,2,(3 赢 1),0.333333}
{4,2,2,(4 赢 2),0.5}
{5,3,2,(5 赢 3),0.6}
{6,3,3,(6 赢 3),0.5}
{7,4,3,(7 赢 4),0.571429}
{8,5,3,(8 赢 5),0.625}
{9,6,3,(9 赢 6),0.666667}
{10,6,4,(10 赢 6),0.6}
{11,7,4,(11 赢 7),0.636364}
{12,8,4,(12 赢 8),0.666667}
{13,9,4,(13 赢 9),0.692308}
{14,9,5,(14 赢 9),0.642857}
{15,10,5,(15 赢 10),0.666667}
{16,11,5,(16 赢 11),0.6875}
{17,12,5,(17 赢 12),0.705882}
{18,13,5,(18 赢 13),0.722222}
{19,13,6,(19 赢 13),0.684211}
{20,14,6,(20 赢 14),0.7}
{21,15,6,(21 赢 15),0.714286}
{22,16,6,(22 赢 16),0.727273}
{23,17,6,(23 赢 17),0.73913}
{24,17,7,(24 赢 17),0.708333}
{25,18,7,(25 赢 18),0.72}
{26,19,7,(26 赢 19),0.730769}
{27,20,7,(27 赢 20),0.740741}
{28,21,7,(28 赢 21),0.75}
{29,21,8,(29 赢 21),0.724138}
{30,22,8,(30 赢 22),0.733333}
{31,23,8,(31 赢 23),0.741935}
{32,24,8,(32 赢 24),0.75}
{33,25,8,(33 赢 25),0.757576}
{34,25,9,(34 赢 25),0.735294}
{35,26,9,(35 赢 26),0.742857}
{36,27,9,(36 赢 27),0.75}
{37,28,9,(37 赢 28),0.756757}
{38,29,9,(38 赢 29),0.763158}
{39,29,10,(39 赢 29),0.74359}
{40,30,10,(40 赢 30),0.75}
{41,31,10,(41 赢 31),0.756098}
{42,32,10,(42 赢 32),0.761905}
{43,33,10,(43 赢 33),0.767442}
{44,33,11,(44 赢 33),0.75}
{45,34,11,(45 赢 34),0.755556}
{46,35,11,(46 赢 35),0.76087}
{47,36,11,(47 赢 36),0.765957}
{48,37,11,(48 赢 37),0.770833}
{49,37,12,(49 赢 37),0.755102}
{50,38,12,(50 赢 38),0.76}
{51,39,12,(51 赢 39),0.764706}
{52,40,12,(52 赢 40),0.769231}
{53,41,12,(53 赢 41),0.773585}
{54,41,13,(54 赢 41),0.759259}
{55,42,13,(55 赢 42),0.763636}
{56,43,13,(56 赢 43),0.767857}
{57,44,13,(57 赢 44),0.77193}
{58,45,13,(58 赢 45),0.775862}
{59,45,14,(59 赢 45),0.762712}
{60,46,14,(60 赢 46),0.766667}
{61,47,14,(61 赢 47),0.770492}
{62,48,14,(62 赢 48),0.774194}
{63,49,14,(63 赢 49),0.777778}
{64,49,15,(64 赢 49),0.765625}
{65,50,15,(65 赢 50),0.769231}
{66,51,15,(66 赢 51),0.772727}
{67,52,15,(67 赢 52),0.776119}
{68,53,15,(68 赢 53),0.779412}
{69,53,16,(69 赢 53),0.768116}
{70,54,16,(70 赢 54),0.771429}
{71,55,16,(71 赢 55),0.774648}
{72,56,16,(72 赢 56),0.777778}
{73,57,16,(73 赢 57),0.780822}
{74,57,17,(74 赢 57),0.77027}
{75,58,17,(75 赢 58),0.773333}
{76,59,17,(76 赢 59),0.776316}
{77,60,17,(77 赢 60),0.779221}
{78,61,17,(78 赢 61),0.782051}
{79,61,18,(79 赢 61),0.772152}
{80,62,18,(80 赢 62),0.775}
{81,63,18,(81 赢 63),0.777778}
{82,64,18,(82 赢 64),0.780488}
{83,65,18,(83 赢 65),0.783133}
{84,65,19,(84 赢 65),0.77381}
{85,66,19,(85 赢 66),0.776471}
{86,67,19,(86 赢 67),0.77907}
{87,68,19,(87 赢 68),0.781609}
{88,69,19,(88 赢 69),0.784091}
{89,69,20,(89 赢 69),0.775281}
{90,70,20,(90 赢 70),0.777778}
{91,71,20,(91 赢 71),0.78022}
{92,72,20,(92 赢 72),0.782609}
{93,73,20,(93 赢 73),0.784946}
{94,74,20,(94 赢 74),0.787234}
{95,74,21,(95 赢 74),0.778947}
{96,75,21,(96 赢 75),0.78125}
{97,76,21,(97 赢 76),0.783505}
{98,77,21,(98 赢 77),0.785714}
{99,78,21,(99 赢 78),0.787879}
{100,78,22,(100 赢 78),0.78}
{101,79,22,(101 赢 79),0.782178}
--------------------------------

KeyTo9_Fans

这个 0.807（还在增加中）：

{192,192,(996 赢 804),0.807229}

和这个问题二里面的 C(1/2)≈0.811 很接近：

https://www.cnblogs.com/v-July-v/archive/2011/02/26/1983673.html



这两个数会不会相等呢？

如果能证实相等，就是一个重大发现了，可以发表学术论文的。

dlpg070

KeyTo9_Fans 发表于 2020-7-30 18:40
这个 0.807（还在增加中）：

{192,192,(996 赢 804),0.807229}

一个连接:               
J. D. Dixon, Longest common subsequences in binary sequences,
[math.GR], 2013.
https://arxiv.org/abs/1307.2796
给出 L(n,n)/n 9个估值
我仿照Dixon的方法计算12个点 n最大=65536 , 耗时10000秒
猜想 C1/2=gamma_2>0.8113 ,不等于 0.811

序号 n    均值     均方差      (    估值区间     ) 耗时 秒
{1, 32,   0.751875,0.032025,   (0.71985, 0.7839  ),0.0020002}
{2, 64,   0.777188,0.020825,   (0.756363,0.798013),0.0040002}
{3, 128,  0.788281,0.012875,   (0.775406,0.801156),0.0150008}
{4, 256,  0.796406,0.0116,     (0.784806,0.808006),0.0590034}
{5, 512,  0.800938,0.00539688, (0.795541,0.806335),0.260015}
{6, 1024, 0.805234,0.00443125, (0.800803,0.809665),1.18707}
{7, 2048, 0.806836,0.00277734, (0.804059,0.809613),5.52532}
{8, 4096, 0.809087,0.00147012, (0.807617,0.810557),25.1524}
{9, 8192, 0.81002, 0.0011166,  (0.808903,0.811137),113.417}
{10,16384,0.810876,0.000735352,(0.810141,0.811611),499.713}
{11,32768,0.811442,0.00050293, (0.810939,0.811945),2168.1}
{12,65536,0.811679,0.000346851,(0.811332,0.812026),9737.26}

dlpg070

dlpg070 发表于 2020-8-3 21:06
一个连接:               
J. D. Dixon, Longest common subsequences in binary sequences,
[math ...

KeyTo9_Fans的精确数据an太好了,遗憾n还不够大
通常用统计方法给出估值
下面比较KeyTo9_Fans的精确数据和我的统计结果
结果表明 :全部9项的精确值均在我的估值的 1 均方差之内!!!,统计结果正确
,足见这些精确值的重要 ,Dixon的统计方法是个好方法
说明:这里的KeyTo9_Fans的精确数据,由an计算maxwin数列,再提取给定条件的项得到
   n    nean   meandev  Fans   mean-Fans  

{1,2,  0.5,     0.18,      0.5,      0.,       (2 赢 1)}
{2,4,  0.64,    0.1632,    0.5,      0.14,     (4 赢 2)}
{3,8,  0.72,    0.0908,    0.625,    0.095,    (8 赢 5)}
{4,16, 0.71875, 0.055,     0.6875,   0.03125,  (16 赢 11)}
{5,32, 0.751875,0.032025,  0.75,     0.001875, (32 赢 24)}
{6,64, 0.777188,0.020825,  0.765625, 0.011563, (64 赢 49)}
{7,128,0.788281,0.012875,  0.789063,-0.0007815,(128 赢 101)}
{8,256,0.796406,0.0116,    0.796875,-0.000469, (256 赢 204)}
{9,512,0.800938,0.00539688,0.804688,-0.0037495,(512 赢 412)}

dlpg070

dlpg070 发表于 2020-8-4 11:23
KeyTo9_Fans的精确数据an太好了,遗憾n还不够大
通常用统计方法给出估值
下面比较KeyTo9_Fans的精确 ...

根据最近我的统计计算的结果和KeyTo9_Fans'的计算结果得到的Maxwin数列
画图观察渐进过程,明显逼近极限值 = 约0.811

dlpg070

dlpg070 发表于 2020-8-8 12:34
根据最近我的统计计算的结果和KeyTo9_Fans'的计算结果得到的Maxwin数列
画图观察渐进过程,明显逼近极 ...

一个外行的猜想,一个认真的笑话
对我的统计计算数据做曲线拟合,求极限,估计误差
拟合函数类似:
   f(x)= a + b * ArcTan[x^c]
得到C1/2=gamma_2估值如下:
   
   极限= 0.81230 ,标准差= 0.00052
   0.81177 <= gamma_2 <= 0.81283
也许有点靠谱!!!请专家们论证吧
我将继续研究游戏策略
参考图:

KeyTo9_Fans

把局数从$1000$扩展到$100000$，结果是$100000$局赢$81065$局。

胜率的预估极限值是$0.81071\pm 0.00003$。

胜率随局数变化的拟合曲线如下图所示：

拟合曲线

曲线的函数式如下：

User-Defined Model: $y=a-b/x^c$
Coefficient Data:
$a=0.81071306$
$b=1.5749541$
$c=0.87848309$

#####

把局数扩大到$1000000$，结果是赢$810703$局。

胜率的预估极限值是$0.810711\pm 0.000004$。

拟合曲线的函数式更新如下：

User-Defined Model: $y=a-b/x^c$
Coefficient Data:
$a=0.81071089$
$b=1.5518589$
$c=0.88158212$

接下来需要找到随机序列的最长公共子序列长度的精确数据，才能进一步确认或否定两个问题的结果相等。

KeyTo9_Fans

该楼留空，以后再编辑......

#####KeyTo9_Fans于2021-11-3编辑了此贴#####

根据 https://arxiv.org/pdf/1307.2796.pdf 里面的数据：



长度为16384的随机01序列的最长公共子序列与16384的比值已经达到0.8111±0.0002了，

n继续增大后，这个值还会增大一些，好像要比智取黑白配问题的极限值0.8107要大。

然后 @dlpg070 也声称极限是0.8117±0.0004，好像也比0.8107要大。

我接下来自己设计程序，跑久一点，看看是不是真的比0.8107大。

是的话，“两个问题的结果相等”这个猜想就不成立了，

只能说两个问题的结果因为巧合，非常接近。

#####2021-11-5#####

24小时跑了5218例，得到LCS的$C_{0.5}(n)$的68%置信区间如下：



#####2021-11-17#####

10天跑了52012例，得到LCS的$C_{0.5}(n)$的68%置信区间如下：



也就是说，

公共子序列问题在 n=131072 的结果是0.811896±0.000001

智取黑白配问题在n=1000000的结果是0.810711±0.000004

前者比后者大了很多。

所以接下来我们应该把智取黑白配的关注点从最坏情况改为平均情况，

看看后面这个0.810711会增加多少，有没有可能和前面这个0.811896相等。