俄罗斯奥数题

俄罗斯奥数题由于本人是AI语言模型，故无法将经典的俄罗斯奥数题目全都列举出来，但我可以举几个比较经典的例子并给出解题思路。

1.小球问题

在一个圆形的球盘中有$2n$个编号为$1,2,...,2n$的小球，其中编号为$i$和$i+n$的两个小球的重量不同。已知只有一体秤，使用次数不限，如何能够用最小的次数找出哪两个小球重量不同？

解题思路：考虑使用二分法，将$2n$个小球分成两半，分别称重。假设左半部分重量为$W_l$，右半部分重量为$W_r$，如果$W_l=W_r$，则证明两个不同重量的小球分别在左右两半中，问题规模缩小到$n$个小球中，可以不断递归使用该方法。如果$W_l\neqW_r$，则可以证明两个不同重量的小球在重量较轻的一边。此时问题规模也缩小到$n$个小球中，重复上述过程即可。设总共选择了$k$次，问题规模为$n_k$个小球，则总体使用的次数为$\sum_{i=1}^k\log_2n_i+k$。如果使用贪心策略，每次都按一半的比例进行称重，则可以证明总次数不会超过$3n-2$。

2.无限次扔骰子问题

现有一枚骰子，每次扔出的结果是$1,2,3,4,5,6$中的一个，可以无限次地扔骰子。如果当前得到的点数比之前的最大点数还要小，则游戏结束。如果游戏可以无限进行下去（即没有结束），求所有可能得到的点数的期望值。

解题思路：设当前最大点数为$k$，则下一次投掷得到的小于等于$k$的概率为$\frac{k}{6}$，得到比$k$大的概率为$\frac{6-k}{6}$。如果得到比$k$大的点数$m$次后结束游戏，则当前得到的点数为$k+m$。因此，当前最大点数为$k$时游戏不结束的概率为$\frac{k^2}{6^{k+1}}$。根据全概率公式，得到当前得到的点数为$k$时，所有可能的下一步点数的期望值为$\sum_{j=k+1}^6\frac{j}{6}\cdot\frac{6-j}{6}\cdot\frac{k^2}{6^{k+1}}+\frac{k^2}{6^{k+1}}$。因此，当前最大点数为$k$时所有可能得到点数的期望值为$\frac{k^2}{6^k}+\sum_{i=k+1}^\infty\frac{i^2}{6^{i+1}}$。将其求和，得到所有可能得到点数的期望值为$\sum_{k=1}^\infty(\frac{k^2}{6^k}+\sum_{i=k+1}^\infty\frac{i^2}{6^{i+1}})$。

3.极小图问题

给定一个$n$个点$m$条边的无向图，边权为$1$或$2$，每个点至少有一个邻居。证明该图的极小值为$2$或$3$。

解题思路：设当前图的极小值为$k$，则存在一组边$(u,v)$，且只有$(u,v)$的边权为$1$，其余边的边权均为$2$。根据定义，$k$等于最短路中最长的边权。假设存在另一对节点$(u',v')$，其边权为$1$，则一定有$(u',v)$或$(u,v')$的边权也为$1$。由此推广，可以得到最多存在一个边权为$1$的连通分量。因此，对于每个点$v$，如果其度数$\geq3$，则存在一对相邻的边$(u,v),(v,w)$，且$(u,v)$的边权为$1$，$(v,w)$的边权为$2$。将$(u,v)$的边权改为$2$，$(v,w)$的边权改为$1$，可以将极小值减小为$k-1$或$k-2$。最终，极小值