How to slove it,3

假设有一个硬币，抛出字（背面）和花（正面）的概率都是0.5，而且每次抛硬币与前次结果无关。
现在做一个游戏，连续地抛这个硬币，直到连续出现两次字为止，问平均要抛多少次才能结束游戏？
注意，一旦连续抛出两个“字”向上游戏就结束了，不用继续抛。


另外一个变形是，硬币铸造时有差错，抛出字和花的概率分别是p和1-p （0<=p<=1），问平均要抛多少次才能结束这个游戏。 设 字为A 花为B， 把抛出来的结果写成字符串， 现在求 *不连续* 构成两个A 的字符串组合数。 用向量 [A B] 表示 [尾为A的组合数 尾为B的组合数]， 因为A后面只能接B，而B后面可以接A或B，所以状态转移矩阵 M 是 0 1 1 1 一次结果：A、B [A1 B1] = [1 1] 两次结果：AB、BA、 BB [A2 B2] = M*[A1 B1] = = [1 2] 三次结果： [A3 B3] = M*[A2 B2] = = [2 3] 四次结果： [A4 B4] = M*[A3 B3] = [3 5] A1，A2，A3....An 这个数列的意义是，抛n 次，得到*非终止*序列的 而且最后一次为 A 的组合数。 只要在这些组合后面再抛一次 A 即可得到终止序列。 从上面可以看出 An 正是斐波那契数 F(n)，可以直接代入通项公式。 所以抛 n 次得到终止序列的概率为 F(n-1)/2^n 得到终止序列的抛硬币次数期望为：2*F(1)/2^2 + 3*F(2)/2^3 + 4*F(3)/2^4 + ....

A_n是斐波那契数有组合意义, 只要讨论前两个次试验的情况, 如果第一次是B, 后面构成A_(n-1)结构, 如果第一次是A, 则第二次必须是B, 于是后面构成A_(n-2)结构, 于是在考察一下A_1和A_2就可以了.

对于期望的计算, 可以考虑生成函数.

设
G(x) = F(1)/2^2 * x^2 + F(2)/2^3 * x^3 + F(3)/2^4 * x^4 + ...
将递归关系带入得到
G(x) = x/(4-2x-x^2)

于是那个无限求和的期望就等于 G'(1)=4. 注意这个期望是最后两次A之前的试验次数, 故加上最后两次A就是期望6了.

How To Solve It,2

Problem：100根火柴，两个人轮流取，每个人每次只能取1~7根，谁拿到最后一根火柴谁赢；问有必胜策略吗，有的话是先手还是后手必胜？
问题很简单，也就是我先前提到的逆向思维的拓展问题之一。
采取递归的思维方式，请先回忆一下汉诺塔问题。
拿到最后一根火柴为胜者，即在对手取最后一轮时，火柴最多只能剩7根，多则溢少则输。
换句话说，必胜策略：胜者取完倒数第二轮后，剩余火柴为8根。此时无论输者取几根都是输。根据100-8=92，可知，胜者必须取到第92根。
呵呵，到这里了，同样应用同种原理，胜者必须取到92-8=84，第84根。
如此，tsutsukeru
92，84，76，……，12，4.
由于4<7，故先手必胜。

还有个可用类似思维方式的题，来自《编程之美》
两堆橘子，各为m和n个，两人轮流拿，拿的时候你只能选择某一堆在里面拿（即不能跨堆拿），你可以拿1~这堆里面所有剩下的个橘子，谁拿到最后一个橘子谁赢；问题同上。