【报数拆区间】游戏的最佳策略

mathe

3个选手时，去除总数不超过12的特殊情况，
5000以内所有不可以采用方案12的情况只有以下各种:
[26, 27, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 54, 55, 56, 57, 58, 59, 62, 63, 66, 67, 71, 74, 75, 83, 84, 87, 91, 92, 95, 96, 97, 103, 104, 110, 118, 122, 130, 131, 138, 139, 142, 143, 150, 151, 153, 157, 171, 176, 188, 194, 200, 206, 208, 218, 231, 243, 247, 259, 265, 266, 267, 271, 277, 278, 279, 289, 294, 306, 312, 314, 324, 326, 338, 382, 406, 429, 441, 487, 499, 522]
可以看出，在数目超过522以后，应该总是可以采用方案12。

mathe

3个人的情况，对于数目充分大以后，如果n个数，那么最终输的概率都可以写成一个分母为n的分数，而三个人的分子相差会很小，其中先手总是最小，而另外两人分子比第一人最多多2，总共可用的模式很少，而12也是一个满足这种模式的情况，这可能为什么我们总是能够得出策略12符合条件。
而对于充分大的数据，通过计算机穷举验证前面那些不符合条件的模式以及符号运算符合条件模式之间的大小比较，就应该可以证明对于充分大的n,总是可以使用模式12的

mathe

对于三个人和充分大的n，经过计算可以直到，三个人输的概率模式分别如下
n=3k时,有三种模式
$P_0: k/n, k/n, k/n$
$P_1: {k-1}/n, {k+1}/n, k/n$
$P_2: {k-1}/n, k/n, {k+1}/n$
n=3k+1时，有三种模式
$Q_0: k/n, {k+1}/n, k/n$
$Q_1: {k-1}/n, {k+1}/n,{k+1}/n$
$Q_2: k/n, k/n, {k+1}/n$
n=3k+2时，只有一种模式
$R: k/n, {k+1}/n, {k+1}/n$
而选择第12个数是最优的理由是留下一个11个数的模式，其概率分布为$5/11,4/11,2/11$, 这是一种给小弟概率充分大，而自己下一轮概率充分小的方案。
验算可以知道，选第12个数的方案会将概率分布$P_0$转化为$P_1$,而$P_1$转化为$P_2$,而$P_2$转化为$P_0$
   同样选第12个数的方案会将概率分布$Q_0$转化为$Q_1$,而$Q_1$转化为$Q_2$,而$Q_2$转化为$Q_0$
  而选第12个数会将概率分布$R$转化为$R$
所以得出最终对于充分大的时候，模式是以36为周期，这个规律验算以后对于$547<=n<=2000$都成立。
由于模式计算公式是线性的，规律成立的部分已经远远超过一半多36，这说明后面必然周期性都成立了。
而一个周期内的概率模式应该是$P_0,Q_0,R,P_1,Q_1,R,P_1,Q_1,R,P_0,Q_0,R,P_1,Q_1,R,P_2,Q_2,R,P_2,Q_2,R,P_1,Q_1,R,P_2,Q_2,R,P_0,Q_0,R,P_0,Q_0,R,P_2,Q_2,R$。其中第一个模式是n是36的倍数时

mathe

