上次被 utomaya 提醒了一遭，在五十人之前肯定是不能发题解了……

那我就来翻译吧～

Problem

PE 438 不会 >__<

Problem

令 \(d(n) = \sum_{d|n} d\) ，求 \[S(n) = \sum_{i = 1}^n \sum_{j = 1}^n d(ij)\] 其中 \(n = 10^{11}\)

好久没做题了似乎，最近被抽代虐的有点发慌。

Problem

令 \(a_n\) 为 \(x^3 - 2^n x^2 + n = 0\) 最大的一个实数根，求 \[\sum_{i=1}^{30} \lfloor {a_i^{987654321}} \rfloor\]

开学了～

Problem

求 \([1, 10^8]\) 内满足存在一个原根 \(g\) 且 \(1 + g \equiv g^2 \mod{p}\) 的素数 \(p\) 的和。

\(\newcommand{\D}[0]{\mathrm{d}}\) 卡着第 50 名过……

谁来教教我如何用微积分算期望啊，我算着简直要疯了。。

Solution

其实只要算出这两个随机变量的 pdf 就好了。但是我觉得算起来特别恶心……主要是对这货不熟吧，时不时就卡住了。

首先算第一个的 pdf 。我们枚举累加器是在第 \(n\) 次累加时超过 1 ，我们计算出 \(n\) 个变量的和为 \(t\) 的 pdf \(f(x) = \frac{t^{n - 1}}{(n - 1)!}\) ，则第一个值的密度分布函数为 \[ \begin{aligned} P(x) & = \sum_{n = 1}^\infty \int_{1 - x}^{1} f(t) \D{t} \\ & = \sum_{n = 1}^\infty \int_{1 - x}^{1} \frac{t^{n - 1}}{(n - 1)!} \D{t} \\ & = \sum_{n = 1}^\infty \frac{1 - (1 - x)^n}{n!} \\ & = \sum_{n = 1}^\infty \frac{1}{n!} - \sum_{n = 1}^\infty \frac{(1 - x)^n}{n!} \\ & = (e - 1) - (e^{1 - x} - 1) \\ & = e - e^{1 - x} \\ \end{aligned} \]

第二个值的 pdf 就比较恶心了。还是同样的思想，我们令 \(g_n(x)\) 表示 \(n\) 个 0 到 1 的变量的和为 \(1 + x\) 的 pdf ，可以得到 \(g_1(x) = 0\) 。可以求出 \(g_n (x)\) 递推式：

\[ \begin{aligned} g_{n+1}(x) & = \int_{0}^x g_n(t) \D{t} + \int_{x}^1 f(t) \D{t} \\ & = \int_{0}^x g_n(t) \D{t} + \frac{1 - x^n}{n!} \\ \end{aligned} \]

求出 \(g_n(x)\) 通项似乎是比较困难的，但是注意，第二个值的 pdf 我们只关心 \(\sum_{n=1}^\infty g_n(x)\) 。

对于递推式 \(v_{n+1}(x) = \int_0^x v_n(t) \D{t}, v_{0}(x) = 1\) ，我们可以得到 \(v_n(x) = \frac{x^n}{n!}\) ，则 \(\sum_{n=0}^\infty v_n(x) = e^x\) 。

我们考虑 \(g_{n+1}(x) = \int_0^x g_n(t) \D{t} + \frac{1 - x^n}{n!}\) 里面的 \(\frac{1}{n!}\) 。这个数会被连续积分无数次，最后对 \(\sum_{n = 1}^\infty g_n (x)\) 的贡献是 \(\frac{e^x}{n!}\) 。 \(\frac{x^n}{n!}\) 也会被积分无数次，注意到对于 \(k\) 来说，所有 \(x \leq k\) 的 \(\frac{x^n}{n!}\) 积分时都会得到过一个 \(\frac{x^k}{k!}\) ，所以这部分对于和的贡献是 \(\sum_{k = 1}^\infty k \frac{x^k}{k!} = x e^x\) 。所以我们有： \[\sum_{n = 1}^\infty g_n(x) = \sum_{n = 1}^\infty \frac{e^x}{n!} - x e^x = e^x (e - 1 - x)\]

现在要开始求第二个值的 pdf 了。令 pdf 为 \(Q(x)\) ，则有 ： \[Q(x) = \int_{1-x}^1 e^x(e-1-x)\D{x}\]

知道了 \(P(x)\) 和 \(Q(x)\) ，答案就是：

\[ans = \int_{0}^1 Q(x) \int_0^x P(y) \D{y} \D{x}\]

\(Q(x)\) 和 \(ans\) 的具体表达式我用的 sage 暴力算的，就没写出来了。

nonsense

看着 forum 里面各种高大上的积分感觉被虐傻了。

@dyh 求你的做法。

又在军训的时候想出一道题……

Problem

有 \(2n\) 个人，编号 1 到 \(2n\) ，每个人头上有一顶帽子，帽子要么是黑色的要么是白色的。现在这 \(2n\) 个人需要同时说出自己帽子的颜色，如果不少于 \(n\) 个人说对了自己帽子的颜色，则这局游戏获胜，否则失败。求是否存在必胜策略。

居然能在站军姿的时候 YY 出一道题……

Problem

有 \(n\) 个人，对于任意一个非空子集 \(S\) ，都存在一个人使得他在 \(S\) 中有偶数个朋友。求证 \(n\) 是偶数。

智商亟需拯救。 \(\newcommand{\D}[0]{\mathrm{d}}\)

Problem

