难题集合

倪举鹏

1.一个坛子里有 n 个不同颜色的小球，然后每次取出两个，将第二个球染成第一个球的颜色,再把两个球都放回坛子里。问平均需要几次可以将 n 个球都染为同色？
2.在平面上有一个发光点P，P可以向所有的方向发射任意长度的光，如果这些光射到圆周上则按反射定律反射，
问：是否可能恰当的安排有限个圆(它们任意两个不相交也不相切，而且P点在所有的这些圆的外面)，挡住从P点出发的所有的光线呢？
换个说法就是：存在一个大圆，使得在这个大圆外看不到任何光线？
3.在平面上直径为1的等宽凸形总能内切于两条距离为1的平行线，它的周长必为π，直径为1的三维等宽凸体也总能内切于两个距离为1的平行平面，那么它的表面积是否也是定值？
4.在n*n的国际象棋棋盘上，至少放需要放多少个“后”，才能使所有格子都被这些“后”所控制（“后”所在的格子视为被控制）
5.直径为1的n边形的面积最大是多少？(n为常数)
提醒：并非当n边形为正n边形时面积最大。
6.跑道是一条无限长的直线，龟兔在0点同时出发，乌龟匀速每２秒向右爬一米；兔子每一秒跳一次(每次跳一米)，兔子是瞎的, 左右瞎跳(每一次跳左跳右的概率各为1/2)，请问兔子追上乌龟的可能性是多大(跳过和恰好跳到都算追上)？
7.有一道n选一的选择题，你现在有一个硬币，可以以1/2的概率无数次独立的掷出正面与反面，
问题：怎么设计方案，使得你可以以1/n的概率选择每一个选项，而掷硬币的次数的期望最小?

yigo

第1题
经过题目中的操作，考虑n个球可能出现的颜色状态种类（所谓颜色状态是指统计出各种颜色的球的数量按多到少排序）为
\(x_1+x_2+x_3+...+x_n=n的非负整数解的个数，其中x_1 \geq x_2 \geq x_3 \geq ...x_n \geq0\)
等价于
\(t_1+2t_2+3t_3+...+nt_n=n的非负整数解的个数\)
每取一次球就会从其中一种状态转化为另一种状态（当然也可能是同一种状态），最后就是解多元一次方程
\(n=2时，期望E=1\)
\(n=3时，设始状态为3种颜色的期望为E_1，初始状态有2种颜色的期望为E_2，则\)
\(E_1=1+E_2 \\ E_2=1+\frac{1}{3}E_2+\frac{2}{3}\frac{1}{2}E_2\)
\(解得E_1=4,E_2=3\)
\(n=4时，设始设状态为4种颜色的期望为E_1，\\初始状态有3种颜色的期望为E_2，\\初始状态有2种颜色且其中1种颜色有3个球的期望为E_3，\\初始状态有2种颜色且每种颜色有2个球的期望为E_4，则\)
\(E_1=1+E_2\\E_2=1+\frac{1}{6}E_2+\frac{4}{6}(\frac{1}{2}E_2+\frac{1}{2}E_3)+\frac{1}{6}E_4\\E_3=1+\frac{3}{6}E_3+\frac{3}{6}\frac{1}{2}E_4\\E_4=1+\frac{2}{6}E_4+\frac{4}{6}E_3\\解得E_1=9,E_2=8,E_3=\frac{11}{2},E_4=7\\当n=5时，类似的可解得初始为5种颜色的期望E=\frac{1391}{111}\)

倪举鹏

第二题应该不能，不会证明
第三题不是定值，球面面积是最大的

yigo

第6题
兔子第1次跳（0秒）有1/2的概率超过乌龟，如果第1次往回跳，后面只可能在第4,8,12，...，4n秒的时候超过乌龟，
设兔子直到第4n秒才超过乌龟的概率为P(n)，则P(0)=1/2,n≥1时，
\(P(n)=\frac{A(n)}{2^{4n}}，A(1)=1，A(2)=3，A(3)=15，A(4)=91,A(n)=\frac{3C(4n-1,n-1)}{4n-1}\)
\(P=\sum_0^\infty P(n)=\frac{1}{2}+\frac{1}{2^4}+\frac{3}{2^8}+\frac{15}{2^{12}}+...=\frac{5}{4}-\frac{3}{4} {_3F_2}(-\frac{1}{4},\frac{1}{4},\frac{1}{2};\frac{1}{3},\frac{2}{3};\frac{16}{27})\approx 0.5803\)
(wolframalpha算的）
A(n)序列编号A006632
由于打印成黑白的了，红线就是乌龟指的那条线（乌龟的时间位移线），网格为兔子的可能位置,图中A(n)公式写错了，A(n)=B(4n-1,3n-1)。

图

B(n,k)的一些项，k(列号）表格中从1开始，应该从0开始。