现在假设有k个人n个数的情况，我们定义数组
\[\begin{cases}a_1(0)=&a_2(0)=&a_3(0)=&\dots=&a_k(0)=0\\
a_1(1)=k-1,&a_2(1)=&a_3(1)=&\dots=&a_k(1)=-1\end{cases}\]
然后递归定义
\[\begin{cases}
a_1(n)&=&\min_{1\le h\le n} &\{k-1+a_k(h-1)+a_k(n-h)\}\\
a_2(n)&=&\max_{\begin{cases}1\le h\le n\\k-1+a_k(h-1)+a_k(n-h)=a_1(n)\end{cases}} &\{a_1(h-1)+a_1(n-h)-1\}\\
a_3(n)&=&\max_{\begin{cases}1\le h\le n\\k-1+a_k(h-1)+a_k(n-h)=a_1(n)\\a_1(h-1)+a_1(n-h)-1=a_2(n)\end{cases}} &\{a_2(h-1)+a_2(n-h)-1\}\\
a_4(n)&=&\max_{\begin{cases}1\le h\le n\\k-1+a_k(h-1)+a_k(n-h)=a_1(n)\\a_1(h-1)+a_1(n-h)-1=a_2(n)\\a_2(h-1)+a_2(n-h)-1=a_3(n)\end{cases}} &\{a_3(h-1)+a_3(n-h)-1\}\\
&&\dots\\
a_k(n)&=&\max_{\begin{cases}1\le h\le n\\k-1+a_k(h-1)+a_k(n-h)=a_1(n)\\a_1(h-1)+a_1(n-h)-1=a_2(n)\\\dots\\a_{k-2}(h-1)+a_{k-2}(n-h)-1=a_{k-1}(n)\end{cases}}&\{a_{k-1}(h-1)+a_{k-1}(n-h)-1\}
\end{cases}\]
这样定义的好处是所有的$a_u(v)$都是整数，而且$\sum_{h=1}^k a_h(n)=0$,而且最优策略下k个人选择n个数，各人输的概率分别就是\(\frac{n+a_1(n)}{kn},\frac{n+a_2(n)}{kn},\dots,\frac{n+a_k(n)}{kn}\)
也就是计算\(a_1(n)\)时，我们需要测试所有的n个可能的h，找到其中使得\(k-1+a_k(h-1)+a_k(n-h)\)最小的那些$h$
而计算\(a_2(n)\)时，我们只需要测试计算\(a_1(n)\)时余下的那些$h$,然后在其中找出使得\(a_1(h-1)+a_1(h-n)\)最大的$h$,依次类推。
而计算的关键在于第一步，因为通常第一步计算以后，能使\(a_1(n)\)达到最小的$h$余下的数目应该不多。
而为了能够快速查找\(k-1+a_k(h-1)+a_k(n-h)\)的最小值，一种比较有效的方法是将所有的\(a_k(.)\)从小到大排列，优先使用最小的\(a_k(.)\)。而事实上\(a_k(.)\)的取值范围应该不大，可以通过使用几个动态数组来保存即可。

mathe