@fotile 问的一个题，我将题目改了下描述：

\(n\) 个变量 \(x_1, x_2, \dots, x_n\) ，满足 \(0 \leq x_i\) 且 \(\sum x_i = 1\) 。求 \(x_i\) 中第 \(k\) 小值的期望。

听天由命的节奏？

Problem

Mathematics (60 pts + 10 bonus pts)

1 (5 pts)

一个人、一只狼、一头羊、一卷白菜要过河。如果人不在，狼会吃羊，羊会吃白菜。求过河方案。

2 (10 pts)

两个 \(8 \times 8\) 的棋盘，第一个棋盘 \((i, j)\) 为黑当且仅当 \(\frac{i}{2} \equiv \frac{j}{2} \mod{2}\) ，第二个棋盘 \((i, j)\) 为黑当且仅当 \(i \equiv j \mod{2}\) 。现在要求将第一个棋盘剪成若干块，然后重新组成第二个棋盘，问至少要剪成多少块，并证明最优性。

3 (10 pts)

求 \([1, 10^6]\) 内所有数字的数位和。

4 (10 pts)

\(n\) 个人，每个人有一个秘密，现在任意两个可以通过电话交流，每次交流后两人都知道了对方知道的所有的秘密。问至少要经过多少次交流才能使得每个人都知道所有秘密。

5 (15 pts)

A B 两点相距 1 个单位，现在你可以从 A 走 \(n\) 步到 B 去，每步必须走直线，且你到 B 的距离一定要减小。求你走的最长距离。

6 (10 pts + 10 bonus pts)

A B 两人玩游戏，A 被蒙上了眼睛。一个圆桌子上有 \(n\) 个硬币，每个硬币要么正面朝上要么反面朝上。两人轮流进行操作，每次操作如下：

1. A 选择若干个位置
2. B 旋转桌子
3. 翻转 A 选择位置上的若干个硬币

如果所有的硬币都是朝上的那就是 A 赢。否则 B 赢。

问题有三个：

1. (5 pts) 给出一个 \(n = 4\) 的必胜策略。所谓必胜策略是指无论初始状况怎么样，A 总是可以赢的策略。
2. (5 pts) 证明 \(n\) 是奇数时 A 不存在必胜策略。
3. (bonus 10 pts) 证明存在必胜策略，当且仅当 \(n\) 是 2 的整数次幂。

Physics (40 pts)

1 (5 pts)

画两个图的电场线。第一个图为一个金属空心球体内有一个正的点电荷，第二个图为外有一个正的点电荷。

2 (5 pts)

一个均匀绳子，长度为 \(L\) ，质量为 \(m\) ，下端刚好接触一个天平。现在开始自由下落。当天平上绳子的长度恰好为 \(x\) 时，求天平的超级罗瞬间读数。

3 (10 pts)

一个无穷网格，每条线段的电阻为 1 欧，求相邻两点之间的等效电阻的大小。

4 (10 pts)

将一个硬币抛起来，如果立起来的可能性为 \(\frac{1}{3}\) ，求硬币半径与厚度的关系。

5 (10 pts)

1. (5 pts) 一个质量为 \(M\) 的球上放一个质量为 \(m\) 的小球。将两个球从 1m 出自由落体，已知 \(M\) 远远大于 \(m\) ，求小球能弹多高。
2. (5 pts) 由第一问画出航天器借助行星来进行加速的原理。

所有碰撞均为完全弹性碰撞。

在看到之前你会以为这是啥 = =？

wiki 在 这里

其实就是一个公式罢了。刚刚才发现的，实在是太漂亮了： \[\int_0^1 \frac{1}{x^x} \mathrm{d} x = \sum_{n=1} \frac{1}{n^n}\]

从一个积分到一个求和，连续到离散，真是不错。

证明的话， wiki 上有吧，摘抄如下。

首先变形： \(x^{-x} = e^{-x \log x}\) 。展开有： \[x^{-x} =\sum_{n=0} \frac{(-x \log x)^n}{n!}\]

代入并提前 \(\sum\) ： \[\int_0^1 \frac{1}{x^x} \mathrm{d} x = \int_0^1 \sum_{n=0} \frac{(-x \log x)^n}{n!} \mathrm{d} x = \sum_{n=0} \frac{1}{n!} \int_0^1 (-x \log x)^n \mathrm{d}x\]

换元，令 \(x = e^{-\frac{t}{n+1}}, \mathrm{d} x = -\frac{e^{-\frac{t}{n+1}}}{n+1}\mathrm{d}t\) ， \(0 < t < \infty\) ： \[ \begin{array}{rcl} \int_0^1 (-x \log x)^n \mathrm{d}x & = & \int_0^\infty(e^{-\frac{t}{n+1}} \frac{t}{n+1})^n \frac{-e^{-\frac{t}{n+1}}}{n+1}\mathrm{d}t \\ & = & \frac{1}{(n+1)^{n+1}} \int_\infty^0 -e^{-t} t^n \mathrm{d} t \\ & = & \frac{n!}{(n+1)^{n+1}} \\ \end{array} \]

再次代入： \[ \begin{array}{rcl} \int_0^1 \frac{1}{x^x} \mathrm{d} x & = & \sum_{n=0} \frac{1}{n!} \int_0^1 (-x \log x)^n \mathrm{d}x \\ & = & \sum_{n=0} \frac{1}{n!} \frac{n!}{(n+1)^{n+1}} \\ & = & \sum_{n=1} \frac{1}{n^n} \\ \end{array} \]