赠券半收集

Aster GameのDay, 理宅异闻录 Leave a Comment

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$$

Read More

最速输入问题(上)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

屏幕上有一个字符, 如果只用全选复制粘贴, 要达到$n$个字符最少要多少次按键?

要想达到$N$个字符

  • 如果$N$是个素数,玩完了

只能一个一个复制了, ACVVVVVVVVVV...

也就是 N+2 次.

  • 如果N可以分解

那么我们找出他的一个因子 $\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]}$$

我们比较三种路径那个更小就行了.

当然所有路线一起比是一样的...

Read More

随机级数

Aster 理宅异闻录 Leave a Comment

考虑 $\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)$来近似.

我们可以用级数展开来确定系数.

Read More

区块链原理

Aster 理宅异闻录 Leave a Comment

比特币挖矿,说来也容易,其实就是找到如下方程的一个解而已:

$$\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越小,找到一个解的难度自然就越高.

而唯一的求解方法就是穷举.

Read More

经典赠券收集

Aster GameのDay, 理宅异闻录 Leave a Comment

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}$$

Read More

几何の暴力美学:心似三角形

Aster 理宅异闻录 Leave a Comment

是否存在一个三角形,其重心、垂心和内心所连成的三角形与原三角形相似?

难度有点大啊...这就要用到数学实验了,先做模拟一下看看解的情况再说.

发现一个重要的现象,内心所成的角∠ZNC 必然是钝角,那么原来的三角形就不可能是锐角或者钝角,这就可以当定解条件了.

一方面角又是单调了,在B点右端移动就可以取到唯一解.

Read More

几何の暴力美学:角圆

Aster 理宅异闻录 Leave a Comment

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:如果这样子一个一个又一个的圆无限延伸下去,求所有圆的总面积和三角形面积的比值.

Read More

【π史话】BBP类公式

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

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} \]

Read More