一道有趣的思考题:老鼠喝药水
题目很简单:你的面前有 100 瓶打乱了的药水,其中有且只有一瓶为毒药. 你有 7 只老鼠,喝了毒药的老鼠会死去,反之不会. 现请你利用这 7 只老鼠设计一种方案,根据老鼠的死活情况找出毒药.
假定每只老鼠可以喝下无限量的药水,且每瓶药水不会被喝完. 在方案实施的过程中,你无法得知当前的执行情况,也就是说,你不能根据前一只老鼠的死活决定后续的操作.
满船清梦压星河。
题目很简单:你的面前有 100 瓶打乱了的药水,其中有且只有一瓶为毒药. 你有 7 只老鼠,喝了毒药的老鼠会死去,反之不会. 现请你利用这 7 只老鼠设计一种方案,根据老鼠的死活情况找出毒药.
假定每只老鼠可以喝下无限量的药水,且每瓶药水不会被喝完. 在方案实施的过程中,你无法得知当前的执行情况,也就是说,你不能根据前一只老鼠的死活决定后续的操作.
组合数 $C_m^n={n \choose m}$ 为什么一定是整数?
我把这个问题当作一把量人的尺子:如果你斩钉截铁地回答“显然”,那我们大抵是没什么缘分的了;但如果你由此陷入了思考,那说明你属于我想结识的那类人.
狄利克雷卷积(Dirichlet Convolution)在解析数论中是一个非常重要的工具.
使用狄利克雷卷积可以很方便地推出莫比乌斯反演(Möbius Inversion)相关重要函数和公式,它在信息学竞赛和解析数论中至关重要.
很多初学者不能真正地理解莫比乌斯反演,或者说即使能使用最终的公式,也难以理清楚它是怎么推导的.
本文中,我将尝试使用一种新的方式讲解狄利克雷卷积和莫比乌斯反演,希望能对大家有所帮助.
离散傅里叶变换(Discrete Fourier Transform, DFT)和离散傅里叶反变换(Inverse Discrete Fourier Transform, IDFT) 是鼎鼎大名的快速傅里叶变换(Fast Fourier Transform, FFT)的前置知识.
其中 FFT 用于加速两个多项式 $A(x)$、$B(x)$ 的乘积 $C(x)$ 的计算,DFT 和 IDFT 是 FFT 的两个中间步骤.
费马点(Fermat’s point)又称托里切利点(Torricelli’s Point),
费马点 $O$ 是位于凸多边形内的一个点,
它满足到各顶点距离之和最小,
这样的点是存在且唯一的.
定理如下:
对于任意 $n$ 边形,其顶点为 $A_1..A_n$,
取 $O$ 点满足 $\angle A_1OA_2=\angle A_2OA_3=\cdots=\dfrac{2\pi}{n}$
那么对于任意点 $P$,有:
实际上这里的 $O$ 点就是费马点.
下面对该定理进行证明.
可以证明:
也就是说一共有 $n+1$ 个根号。注意最外层根号里是减号,最内层为 $\sqrt{3}$.
证明以下内容后经群友提醒才确定这属于群论,那本文就当作是循环群的通俗解释吧.
对任意封闭体系内的元素进行互换位置的操作,
一定能在有限次操作后恢复到操作前的状态,
且这有限次操作的次数是可以计算的.
下面尝试给出其证明,若有误欢迎指出.
斐波那契数列(Fibonacci sequence),指数列:
1, 1, 2, 3, 5, 8, 13, 25, 38…
即后一项为前两项之和
我们不妨用 $\{a_n\}$ 表示斐波那契数列,那么有:
我们采用特征方程来推导通项公式.
泰勒级数即无穷项泰勒多项式.
这是正弦函数的泰勒级数展开形式,下面使用多阶导对其推导方式作证明.