日漫《欺诈游戏》挺好看，推荐。
最近又刷了一遍，里边有两个数学问题，做下笔记。
一、少数决
一票人参加一个叫少数决的游戏，游戏规则：
- 主办方随机抽取一个人到台上来，向众人问一个二选一的问题，问题内容不限，只要是能用“YES”、“NO”回答的二选一问题就行。
- 每个人手里都会得到两张选票，两张选票上都印有自己的名字，但其中一张纸上印有“YES”，另一张纸上印有“NO”。游戏者们有6个小时的时间进行交流和考虑，并要在时间结束前将自己的选择投入投票箱。
- 时间结束后，主办方进行唱票，并规定票数较少的那一方获胜，票数较多的多数派将全部被淘汰。
- 获胜的少数派选手将进行新一轮的游戏，主办方从剩下的人中重新选一位进行二选一提问，并要求大家在6个小时内投票，唱票后仍然宣布少数派胜出。
- 若某次投票后双方人数相等，则该轮游戏无效，继续下一轮。
- 游戏一直进行下去，直到最后只剩下一人或两人为止（只剩两人时显然已无法分辨胜负）。
- 所有被淘汰的人都必须缴纳罚金，这些罚金将作为奖金分给获胜者。
这个游戏乍一看并没有什么思路，因为它不同于多数决，无法通过与半数以上的人结成同盟来确保胜利。但稍微转个弯，就可以想到一种不败的办法。
少数决本质是个不严格的二分过程，不严格在于每次取的都是少数那部分。从不严格二分这点出发，可以得出一个结论：游戏进行的次数必然小于等于 \(\lfloor log_2N \rfloor\) ，其中N为参加游戏的人数。
- 游戏次数不可能大于 \(log_2N\) 。如果游戏次数大于\(log_2N\)，那么 \(游戏人数 \geq 2^{游戏次数} > 2^{log_2N} = N = 游戏人数\)，得出了游戏人数大于游戏人数的悖论。
- 游戏次数不可能等于 \(log_2N\) 。如果 \(log_2N\) 为小数，游戏次数应为整数，必然不等。如果 \(log_2N\) 为整数，只有在严格二分的情况下，即每轮游戏都是对半分，\(2^{游戏次数}\) 才能等于N。由于游戏规定“YES”和“NO”投票人数相同时需重新投票，因此每次留下的玩家人数必然小于之前玩家人数的一半，不可能实现严格二分。所以游戏进行的次数一定小于：\(log_2N\)。
- 小于 \(log_2N\) 的最大正整数： \(\lfloor log_2N \rfloor\)。
基于以上推论，在游戏中只要能够与： \(2^{\lfloor log_2N \rfloor}\) 或 \(2^{log_2N - 1}(log_2N为整数时)\) 个玩家组成同盟，每次对半投票就能保证同盟中有人能够坚持到最后胜利。
但以上情况还不是最优解，下边是两个例子：
- 玩家31人时，第一轮最多留15人，第二轮最多留7人，第三轮最多留3人，第四轮留1人。游戏可以撑满 \(\lfloor log_231 \rfloor = 4\) 轮。因此结盟人数16人是必要的。
- 玩家22人时，第一轮最多留10人，第二轮最多留4人，第三轮留1人。游戏最多只能进行3轮，因此结盟人数8人就可以保证不败。
准确的游戏轮数 i 算法应该是：
- \(n = \lfloor {(N-1)/2} \rfloor\) ，i = 1;
- \(n = \lfloor (n-1)/2 \rfloor\)，while(n > 2) i++;
算法公式：\(i = \lfloor {log_2(N+1)} \rfloor - 1\)
二、光明与黑暗
光明与黑暗是一个简单的概率计算问题，只是觉得概率轮是个很神奇的知识。
先说结论：每局33%的概率，想要先赢10局的概率只有6%；每局40%的概率，先赢10局的概率也只有18%。
游戏规则：
- 两张扑克牌，一张牌两面都是黑，一张牌一面白一面黑。
- 两张牌放在袋子里，每局随机从袋子里拿出一张牌放在桌上。
- 如果拿出的牌白面朝上，则重新拿。
- 如果拿出的牌黑面朝上，则继续游戏。
- 将拿出的这张牌反过来，如果是白面则本局我方胜，如果是黑面则本局对方胜。
- 先胜10局的获得最终胜利。
这个游戏乍一看还算公平，但稍微了解一点概率的童鞋就能看出来，双方单局获胜的概率不同。总共会出现的情况：
白（黑白牌），无效
黑（黑白牌），我方胜
黑（黑黑牌），对方胜
黑（黑黑牌），对方胜
白面朝上的情况被ban掉后，我方单局胜的情况就是1/3了，这样要想先胜10局的概率只有6%。
具体计算代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Probability {
/**
* p概率，先赢n把的概率
*
* @param p 每把游戏胜利的固定概率p
* @param n 先赢多少把
*/
public static double solution(double p, int n) {
double base = Math.pow(p, n);
double combination = 0.0;
for (int i = 0; i < n; i++) {
/*
* 我方先赢n把，要把对方已赢0，1，2，...，n-1把的情况都算上。
* 对方已赢i把的所有情况数：Cnm(n+i-1, i)，n+i是总数，-1是因为最后一把是我方赢，对方不能选。
* 对方已经i把的概率：Math.pow((1.0 - p), i)
*/
combination += Cnm(n + i - 1, i) * Math.pow((1.0 - p), i);
}
return base * combination;
}
/**
* 排列组合
*
* @param n 总数
* @param m 取数
* @return 组合数
*/
private static long Cnm(int n, int m) {
long divisor = 1;
long dividend = 1;
for (int i = 1; i <= m; i++) {
divisor *= i;
dividend *= n + 1 - i;
}
return dividend / divisor;
}
public static void main(String[] args) {
System.out.println(solution(1 / 3.0, 10));
}
}