生成函数与计数
问题: 对于集合 $\{1,2,\dots, 2000\}$,有多少个子集满足子集中所有数字的和可以被 $5$ 整除? 递推法 首先对集合进行分组 $A_n = \{5n-4, \dots, 5n\}$。对于任意 $A_n$,其子集中所有数字的和对 $5$ 取余的结果与 $A_1$ 相同。可以得到结果为 $0,1,2,3,4$ 的个数分别为 $8,6,6,6,6$。注意空集也满足条件(认为空集的所有数字和为 $0$)。 ...
问题: 对于集合 $\{1,2,\dots, 2000\}$,有多少个子集满足子集中所有数字的和可以被 $5$ 整除? 递推法 首先对集合进行分组 $A_n = \{5n-4, \dots, 5n\}$。对于任意 $A_n$,其子集中所有数字的和对 $5$ 取余的结果与 $A_1$ 相同。可以得到结果为 $0,1,2,3,4$ 的个数分别为 $8,6,6,6,6$。注意空集也满足条件(认为空集的所有数字和为 $0$)。 ...
IMO 2011 年的第 2 题: 设 $S$ 是平面上包含至少两个点的有限点集,并且其中任意三点不共线。定义一个「风车」过程:直线 $l$ 从 $S$ 中一点 $P$ 开始,绕 $P$ 顺时针旋转,直到 $l$ 碰到 $S$ 中另一点 $Q$。此时 $Q$ 变为 $l$ 的新旋转中心,$l$ 继续顺时针旋转,直到直线再次碰到 $S$ 中的某一点。此过程将一直持续下去。证明可在 $S$ 中选一点和过该点的一条直线,使得对应的「风车」过程中,$S$ 中的所有点都将无限次地作为旋转中心。 ...
使用 dual graph 证明欧拉公式:$V-E+F=2$ 对于一个 connected planar graph $G$,如下图蓝色部分所示,其所对应的 dual graph $G^*$ 则为红色部分: $G^*$ 的每个顶点对应 $G$ 中的每个面 $G^*$ 中的每条边连接两个顶点,这两个顶点对应于 $G$ 中相邻的两个面(即共享一条边的两个面) 对偶图有一些性质: ...
问题: 想象光滑的地面有两个静止的小滑块,左面有一堵质量无穷大的墙。左边的小滑块质量为 $1$。此时给右边的小滑块一个向左的速度,假设所有的碰撞都为完全弹性碰撞,请问总共的碰撞次数?(滑块之间的碰撞+左滑块和墙的碰撞) ...
问题: 证明 $1+\dfrac{1}{4}+\dfrac{1}{9}+\dfrac{1}{16}+\cdots=\dfrac{\pi^2}{6}$ 这一问题实际上有多种代数方法证明,但由于公式中出现了 $\pi$,则必定在几何学中可以找到圆来对应。 想象一位观察者站在数轴的原点,并在所有的正整数的位置放置一座灯塔。假设观察者接收到的第一座灯塔的亮度为 $1$。由于亮度和距离的平方成反比,则第 $n$ 座灯塔的亮度为 $\dfrac{1}{n^2}$。这样我们就将原问题转化为了物理的表达形式,我们只需要证明原点所接收到的总亮度为 $\dfrac{\pi^2}{6}$ 即可。 ...
问题: 在圆上任取 $n$ 个点,将每对点用直线连接,并规定三条线不能交于一点,这些直线会将圆分割成多少份? 首先我们列出一些简单情况来寻找规律: $2$ 个点将圆分为 $2$ 份 $3$ 个点将圆分为 $4$ 份 $4$ 个点将圆分为 $8$ 份 $5$ 个点将圆分为 $16$ 份 Simple Cases ...
想象你的麦克风在录制一段由四个纯音同时播放的音频,由于其只能捕捉气压——时间图像,因此最后的结果看起来相当复杂: Pressure-Time 如果给定这样一段音频,该如何将其分解为不同纯音的叠加? ...
问题: 在球面上随机选择四点组成四面体,问球心落在该四面体内部的概率? 首先将问题简化,考虑二维情形:在圆上随机选择三点 $P_1, P_2, P_3$ 组成三角形,求圆心落在该三角形内部的概率。 ...
问题: 一条项链上有 $n$ 种类型的珠宝,每种珠宝的数量均为偶数。问至少需要切几刀,可以将所有珠宝均分? 首先介绍 Borsuk-Ulam Theorem: 想象一个三维空间中的球面被扭曲压缩到二维平面上,由于变形是连续的,因此球面上有许多点重合在了一起。Borsuk-Ulam 定理告诉我们总能找到这样的两个点,它们一开始在球面上处于完全相反的两极,经过映射后会重合在一起。 ...
问题: 证明 $\dfrac{\pi}{4} = 1-\dfrac{1}{3}+\dfrac{1}{5}-\dfrac{1}{7}+\dfrac{1}{9}-\cdots$ $$ \begin{split} 1-\dfrac{1}{3}+\dfrac{1}{5}-\dfrac{1}{7}+\cdots &= \int_0^1 (1-x^2+x^4-\cdots)dx \\ &= \int_0^1 \frac{1}{1+x^2}dx \\ &= \tan^{-1}(1) \\ &= \frac{\pi}{4} \end{split} $$ 我们选择从另外一种方式来得出这个等式,从圆的定义开始。 计算圆内格点数目 如果将二维平面划分为网格,并画出半径为 $r$ 的圆,圆内包含的格点数应该大约等于 $\pi r^2$,并且当 $r\to+\infty$ 时,两者应该无限接近,这即给出了一个计算 $\pi$ 的方法。 ...