Math

正交线性基。

参考 link。

orz Sooke。

一直都想学的引荐东西了。

瞎给个 link。

对于一个 $n\times n$ 的矩阵，$[1,n\times n]$ 在其中各出现一次。

定义一条好路径为一个坐标序列 $(x_1,y_1),(x_2,y_2),...,(x_k,y_k)$ 满足 $(x_1,y_1)$ 是「山谷」并且 $(x_i,y_i)$ 与 $(x_{i+1},y_{i+1})$ 相邻，且坐标上的数字单调增。

「山谷」表示这个点的数字比与他相邻的点都小，相邻是四联通。

对于所有满足条件的矩阵，求好路径最小值，并构造方案。

来源：IMO 2023 T6

收录一点看到的题。

求等幂和

$$S_k(n)=\sum_{i=0}^{n-1} i^k,(n\le 10^9,k\le 2000)$$

收录一点看到过的趣题。

先由一个经典的问题引入

有 $n$ 个奖陆续出台，每一个奖可以选择选或者不选，每个奖只能在出台的时候选，并且只能选一个奖，每出台一个可以和前面的比较价值大小，问想得到价值最大的奖的最优策略。

这是经典的秘书问题。

鞅

鞅最开始用来研究赌博策略问题，后来引入到数学中。

先考虑这样一个公平赌博局面，每一轮，你都可以下注 $x$ 元，然后有 $\frac{1}{2}$ 的概率你可以获得 $2x$ 元，$\frac{1}{2}$ 的概率输光。

此时我们提出一个赌博策略，这个策略每次下注多少由前面的输赢情况进行决定。

我们设一组独立随机变量 $\{Y_1,Y_2,...\}$ 表示前面局面的输赢情况，$Y_i=1$ 表示第 $i$ 局赢，$Y_i=-1$ 表示第 $i$ 局输。

令第 $i$ 轮下注 $b_i$ 元，容易发现 $b_i$ 由 $Y_1,Y_2,...,Y_{n-1}$ 的取值决定。

令 $X_i$ 表示第 $i$ 轮结束后的的钱数，那么有：

$$X_n=X_0+\sum_{i=1} b_iY_i$$

此时我们考虑前 $n$ 轮已经结束，计算 $X_{n+1}$ ：

$$E[X_{n+1}|\{Y_1,Y_2,...,Y_n\}]=E[X_n+b_{n+1}Y_{n+1}|\{Y_1,Y_2,...,Y_n\}]$$

此时由于 $X_n$ 和 $b_i$ 显然已经为定值。

$$=X_n+b_{n+1}E[Y_{n+1}|\{Y_1,Y_2,...,Y_n\}]=X_n$$

因为 $Y_i$ 间独立。

此时说明了 $X_{n+1}=X_n$，通俗解释就是在公平赌博情况下，不存在一种策略使得自己获利。

此时，设 $\{Y_n\},\{X_n\}$ 为两个随机变量序列，且 $X_n$ 可以由 $Y_1,Y_2,...,Y_n$ 唯一确定，并且满足：

$$E[X_{n+1}|\{Y_1,Y_2,...,Y_n\}]=X_n$$

则称 $X$ 为 $Y$​ 的鞅。