Below you'll find a list of all posts that have been categorized as “理宅异闻录”
Question:
假设有n种赠券，每种赠券获取机率相同，而且赠券亦无限供应。若取赠券k张，能集齐其中m种赠券的机率多少
恰好在第 $k$ 次试验得到指定 $m$ 张不同赠券的试验次数是 $ m! \mathcal{S}_2(k - 1, m - 1)$.
从 $n$ 张不同的赠券中收集 $m$ 张共有 $\mathcal{C}(n,m)$ 种方法.
最后总方法数仍是 $n^k$.
综上所述, 恰好在第 $n$ 次试验完成收集全部 $k$ 张不同的赠券的概率是:
$$P(n)=m! \mathcal{S}_2(k - 1, m - 1)\mathcal{C}(n,m)/n^k$$
屏幕上有一个字符, 如果只用全选复制粘贴, 要达到$n$个字符最少要多少次按键?
要想达到$N$个字符
只能一个一个复制了, ACVVVVVVVVVV...
也就是 N+2 次.
那么我们找出他的一个因子 $\mathrm{i}$ ,另一个因子记为$ \mathrm{ j=N/i}$
也就是达到 $\mathrm{dp[i]}$ 之后粘贴 $j+1$ 次
要不就达到 $\mathrm{dp[j]}$ 之后粘贴$ i+1$ 次
$$\mathtt{dp[i] =Min[dp[j] + i/j + 2, dp[i/j] + j + 2]}$$
我们比较三种路径那个更小就行了.
当然所有路线一起比是一样的...
考虑 $\mathbb{R}$ 上的随机游走,每一步有$\frac{1}{2}$的概率选择往左走,有$\frac{1}{2}$的概率往右走.但是第$n$步走的距离为$\frac{1}{n}$.
请问终点的概率分布是否存在?如果存在那是什么样子的?
这个问题等价于求随机调和级数的收敛分布.
如果$\sum a_n x^n$ 中的$ a_n $是个随机变量,那么就把他称为随机级数,随机级数有个很最简单的审敛方法.
无偏随机游走嘛,也就是 $ \mathbb{E}( \xi_n ) = 0 $ 的意思, 另一方面$ \mathbb{E}( {\xi_n}^2 ) =\mathbb{E}( {|\xi_n|}^2 ) =\sum_{n=1}^\infty {\frac{1}{n^2}}=\frac{\pi^2}{6} $.
所以这个随机级数以概率$1$收敛,接下来我们来求最终收敛到的概率密度函数.
$a_n$是个数列,$ \sum a_n$自然收敛到一个数.
$a_n$服从一个概率分布,那$ \sum a_n$自然也就收敛到一个概率分布咯.
因为问题的复杂性,一般来讲是没法求出解析式的,只有各种近似计算.
考虑这个过程的生成函数$\prod\limits_{n > 0} {\left( {\frac{1}{2}{z^{\frac{1}{n}}} + \frac{1}{2}{z^{ - \frac{1}{n}}}} \right)}$,这根本就无从下口.
所以我们转而考虑其特征函数 $\cos(t/n) $,也就是求 $\prod_{n=1}^\infty \cos(t/n)$ 的逆傅里叶变换.
我们希望找个能进行傅里叶变换的函数来近似计算.
首先这是个偶函数,其次无穷个余弦函数相乘在远离原点的地方会衰减,$\text{Sinc}$函数是个不错的示范
但是衰减的速度不是很契合,所以还要加个指数函数来调整,当然得是偶函数,加个平方.
也就是用$e^{-\frac{t^2}{a}} \text{sinc}(b t)$来近似.
我们可以用级数展开来确定系数.
比特币挖矿,说来也容易,其实就是找到如下方程的一个解而已:
$$\text{hash}(x)<\text{target}$$
其中hash就是常说的哈希函数,target则决定了难度.
哈希函数定义域为整数,值域则是某个范围的正整数.
可以看出其实解有无数个,但是发现其中一个并不容易.
你可能要说了,我能不能分析这个函数来求它的反函数?
有些哈希函数可以,比如CRC校验函数,但是一类用作加密的哈希函数不可以.
哈希加密函数,基本特点之一就是随机,以比特币使用的SHA256为例,画出前100个数字的哈希值:
可以看出这个函数图像几乎就是$0\sim 2^{256} \approx 1.15792\times 10^{77} $ 中的一个随机数.
也就是说随便说一个数,说中答案的概率只有 $8.63616^{-78}$,宇宙原子总数才$10^80$左右...
Target用来调节难度.Target越小,找到一个解的难度自然就越高.
而唯一的求解方法就是穷举.
Question:
假设有n种赠券，每种赠券获取机率相同，而且赠券亦无限供应。若取赠券k张，能集齐n种赠券的机率多少？
在第 $k$ 次试验后恰好第一次完成全部收集,则在前 $k - 1$次试验收集了 $n - 1$ 张不同的赠券.前 $k - 1$ 次试验相当于将 $k - 1$ 个元素的集合划分成有序的 $n - 1$ 个非空子集的个数.即 $(n - 1)! \mathcal{S}_2(k - 1, n - 1)$ 个,其中$\mathcal{S}_2 (k, n )$ 是第二类Stirling 数.
从 $n$ 张不同的赠券中收集到 $n - 1$ 张有 $\mathcal{C}(n,n-1)$ 种组合, 其中$\mathcal{C}(n,k)$ 为二项式系数.
最后除以总方法数,也就是将 $k$ 个元素的集合划分成 $n$ 个子集的方式,共 $n^k$ 种.
综上所述,恰好在第 $k$ 次试验完成收集全部 $n$ 张不同的赠券的试验的概率是:
$$\begin{aligned}
P(n)=&(n - 1)! \mathcal{S}_2(k - 1, n - 1)\mathcal{C}(n,n-1)/ n^k\\
=&\frac{n!}{n^k} \mathcal{S}_2(k - 1, n - 1)\\
\end{aligned}$$
是否存在一个三角形,其重心、垂心和内心所连成的三角形与原三角形相似?
难度有点大啊...这就要用到数学实验了,先做模拟一下看看解的情况再说.
发现一个重要的现象,内心所成的角∠ZNC 必然是钝角,那么原来的三角形就不可能是锐角或者钝角,这就可以当定解条件了.
一方面角又是单调了,在B点右端移动就可以取到唯一解.
我们知道三个圆相切可以围成一个不规则图形, 不妨称其为圆隙...
Wait...好像不严谨, 套一起的话三圆可以切于同一点...
好吧三圆相切于不同点...oh no...还是不能唯一确定图形...
我们今天的探究目标是求圆隙,也就是中间那个不规则部分的面积.
Exercise1: 如图两个圆称为角圆,求大圆与小圆的周长比与角度的关系
第一问很简单,解方程就是了:
\[\begin{aligned}
\sin \frac{\theta }{2} &= \frac{{AH}}{{AO}} = \frac{{BI}}{{BO}} \\
\sin \frac{\theta }{2} &= \frac{r}{{AO}} = \frac{R}{{r + R + AO}} \\
AO &= r\csc \frac{\theta }{2} = \frac{{r(R + r)}}{{R - r}} \\
\frac{R}{r} &= \frac{{\csc (\theta /2) + 1}}{{\csc (\theta /2) - 1}} = {\tan ^2}\left( {\frac{{\theta + \pi }}{4}} \right) \\
\end{aligned}\]
Exercise2:如果这样子一个一个又一个的圆无限延伸下去,求所有圆的总面积和三角形面积的比值.
BBP公式全称为 贝利-波尔温-普劳夫公式 (Bailey–Borwein–Plouffe formula),该公式发现于1995年,以三位发表者的名字命名.
最初的一个BBP公式是:
\[\pi = \sum\limits_{k = 0}^\infty {\frac{1}{{{{16}^k}}}\left( {\frac{4}{{8k + 1}} - \frac{2}{{8k + 4}} - \frac{1}{{8k + 5}} - \frac{1}{{8k + 6}}} \right)} \]
证明不算太难,可以作为一道高数习题.一个思路是交换积分求和次序来将式子转化为有理分式积分.
\[\begin{aligned}
\int_0^{1/\sqrt 2 } {\frac{{{x^{p - 1}}}}{{1 - {x^8}}}{\text{d}}x} &= \int_0^{1/\sqrt 2 } {\sum\limits_{k = 0}^\infty {{x^{p - 1 + 8k}}} {\text{d}}x} \\
&= \sum\limits_{k = 0}^\infty {\int_0^{1/\sqrt 2 } {{x^{p - 1 + 8k}}{\text{d}}x} } \\
&= \sum\limits_{k = 0}^\infty {\frac{{{2^{ - 4k - \frac{p}{2}}}}}{{8k + p}}} \\
&= \frac{1}{{{2^{p/2}}}}\sum\limits_{k = 0}^\infty {\frac{1}{{{{16}^k}}}\frac{1}{{8k + p}}} \\
\end{aligned} \]
