热身题
尝试寻找单次变化递推式，设第\(i\)个圆为\(X^2+Y^2=R^2\)，在圆\(i\)内随机选择一点\((x,y)\)
\[E(a^2+b^2)->E((a+x)^2+(b+y)^2) \] \[=E(a^2+b^2)+E(x^2+y^2)+2aE(x)+2bE(y) \] \[E(x)=E(y)=0 \]设\(x^2+y^2=r^2\)
\[E(x^2+y^2)=\int_{0}^{R}\frac{2\pi r}{\pi R^2}r^2=\frac{R^2}{2} \]综上
\[ans=\sum_{i=1}^{n}\frac{R_i^2}{2} \]巴士博弈
只有一堆\(n\)个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取\(m\)个，最后取光者胜
当\(n\%(m+1)==0\)时，先手必输，否则先手必胜
证明：当\(n\%(m+1)==0\)时，无论先手取多少\(s\)，后手都可以取\(m+1-s\)来保证剩余数量永远是\((m+1)\)的倍数
此时是一个先手必败态，简称必败态
当\(n\%(m+1)\neq 0\)时，先手可以取走\(n%(m+1)\)来让游戏进入到必败态从而先手获胜
威佐夫博弈
两人轮流取两堆筹码，可以从其中一堆中取走任意个筹码，也可以从两堆中取走相同数量的筹码，最后取完的一方获胜
假设\((0,0)\)是必败态
那么\((0,k),(k,k),(k,0)\)是必胜态
递推递推懒得加图了
设必败态为\((a_1,b_1),(a_2,b_2)……(a_n,b_n)\)
其中\(a_i<b_i\)
那么\(b_i=a_i+i\)
\[a_i=i*\phi,b_i=i*\phi^2 \] \[\phi+1=\phi^2,i*\phi+i=i*\phi^2,\phi=\frac{\sqrt{5}+1}{2} \]通项公式证明：
假设\(W\)是必败点集，\(W\)中的点有三个条件
\(1.W\)中的点不能一步走到\((0,0)\)
\(2.W\)中的任何一个点不能一步变成\(W\)中的另外一个点
\(3.W\)之外的任何一个非零数对可以一步走到\((0,0)\)或\(W\)中的点对
\(W\)满足三个性质就可以刚好满足要求：
\(1.W\)不重不漏的包含每个整数
\(2.W\)中每对数字差值为\(1,2,3……\)
\(3.W\)中各项里较小数依次递增
条件\(1、2\)很好满足
条件\(3\)，设\(W\)外的数对\((x,y),x<y\)，根据性质\(1\),\(W\)中存在一个数对包含\(x\)
若\(W\)中数对为\((a,x),a<x\)，那么\(y>x>a\)，\(y\)一定能变成\(a\)
若\(W\)中数对为\((x,b),x<b\),此时若\(y>b\)那么\(y\)一定能变成\(b\)，若\(y<b\)，说明\(y-x=d<b-x=d'，W\)中存在某个数对\((a',b')\)满足\(b'-a'=d\),而且\(x>a',b>b'\)
由于\(a'<x,a'+d=b',b'<y\)，所以可以让\((x,y)\)减去某个相同数字变成\(W\)中的数对
证明\(W(a_i,b_i)\)满足三个性质：
性质二：
\[a_i=i*\phi,b_i=i*\phi^2 \] \[\phi+1=\phi^2 \] \[i\phi^2-i\phi=i \]性质三白给
性质一：
\(Beatty-Rayleigh\)定理：
如果有无理数\(α\)和\(β\)
满足\(\frac{1}{α}+\frac{1}{β}=1\)
那么\(α、2α……\)和\(β，2β……\)不重不漏地包含每个整数
有\(\frac{1}{\phi}+\frac{1}{\phi^2}=1\)
证明定理：(原视频证明疑似有大锅，证明来自百度百科)
设\(P=\{\lfloor α \rfloor,\lfloor 2α \rfloor,……\},Q=\{\lfloor β \rfloor,\lfloor 2β \rfloor,……\}\)
\(1.\)证明\(P∩Q=Ø\)
反证：若存在\(\lfloor nα\rfloor = \lfloor mβ \rfloor=k\)，即 \(k-1<nα、mβ<k\)
同除\(n\)或\(m\)取倒数
则\(\frac{n}{k+1}<\frac{1}{α}<\frac{n}{k}，\frac{m}{k+1}<\frac{1}{β}<\frac{m}{k}\)
相加得
\(\frac{n+m}{k+1}<1<\frac{n+m}{k}\)
\(k<n+m<k+1\)
与\(n、m\)是整数矛盾
\(2.\)证明\(P∪Q=N^{+}\)
反证：假设\(k∈N^{+}\)且\(k∉P∪Q\)
则存在\(n,m\)使得\([nα]<k<[(n+1)α],[mβ]<k<[(m+1)β]\)
所以\([nα]<k≤[(n+1)α]-1<(n+1)α-1\)
即\(\frac{n}{k}<\frac{1}{α}<{n+1}{k+1}\)
两式相加
\(\frac{n+m}{k}<1<\frac{n+m+2}{k+1}\)
即\(n+m<k<k+1<n+m+2\)与\(n,m,k\)都是正整数矛盾
必胜态，必败态
\(1.\)任何游戏的终点的必败态
\(2.\)至少有一种操作必胜态可以走向必败态
\(3.\)无论怎么操作必败态只能走向必胜态