有两堆石子,一堆100个,一堆150个,现两人轮流取石子,一次可从一堆中取若干个,或从两堆中取相等个.谁将全部取完则谁胜.则先手还是后手有必胜策略?

Question

有两堆石子,一堆100个,一堆150个,现两人轮流取石子,一次可从一堆中取若干个,或从两堆中取相等个.
谁将全部取完则谁胜.则先手还是后手有必胜策略?

Answer 1

这个是一个博弈,把小的一堆除以黄金分割比例,得到a,如果小的那堆加上a等于较大的那堆,那么先取必败,否则先取必胜,证明用到斐波拉契矩阵,贝蒂定理
此题先取必胜
你是必胜态,无论对方怎么取,你都能创造一个必败态,例如,本题你两堆同时取20,就创造一个必败态给对手了
100 150 --> 80 130
附：所有100内的必败态（其他当然就是必胜态,100 150就是必胜）
1 2
3 5
4 7
6 10
8 13
9 15
11 18
12 20
14 23
16 26
17 28
19 31
21 34
22 36
24 39
25 41
27 44
29 47
30 49
32 52
33 54
35 57
37 60
38 62
40 65
42 68
43 70
45 73
46 75
48 78
50 81
51 83
53 86
55 89
56 91
58 94
59 96
61 99
63 102
64 104
66 107
67 109
69 112
71 115
72 117
74 120
76 123
77 125
79 128
80 130
82 133
84 136
85 138
87 141
88 143
90 146
92 149
93 151
95 154
97 157
98 159
100 162