3人结果很好。但是4人结果就很不规律了，总体上来说，先选择的人会略有优势。
比如4个人，通过14#算法，计算得出$a_n(k)$的局部信息,而{}内是可选的最优策略,
越小的数字代表对应人概率越小(数字除以前面编号在加1/4就代表概率）
可以看出挑选463的方案最多，因为462个数的分布为:
462     :6,     26,     14,     -46:{295}
其中最后一个人输的概率特别小。
99906   :-22,   -22,    10,     34:{11966}
99907   :-31,   -7,     29,     9:{463}
99908   :-28,   -4,     16,     16:{463}
99909   :-13,   -21,    11,     23:{463}
99910   :-26,   -6,     14,     18:{463}
99911   :-15,   -15,    5,      25:{463}
99912   :-24,   -8,     16,     16:{463}
99913   :-25,   -29,    15,     39:{92356}
99914   :-22,   -14,    10,     26:{92356,6705,93210}
99915   :-19,   -11,    17,     13:{463}
99916   :-28,   -16,    16,     28:{463}
99917   :-37,   -9,     23,     23:{463}
99918   :-26,   -10,    6,      30:{463}
99919   :-23,   -11,    9,      25:{463}
99920   :-8,    -12,    -4,     24:{463}
99921   :-21,   -5,     7,      19:{463}
99922   :-22,   -6,     10,     18:{463}
99923   :-27,   -7,     9,      25:{463}
99924   :-4,    -12,    -16,    32:{7593}
99925   :-17,   -21,    7,      31:{92356}
99926   :-26,   2,      18,     6:{463}
99927   :-19,   -3,     9,      13:{463}
99928   :-16,   -8,     0,      24:{91087,8842}
99929   :-21,   -17,    15,     23:{463}
99930   :-34,   -6,     30,     10:{92356,7575}
99931   :-15,   -15,    -3,     33:{71475,28457}
99932   :-24,   -8,     20,     12:{463}
99933   :-29,   -21,    11,     39:{6705,93229}
99934   :-38,   -10,    14,     34:{92356,7579}
99935   :-23,   -15,    9,      29:{463}
99936   :-24,   -8,     12,     20:{463}
99937   :-21,   -17,    7,      31:{463}
99938   :-22,   -22,    18,     26:{463}
99939   :-23,   -27,    17,     33:{463}
99940   :-20,   -8,     12,     16:{463}
99941   :-25,   -13,    19,     19:{463}
99942   :-14,   -18,    -2,     34:{463}
99943   :-15,   -15,    17,     13:{463}
99944   :-16,   -28,    4,      40:{11966}
99945   :-13,   -21,    3,      31:{463}
99946   :-2,    -6,     -6,     14:{463}
99947   :-31,   -15,    21,     25:{463}
....
3999971 :-35,   -19,    17,     37:{11966,3988006}
3999972 :-20,   -8,     12,     16:{463}
3999973 :-21,   -17,    15,     23:{463}
3999974 :-26,   -10,    14,     22:{463}
3999975 :-27,   -23,    9,      41:{11966}
3999976 :-12,   -32,    8,      36:{319}
3999977 :-29,   -21,    11,     39:{463}
3999978 :-14,   -30,    18,     26:{48}
3999979 :-11,   -15,    9,      17:{463}
3999980 :-12,   -24,    0,      36:{463}
3999981 :-9,    -13,    -1,     23:{463}
3999982 :-10,   -26,    2,      34:{1522320}
3999983 :-15,   -19,    13,     21:{463}
3999984 :-8,    -4,     -4,     16:{463}
3999985 :-25,   -9,     11,     23:{463}
3999986 :-14,   -18,    14,     18:{319}
3999987 :-15,   -7,     5,      17:{463}
3999988 :-16,   -4,     20,     0:{463}
3999989 :-17,   -25,    19,     23:{48}
3999990 :-30,   -10,    18,     22:{463}
3999991 :-19,   -31,    9,      41:{483774,3516218}
3999992 :-24,   -8,     16,     16:{463}
3999993 :-21,   -13,    7,      27:{463}
3999994 :-18,   -22,    14,     26:{463}
3999995 :-19,   -35,    1,      53:{1481950}
3999996 :-20,   -24,    4,      40:{463}
3999997 :-25,   -9,     7,      27:{463}
3999998 :-22,   -18,    2,      38:{463}
3999999 :-19,   -23,    13,     29:{463}
...
9999979 :-11,   -3,     9,      5:{169}
9999980 :-36,   -8,     16,     28:{463}
9999981 :-21,   -21,    23,     19:{463}
9999982 :-26,   -6,     6,      26:{463}
9999983 :-35,   -7,     5,      37:{463}
9999984 :-32,   -4,     20,     16:{463}
9999985 :-25,   -17,    23,     19:{463}
9999986 :-22,   -30,    18,     34:{463}
9999987 :-19,   -19,    5,      33:{112846}
9999988 :-36,   -16,    20,     32:{463}
9999989 :-9,    -21,    3,      27:{463}
9999990 :-10,   -34,    10,     34:{319}
9999991 :-19,   -23,    9,      33:{463}
9999992 :-20,   -16,    8,      28:{463}
9999993 :-17,   -5,     15,     7:{2598}
9999994 :-18,   -10,    2,      26:{463}
9999995 :-11,   -15,    1,      25:{5675640}
9999996 :-20,   -16,    16,     20:{463}
9999997 :-25,   -13,    11,     27:{463}
9999998 :-10,   -10,    10,     10:{1189,9998810}
9999999 :-11,   -27,    13,     25:{319}
...
39999984        :-12,   -8,     0,      20:{463}
39999985        :-25,   -25,    15,     35:{319}
39999986        :-26,   -22,    18,     30:{463}
39999987        :-23,   -19,    17,     25:{463}
39999988        :-24,   -24,    20,     28:{319}
39999989        :-13,   -17,    7,      23:{27244457}
39999990        :-22,   -18,    6,      34:{463}
39999991        :-19,   -19,    9,      29:{11966}
39999992        :-16,   -24,    8,      32:{463,7870}
39999993        :-17,   -21,    11,     27:{463}
39999994        :-14,   -22,    -2,     38:{463}
39999995        :-19,   -15,    5,      29:{463}
39999996        :-8,    -20,    -4,     32:{463}
39999997        :-13,   -13,    7,      19:{463}
39999998        :-6,    -6,     -6,     18:{463}
39999999        :-11,   -15,    13,     13:{10655572,29344428}