积分习题XVI:超重积分(2)

Aster 数学题集 Leave a Comment

我觉得我上次讲的不太友好,题目太难了.

我们应该从简单点的开始讲,比如:

$$\int_{{{\left[ {a,b} \right]}^n}} {{\text{d}}{x_1}{\text{d}}{x_2} \ldots {\text{d}}{x_n}}  = {\left( {b - a} \right)^n}$$

嗯,就是求超立方体体积...

然后我们来求超球体的体积,当然是用球坐标咯.

$$\begin{aligned}
dV&=r^{n-1}\sin ^{n-2}(\varphi _{1})\sin ^{n-3}(\varphi _{2})\cdots \sin(\varphi _{n-2})\,dr\,d\varphi _{1}\,d\varphi _{2}\cdots d\varphi _{n-1}\\
V_{n}(R)&=\int _{0}^{R}\int _{0}^{\pi }\cdots \int _{0}^{2\pi }r^{n-1}\sin ^{n-2}(\varphi _{1})\cdots \sin(\varphi _{n-2})\,d\varphi _{n-1}\cdots d\varphi _{1}\,dr\\
&=\left(\int _{0}^{R}r^{n-1}\,dr\right)\left(\int _{0}^{\pi }\sin ^{n-2}(\varphi _{1})\,d\varphi _{1}\right)\cdots \left(\int _{0}^{2\pi }d\varphi _{n-1}\right)\\
&={\frac {R^{n}}{n}}\left(2\int _{0}^{\frac {\pi }{2}}\sin ^{n-2}(\varphi _{1})\,d\varphi _{1}\right)\cdots \left(4\int _{0}^{\frac {\pi }{2}}d\varphi _{n-1}\right)\\
&={\frac {R^{n}}{n}}\textstyle \mathrm {B} \left({\frac {n-1}{2}},{\frac {1}{2}}\right)\mathrm {B} \left({\frac {n-2}{2}},{\frac {1}{2}}\right)\cdots \mathrm {B} \left(1,{\frac {1}{2}}\right)\cdot 2\mathrm {B} \left({\frac {1}{2}},{\frac {1}{2}}\right)\\
&={\frac {R^{n}}{n}}{\frac {\Gamma \left({\frac {n-1}{2}}\right)\Gamma \left({\frac {1}{2}}\right)}{\Gamma \left({\frac {n}{2}}\right)}}{\frac {\Gamma \left({\frac {n-2}{2}}\right)\Gamma \left({\frac {1}{2}}\right)}{\Gamma \left({\frac {n-1}{2}}\right)}}\cdots {\frac {\Gamma \left(1\right)\Gamma \left({\frac {1}{2}}\right)}{\Gamma \left({\frac {3}{2}}\right)}}\cdot 2{\frac {\Gamma \left({\frac {1}{2}}\right)\Gamma \left({\frac {1}{2}}\right)}{\Gamma \left(1\right)}}\\
&={\frac {2\pi ^{\frac {n}{2}}R^{n}}{n\Gamma \left({\frac {n}{2}}\right)}}={\frac {\pi ^{\frac {n}{2}}R^{n}}{\Gamma \left({\frac {n}{2}}+1\right)}}
\end{aligned}$$Read More

积分习题XV:超重积分

Aster 数学题集 Leave a Comment

超重积分就是那种看上去很重很重的积分......嗯?这个字读Chóng来着....那就是n重积分的意思了....

发明一个约定:

$$I(n) = \int_{{{[0,1]}^n}} {\mathop f\limits_{i \in 1\sim n} [{x_i}]{\text{d}}{x_i}}  = \int_0^1 {\int_0^1 . } ..\int_0^1 {f({x_1},{x_2},...,{x_n}){\text{d}}{x_1}{\text{d}}{x_2}...{\text{d}}{x_n}}$$

Well....你以为打一大堆积分号不累啊...

来试验一下,求证:$$\boxed{\bigstar I(n) = \int_{{{[0,1]}^n}} {\mathop {\min }\limits_{i \in 1\sim n} [{x_i}]{\text{d}}{x_i}}  = \frac{1}{{n + 1}}}$$

Read More

级数习题V

Aster 数学题集, 理宅异闻录 Leave a Comment

上次我展示了一个极为惊艳的积分:

\[\int_0^1 {{e^{i\pi x}}} \; {x^x}{(1 - x)^{1 - x}}\; dx = \frac{e}{2}\frac{\pi }{3}\frac{i}{4}\]

这个积分神奇的把$0,1,2,3,4,i,e,\pi,x^x$结合在了一起.

Well,可是有很多吃瓜群众仍不满足,执意要把欧拉常数$\gamma$塞进去...

这个积分很精密的,禁不住这么魔改.不过还真有能塞一起的式子,不但能把$e,\pi,\gamma$一网打尽还能塞个Glaisher常数$\rm A$进去.

\[ - \zeta'(2) = \sum\limits_{k = 1}^\infty  {\frac{{\ln k}}{{{k^2}}}}  = \ln \prod\limits_{k = 1}^\infty  {\sqrt[{{k^2}}]{k}}  = \zeta (2)\ln \left( {\frac{{{{\rm A}^{12}}}}{{2\pi {e^\gamma }}}} \right)\]

Read More

积分习题XI:孪生积分

Aster 数学题集 Leave a Comment

所谓孪生积分就是一种积分技巧,就是一次性算两个积分.唔,这是很常用的积分技巧啦....教科书上基本都有.

一般用于三角函数积分.....就是用的多了会养成习惯....然后连简单的积分都用这个.....然后就没有然后了,因为简单的考试题用基本的积分技巧就能秒了,用这个不是找事情么....


我们来研究这样一个积分:

$$F(x) = \int {\frac{{c + d\;{\text{Tri}}(x)}}{{a + b\;{\text{Tri}}(x)}}{\text{d}}x}$$

Read More

积分习题X:格拉瑟主定理

Aster 数学题集, 理宅异闻录 Leave a Comment

格拉瑟主定理(Glasser's Master Theorem)的标准表述如下:

恒等式$PV\int_{ - \infty }^{ + \infty } {F(\phi (x)){\rm{dx}}}  = PV\int_{ - \infty }^{ + \infty } {F(x){\rm{dx}}} $对任意可积函数$F(x)$和$\phi (x) = |a|x - \sum\limits_{n = 1}^N {\frac{{|{\alpha _n}|}}{{x - {\beta _n}}}} $成立.

其中$a,\left\{ {{\alpha _n}} \right\}_{n = 1}^N,\left\{ {{\beta _n}} \right\}_{n = 1}^N$可以是任意常数,PV是柯西主值(Cauchy Principal Value)不可以两边约掉的啊魂淡可我怎么总是有种两边划掉的强烈冲动怎么办才好啊好烦啊要控制不住了的说....

So....这玩意儿有什么用呢?

叫你证仨积分,汝敢答应否?

$$\begin{aligned}
{I_1} &= \int_{ - \infty }^{ + \infty } {\frac{{{x^8} + 12{x^7} + 58{x^6} + 144{x^5} + 193{x^4} + 132{x^3} + 36{x^2}}}{{{x^{10}} + 12{x^9} + 51{x^8} + 72{x^7} - 81{x^6} - 300{x^5} - 43{x^4} + 576{x^3} + 664{x^2} + 264x + 36}}{\rm{d}}x} = \pi \\
{I_2} &= \int_{ - \infty }^{ + \infty } {\frac{{{x^8} + 4{x^7} + 6{x^6} + 4{x^5} + {x^4}}}{{{x^{12}} + 4{x^{11}} - 2{x^{10}} - 24{x^9} - 10{x^8} + 56{x^7} + 48{x^6} - 40{x^5} - 49{x^4} + 4{x^3} + 20{x^2} + 8x + 1}}{\rm{d}}x = \frac{\pi }{{\sqrt 2 }}} \\
{I_3} &=\int_0^\infty \frac{x^{14}-15x^{12}+82x^{10}-190x^8+184x^6-60x^4+16x^2}{x^{16}-20x^{14}+156x^{12}-616x^{10}+1388x^8-1792x^6+1152x^4-224x^2+16}\; dx = \frac{\pi}{2}
\end{aligned}$$

Read More

积分习题IX

Aster 数学题集 Leave a Comment

又到了喜闻乐见的杂题时间了,不过今天到场的有个重量级人物:

\[\int_0^1 {{e^{i\pi x}}} {\mkern 1mu} {x^x}{(1 - x)^{1 - x}}{\mkern 1mu} dx = \frac{e}{2}\frac{\pi }{3}\frac{i}{4}\]

哈,牛逼的木有吧,神奇的把$0,1,2,3,4,i,e,\pi,x^x$结合在了一起.

Read More

欧拉挑战:入门9段

Aster 欧拉挑战 Leave a Comment

P91:格点直角三角形

点P(x1, y1)和点Q(x2, y2)都是格点,并与原点O(0,0)构成ΔOPQ。

当点P和点Q的所有坐标都在0到2之间,也就是说0 ≤ x1, y1, x2, y2 ≤ 2时,恰好能构造出14个直角三角形。

如果0 ≤ x1, y1, x2, y2 ≤ 50,能构造出多少个直角三角形?

看到这种题第一反应就是生成函....那啥....我又看出规律了.....

编号1-14,对于s×s的正方形,首先有三种简单的情况,就是1,2,10以及8,9,14这种直角在角上的.$3{s^2}$到手.

不在角上的就比较麻烦了...画个草图

 

设直角那个叫$P({x_1},{y_1})$.然后就是$P({x_1},{y_1}),Q({x_2},{y_2}),O({x_0},{y_0})$.

$$ \begin{aligned}
&\because OP \bot PQ \\
&\therefore \overrightarrow{OP} \cdot \overrightarrow{PQ} = 0 \\
&\Rightarrow {x_1}{x_2} + {y_1}{y_2} = x_1^2 + y_1^2
\end{aligned}$$

化简下,于是就从几何问题转化为了代数问题,求这个的整数解.这时候开始穷举也行,不过还能化简公式.

$$ \begin{aligned}
&\quad\ \left\{ \begin{gathered}
{x_2} = {x_1} + a\\
{y_2} = {y_1} + b\\
\end{gathered} \right.\\
&\Rightarrow a{x_1} + b{y_1} = 0\\
&\quad\ d = GCD({x_1},{y_1})\\
&\Rightarrow (a,b) = ( - \frac{{{y_1}}}{d}n,\frac{{{x_1}}}{d}n)\\
&\Rightarrow f(s) = Min(\frac{{{y_1}}}{{{x_1}}}d,\frac{{s - {x_1}}}{{{y_1}}}d)\\
&\Rightarrow S = \sum\limits_{0 < {x_1},{y_1} < s} {f(s)} + 3{s^2}
\end{aligned}$$

翻译成代码,根据对称性卡死${x_1} < {y_2}$,这样还可以少一半计算量,最后乘以2补回去.

92:平方数字链

将一个数的所有数字的平方相加得到一个新的数,不断重复直到新的数已经出现过为止,这构成了一条数字链。

例如,

44 → 32 → 13 → 10 → 11
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

可见,任何一个到达1或89的数字链都会陷入无尽的循环。更令人惊奇的是,从任意数开始,最终都会到达1或89。

有多少个小于一千万的数最终会到达89?

硬计算差评,还有我又一次没看到小于号.....虽然不影响结果...

P93:算术表达式

使用集合{1, 2, 3, 4}中每个数字恰好一次以及(+, −, *, /)四则运算和括号,可以得到不同的正整数。

例如,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)

注意不允许直接把数字连起来,如12 + 34。

使用集合{1, 2, 3, 4},可以得到31个不同的数,其中最大值是36,以及1到28之间所有的数。

若使用包含有四个不同数字a < b < c < d的集合可以得到从1到n之间所有的数,求其中使得n最大的集合,并将你的答案写成字符串:abcd。

9个数字选4个,C(9,4)=126.四个符号选三个C(4,3)=4,7个位子8个空选两个放括号C(8,2)=28,全部乘起来也不大...

没括号的64种情况下是这样的,好吧我就是想秀一下我珍藏多年的强力函数.....

ListToExpression[list_]:=list//.({x___,PatternSequence[a_,u:#,b_],y___}:>{x,u[a,b],y}&/@{Power|Log|Surd,Times|Divide,Plus|Subtract});
OperatorRiffle[exp_,oper_:{Times,Divide,Plus,Subtract}] :=Grid[{#,ListToExpression@#}&/@(Riffle[exp,#]&/@Tuples[oper,Length@exp-1]),Alignment->Left];
OperatorRiffle[{a,b,c,d}]

虽然后来我想到这个其实直接变字符串然后连起来然后读回表达式就行....不过那样就无法装逼了...

而且这个方法对于Log,Surd这类非算子也有效,强制解释为最高级算子.而且运算优先级完全可以魔改,我就是规定加法优先乘法怎么着.....

注意相减算子是SubMinus,Minus是取负,不是个算子.MinusPlus, PlusMinus正负号,负正号这俩就连运算都不是了,只是个保留符号罢了.

Ok,回到这道题,不管怎么样我们就考虑怎么穷举出a,b,c,d的所有计算结果好了.

P94:几乎等边的三角形

可以证明,不存在边长为整数的等边三角形其面积也是整数。但是,存在几乎等边的三角形 5-5-6,其面积恰好为12。

我们定义几乎等边的三角形是有两条边一样长,且第三边与这两边最多相差1的三角形。

对于所有边长和面积均为整数且周长不超过十亿(1,000,000,000)的三角形,求其中几乎等边的三角形的周长之和。

底边不能是奇数,否则面积就会变成无理数.

设底边是$2n$,腰就是$2n \pm 1$,周长就是$6n \pm 2$,所以n的范围就出来了,然后只要判定高$\sqrt {5{n^2} \pm 4n + 1} $是否是整数就行了.

大概像这样 Select[Table[Sqrt[#1],{n,1*^6/3}],FractionalPart[#]==0&]&/@{1.0-4 n+5 n^2,1.0+4 n+5 n^2}

不行啊,周长10亿呢,得找个更强的公式...

设三边分别是$(a,b,c) = \left( {n,n,n + 1} \right)$

$$\begin{aligned}
S &= \frac{{n + 1}}{4}\sqrt {3{n^2} - 2n - 1} \\
&\Rightarrow 3{n^2} - 2n - 1 = {y^2}\\
&\Rightarrow n = \frac{{1 \pm \sqrt {3{y^2} + 4} }}{3}\\
&\Rightarrow {x^2} - 3{y^2} = 4,(x,y) \in {N_ + }
\end{aligned}$$

佩尔方程咯.....

Reduce[{x^2-3y^2==4,x>0,y>0},{x,y},Integers]

(14,8)对应的是(5,5,6)差了一项,要位移一格...

$$\left\{ \begin{gathered}
{x_{i + 1}} = {\left( {2 - \sqrt 3 } \right)^i} + {\left( {\sqrt 3 + 2} \right)^i}\\
{y_{i + 1}} = \frac{{{{\left( {\sqrt 3 + 2} \right)}^i} - {{\left( {2 - \sqrt 3 } \right)}^i}}}{{\sqrt 3 }}\\
\end{gathered} \right.$$

或者写成矩阵式就是

$$\left( {\begin{array}{*{20}{c}}
{{x_i}} \\ {{y_i}}
\end{array}} \right) = {\left( {\begin{array}{*{20}{c}}
2&3 \\ 1&2
\end{array}} \right)^i}\left( {\begin{array}{*{20}{c}}
4 \\ 2
\end{array}} \right)$$

然后代回原来的式子就行.

$\left( {n,n,n - 1} \right)$作同样的推导也是这个式子,这倒是省心了.

公式在手别说10亿了,10亿的平方都不怕了...

P95:亲和数链

一个数除了本身之外的因数称为真因数。例如,28的真因数是1、2、4、7和14。这些真因数的和恰好为28,因此我们称28是完全数。

有趣的是,220的真因数之和是284,同时284的真因数之和是220,构成了一个长度为2的链,我们也称之为亲和数对。

有一些更长的序列并不太为人所知。例如,从12496出发,可以构成一个长度为5的链:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)
由于这条链最后又回到了起点,我们称之为亲和数链。

找出所有元素都不超过一百万的亲和数链中最长的那条,并给出其中最小的那个数。

FindCycle[Graph[Table[i$$DirectedEdge](DivisorSigma[1,i]-i),{i,1,1*^5}]],Infinity] 

然后大点就爆了.....Well......换个函数就好...ConnectedComponents.....

P96:数独

数独(日语原意为数的位置)是一种热门的谜题。它的起源已不可考,但是与欧拉发明的一种类似而更加困难的谜题拉丁方阵之间有着千丝万缕的联系。数独的目标是替换掉9乘9网格中的空白位置(或0),使得每行、每列以及每个九宫格中恰好都包含数字1~9。一个构造精良的数独谜题应该包含有唯一解,且能够通过逻辑推断来解决,尽管有时可能必须通过“猜测并检验”来排除一些选项(这一要求目前还颇受争议)。寻找答案的复杂度决定了题目的难度;上面这个谜题被认为是简单的谜题,因为我们可以通过直截了当的演绎推理来解决它。

在这个6K的文本文件sudoku.txt(右击并选择“目标另存为……”)中包含有50个不同难度的数独谜题,但保证它们都只有唯一解(文件中的第一个谜题就是上述样例)。

解开这50个谜题,找出每个谜题解答左上角的三个数字并连接起来,给出这些数的和;举例来说,上述样例解答左上角的三个数字连接起来构成的数是483。

按例跳过未计时,另外回溯会超时,最好写逻辑判别.

P97:非梅森大素数

1999年人们发现了第一个超过一百万位的素数,这是一个梅森素数,可以表示为26972593−1,包含有2,098,960位数字。在此之后,更多形如2p−1的梅森素数被发现,其位数也越来越多。

然而,在2004年,人们发现了一个巨大的非梅森素数,包含有2,357,207位数字:28433×27830457+1。

找出这个素数的最后十位数字。

快速幂模,水过....

P98:重排平方数

将单词CARE中的四个字母依次赋值为1、2、9、6,我们得到了一个平方数:1296 = 362。神奇的是,使用同样的数字赋值,重排后的单词RACE同样构成了一个平方数:9216 = 962。我们称CARE和RACE为重排平方单词对,同时规定这样的单词对不允许有前导零或是不同的字母赋相同的值。

在这个16K的文本文件words.txt(右击并选择“目标另存为……”)中包含了将近两千个常见英文单词,找出所有的重排平方单词对(一个回文单词不视为它自己的重排)。

重排平方单词对所给出的最大平方数是多少?

注意:所有的重排单词必须出现在给定的文本文件中。

没做出来...放弃....

本来以为So easy的,直接照着说明写一遍就好了,结果发现赋值情况有点多,直接上估计跑到明天都跑不完...

P99:最大的幂

比较两个如211和37这样写成幂的形式的数并不困难,任何计算器都能验证211 = 2048 < 37 = 2187。

然而,想要验证632382518061 > 519432525806就会变得非常困难,因为这两个数都包含有超过三百万位数字。

22K的文本文件base_exp.txt(右击并选择“目标另存为……”)有一千行,每一行有一对底数和指数,找出哪一行给出的幂的值最大。

注意:文件的前两行就是上述两个例子。

高精计算,哦不,其实就是取个对数....真水.....

P100:安排概率

在一个盒子中装有21个彩色碟子,其中15个是蓝的,6个是红的。如果随机地从盒子中取出两个碟子,取出两个蓝色碟子的概率是P(BB) = (15/21)×(14/20) = 1/2。

下一组使得取出两个蓝色盘子的概率恰好为50%的安排,是在盒子中装有85个蓝色碟子和35个红色碟子。

当盒子中装有超过1012 = 1,000,000,000,000个碟子时,找出第一组满足上述要求的安排,并求此时盒子中蓝色碟子的数量。

$$\left\{ \begin{aligned}
&\frac{{B(B - 1)}}{{N(N - 1)}} = \frac{1}{2}\\
&0 < B < {10^{12}} < N
\end{aligned} \right.$$

有点懵逼,简单过头了吧放这,大概是100题了给你们庆祝下.....


58分30秒,欧耶,一小时内搞定,也就P93比较麻烦,其他稍微推导一下都能有思路.P96未计时,P98放弃.

欧拉挑战:入门8段

Aster 欧拉挑战 Leave a Comment

P81:路径和:两个方向

在如下的5乘5矩阵中,从左上方到右下方始终只向右或向下移动的最小路径和为2427,由标注红色的路径给出。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从该矩阵的左上方到右下方始终只向右和向下移动的最小路径和。

和67题一样,不过我那个算法只是定义给三角形的...

虽然正方形就是两个三角形叠起来,不过倒来倒去不麻烦嘛...

有的这么折腾还不如写个正统的动态规划.

$$\begin{aligned}
B[1,1] &= A[1,1]\\
B[i,j] &= B[i,j - 1] + A[i,j]\quad &if\;i = 1\\
&= B[i - 1,j] + A[i,j]\quad &if\;j = 1\\
&= \min (B[i - 1,j],B[i,j - 1]) + A[i,j]\\
\end{aligned}$$

然后直接公式翻译成代码就行了,注意Mathematica是少数和人类习惯一样下标从1开始的编程语言.

这倒不是MMA人性化或者傲娇.MMA的下标其实也是从0开始的,但是下标0分配给了类型,也就是表头.

动态规划写出来也和公式一样美观啊

B[1, 1] := A[[1, 1]];
B[1, j_] := B[1, j - 1] + A[[1, j]];
B[i_, 1] := B[i - 1, 1] + A[[i, 1]];
B[i_, j_] := B[i, j] = Min[B[i - 1, j], B[i, j - 1]] + A[[i, j]];

当然其实很多人觉得这个很丑来着你们说美观的是什么心态....所以我按另一种审美写了个:


P82:路径和:三个方向

注意:这是第81题的一个更具挑战性的版本。

在如下的5乘5矩阵中,从最左栏任意一格出发,始终只向右、向上或向下移动,到最右栏任意一格结束的最小路径和为994,由标注红色的路径给出。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从最左栏到最右栏的最小路径和。

我感觉到了套路的味道...下一道不会要四个方向了吧?

啊哈,还真是,我测了下连三个矩阵都是一样的说,那就是Dijkstra了......

不过我为什么要自己撸一个Dijkstra,脑子瓦特了,把他变成图,剩下的交给Mathematica...

我们可以直接邻接化这个80×80的矩阵变成6400×6400的大型稀疏邻接矩阵,然后AdjacencyGraph变成Graph对象....怎么感觉有点逗比..

不行我得查查高级解决方案....唔,有个古函数MakeGraph...不过这是个古函数了得找到激活方法....

10分钟过去了.......好吧,I'm angry,我之后得撸个程序包...


P83:路径和:四个方向

注意:这是第81题的一个极具挑战性的版本。

在如下的5乘5矩阵中,从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和为2297,由标注红色的路径给出。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和。

用HTML画表格好捉急啊...

HTML这种玩意儿是给人写的吗....


P84:大富翁几率

大富翁游戏的标准棋盘大致如下图所示:

GOA1CC1A2T1R1B1CH1B2B3JAIL
H2C1
T2U1
H1C2
CH3C3
R4R2
G3D1
CC3CC2
G2D2
G1D3
G2JF3U2F2F1R3E3E2CH2E1FP

玩家从标记有“GO”的方格出发,掷两个六面的骰子并将点数和相加,作为本轮他们前进的步数。如果没有其它规则,那么落在每一格上的概率应该是2.5%。但是,由于“G2J”(入狱)、“CC”(宝箱卡)和“CH”(机会卡)的存在,这个分布会有所改变。

除了落在“G2J”上,或者在“CC”或“CH”上抽到入狱卡之外,如果玩家连续三次都掷出两个相同的点数,则在第三次时将会直接入狱。

游戏开始时,“CC”和“CH”所需的卡片将被洗牌打乱。当一个玩家落在“CC”或“CH”上时,他们从宝箱卡和机会卡的牌堆最上方取一张卡并遵循指令行事,并将该卡再放回牌堆的最下方。宝箱卡和机会卡都各有16张,但我们只关心会影响到移动的卡片,其它的卡片我们都将无视它们的效果。

  • 宝箱卡 (2/16 张卡):
    • 回到起点“GO”
    • 进入监狱“JAIL”
  • 机会卡 (10/16 张卡):
    • 回到起点“GO”
    • 进入监狱“JAIL”
    • 移动到“C1”
    • 移动到“E3”
    • 移动到“H2”
    • 移动到“R1”
    • 移动到下一个“R”(铁路公司)
    • 移动到下一个“R”
    • 移动到下一个“U”(公共服务公司)
    • 后退三步

这道题主要考察掷出骰子后停在某个特定方格上的概率。显然,除了停在“G2J”上的可能性为0之外,停在“CH”格的可能性最小,因为有5/8的情况下玩家会移动到另一格。我们不区分是被送进监狱还是恰好落在监狱“JAIL”这一格,而且不考虑需要掷出两个相同的点数才能出狱的要求,而是假定进入监狱的第二轮就会自动出狱。

从起点“GO”出发,并将方格依次标记00到39,我们可以将这些两位数连接起来表示方格的序列。

统计学上来说,三个最有可能停下的方格分别是“JAIL”(6.24%)或方格10,E3(3.18%)或方格24以及“GO”(3.09%)或方格00。这三个方格可以用一个六位数字串表示:102400。

如果我们不用两个六面的骰子而是用两个四面的骰子,求出三个最有可能停下的方格构成的数字串。

按惯例跳过,未计时.

这道题一点意思都没有,就是蒙特卡洛...

没有监狱的话还好,是个马尔科夫过程,加入了入狱出狱的设定就瞬间炸了,没有数学模型能解了...


P85:数长方形

如果数得足够仔细,能看出在一个3乘2的长方形网格中包含有18个不同大小的长方形,如下图所示:

尽管没有一个长方形网格中包含有恰好两百万个长方形,但有许多长方形网格中包含的长方形数目接近两百万,求其中最接近这一数目的长方形网格的面积。

我就数得一点都不仔细,我数了好几遍还没数对.感觉这种题肯定有生成函数解法.

好吧不用生了,脑袋转个弯就出来了,长方形就是长里面选两条,宽里面选两条,那就是

$$S(i,j) = C_i^2C_j^2 = \frac{1}{4}({i^2} + i)({j^2} + j)$$

这么说顺便也解决掉了高维中的情况了,然后就解方程呗....

我还是给点干货吧,如果是求正方形的话就是小正方形移动呗,然后高维推广也不难看出,化简就免了...

$$\begin{aligned}
d &= \min (m,n)\\
S&=\sum\limits_{a = 1}^{d - 1} {(m - a)} (n - a)\\
&= \frac{1}{6}(d - 1)(2{d^2} - d(3m + 3n + 1) + 6mn)\\
&= \frac{1}{6}(d - 1)(3mn - d(d + 1))
\end{aligned}$$


P86:长方体路径

蜘蛛S位于一个6乘5乘3大小的长方体屋子的一角,而苍蝇F则恰好位于其对角。沿着屋子的表面,从S到F的最短“直线”距离是10,路径如下图所示:

然而,对于任意长方体,“最短”路径实际上一共有三种可能;而且,最短路径的长度也并不一定为整数。

当M=100时,若不考虑旋转,所有长、宽、高均不超过M且为整数的长方体中,对角的最短距离是整数的恰好有2060个;这是使得该数目超过两千的最小M值;当M=99时,该数目为1975。

找出使得该数目超过一百万的最小M值。

死算的话有点慢,我们来分析下:

令${F(k)}$是当最大长度为k的长方体中解的数目,所以我们要求的就是第一个使得$\sum\limits_{1 \leqslant k \leqslant n} {F(k)}$超过百万的n值减1. 其他两条边与k构成勾股三元组 .因此对于固定的b,每一种b能被写成两个小于k的正整数之和的方式代表另一个解.

于是我们发现对于给定的b ≤ 2k,解就是$\left\lfloor {\frac{b}{2}} \right\rfloor  + 1 - Max(1,k - b)$,值为0代表无解. 然后加起来就是固定$k$下的解数目了.


P87:素数幂三元组

最小的可以表示为一个素数的平方,加上一个素数的立方,再加上一个素数的四次方的数是28。实际上,在小于50的数中,一共有4个数满足这一性质:

28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24

有多少个小于五千万的数,可以表示为一个素数的平方,加上一个素数的立方,再加上一个素数的四次方?

我靠,不会是三重循环遍历吧,有点坑爹啊,我要骂人了,这几道题太不友好了....

这种题你和我说有会有数论解法?数论解法估计是没有的了,造个筛法应该还是可以的.

当然是从高次开始筛,减完筛低次,全都筛完还剩下的就是解了.该程序已同步到BGG包.


P88:积和数

若自然数N能够同时表示成一组至少两个自然数{a1, a2, … , ak}的积和和,也即N = a1 + a2 + … + ak = a1 × a2 × … × ak,则N被称为积和数。

例如,6是积和数,因为6 = 1 + 2 + 3 = 1 × 2 × 3。

给定集合的规模k,我们称满足上述性质的最小N值为最小积和数。当k = 2、3、4、5、6时,最小积和数如下所示:

k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6

因此,对于2≤k≤6,所有的最小积和数的和为4+6+8+12 = 30;注意8只被计算了一次。

已知对于2≤k≤12,所有最小积和数构成的集合是{4, 6, 8, 12, 15, 16},这些数的和是61。

对于2≤k≤12000,所有最小积和数的和是多少?

可能性太多了,写不出跑进1 min的算法...放弃

不过我当时搜索到了一篇论文Arixv,然而看不太懂他在说啥...


P89:罗马数字

要正确地用罗马数字表达一个数,必须遵循一些基本规则。尽管符合规则的写法有时会多于一种,但对每个数来说总是存在一种“最好的”写法。

例如,数16就至少有六种写法:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

然而,根据规则,只有XIIIIII和XVI是合理的写法,而后一种因为使用了最少的数字而被认为是最有效的写法。

在这个11K的文本文件roman.txt (右击并选择“目标另存为……”)中包含了一千个合理的罗马数字写法,但并不都是最有效的写法;有关罗马数字的明确规则,可以参考关于罗马数字

求出将这些数都写成最有效的写法所节省的字符数。

注意:你可以假定文件中的所有罗马数字写法都不包含连续超过四个相同字符。

阅读理解题...解略


P90:立方体数字对

在一个立方体的六个面上分别标上不同的数字(从0到9),对另一个立方体也如法炮制。将这两个立方体按不同的方向并排摆放,我们可以得到各种各样的两位数。

例如,平方数64可以通过这样摆放获得:

事实上,通过仔细地选择两个立方体上的数字,我们可以摆放出所有小于100的平方数:01、04、09、16、25、36、49、64和81。

例如,其中一种方式就是在一个立方体上标上{0, 5, 6, 7, 8, 9},在另一个立方体上标上{1, 2, 3, 4, 8, 9}。

在这个问题中,我们允许将标有6或9的面颠倒过来互相表示,只有这样,如{0, 5, 6, 7, 8, 9}和{1, 2, 3, 4, 6, 7}这样本来无法表示09的标法,才能够摆放出全部九个平方数。

在考虑什么是不同的标法时,我们关注的是立方体上有哪些数字,而不关心它们的顺序。

{1, 2, 3, 4, 5, 6}等价于{3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6}不同于{1, 2, 3, 4, 5, 9}

但因为我们允许在摆放两位数时将6和9颠倒过来互相表示,这个例子中的两个不同的集合都可以代表拓展集{1, 2, 3, 4, 5, 6, 9}。

对这两个立方体有多少中不同的标法可以摆放出所有的平方数?

允许6 9 相互表示....好好的一个组合问题,这样岂不是把问题复杂化了...

嗯?不对,其实没区别,Subsets[{0, 1, 2, 3, 4, 5, 6, 7, 8, 6}, {6}]就行了.

然后把这些组合分配给俩骰子,C(C(10, 6), 2) = 21945种,穷举不虚的...

然后就是要造一个函数判定一个俩序列是否可以组成平方数.

怎么判定呢....继续穷举好了,穷举所有能构成的数字,看看最后能否包括所有的平方数.

那计算量再乘以6×6那就是790 020,连百万都没有我就放心穷举了.

不过还是可以做点小优化的,比如先删掉所有的7,MemberQ 9次太笨了,直接Union上去看看有没有变化就行了.

不知为何这道题做出来的人不多,难度显示说有40%......


连续计时,1小时46分钟11秒....要命,都是硬计算....

你知道吗,我做到30题的时候感觉2小时能杀光100题是绰绰有余的...然后就不断被各种题各种焦作人了.....

主要是查资料查起来没时间感.....有这个查的时间自己撸代码也能撸出来了....."

欧拉挑战:入门7段

Aster 欧拉挑战 Leave a Comment

P71:有序分数

考虑形如n/d的分数,其中n和d均为正整数。如果n < d且其最大公约数为1,则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可以看出2/5是3/7直接左邻的分数。

将所有d ≤ 1,000,000的最简真分数按大小升序排列,求此时3/7直接左邻的分数的分子。

找个函数来表示接近程度,就是求

$$f(n) = \frac{1}{n}\left\lfloor {\frac{{3n}}{7}} \right\rfloor $$

最大值的意思,写完代码我看了眼输出,我突然想到,我在写什么玩意儿...

这玩意儿不是以7位周期单调递增吗, 999999 = 142857×7 那岂不是直接求f(999 992)到f(999 999)就完事了...


P72:分数计数

考虑形如n/d的分数,其中n和d均为正整数。如果n < d且其最大公约数为1,则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可以看出该集合中共有21个元素。

d ≤ 1,000,000的最简真分数构成的集合中共有多少个元素?

最简真分数的个数其实就是欧拉函数值,想下欧拉函数给出与n互质的正整数数目,互质那不就最简真分数了吗

没听说过欧拉函数的和函数有快速计算方法的,死算吧,顶多来个并行.


P73:分数有范围计数

考虑形如n/d的分数,其中n和d均为正整数。如果n < d且其最大公约数为1,则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可以看出在1/3和1/2之间有3个分数。

将d ≤ 12,000的最简真分数构成的集合排序后,在1/3和1/2之间有多少个分数?

我们用聪明点的穷举,对于分母a,先卡死上下界,求里面和a互质的数个数就行.

ParallelSum[Boole[CoprimeQ[a,b]],{a,1,12000},{b,Floor[a/3+1],Ceiling[a/2-1]}]

我们来封装成函数


P74:数字阶乘链

145之所以广为人知,是因为它的各位数字的阶乘之和恰好等于本身:

1! + 4! + 5! = 1 + 24 + 120 = 145

而169则可能不太为人所知,尽管从169开始不断地取各位数字的阶乘之和构成了最长的循环回到169;事实上,只存在三个这样的循环:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

不难证明,从任意数字出发最终都会陷入循环。例如,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

从69开始可以得到一个拥有五个不重复项的链,但是从一个小于一百万的数出发能够得到的最长的无重复项链包含有60项。

从小于一百万的数出发,有多少条链恰好包含有60个不重复项?

有种不祥的预感,是不是又要用编译了...

用点小技巧,网上去查所有的不动点和循环链,然后用模式对象和递归机制可以稍稍优化下.

其实之前Collatz那题也应该这么做,不过当时我没想到.


P75:唯一的整数边直角三角形

只能唯一地弯折成整数边直角三角形的电线最短长度是12厘米;当然,还有很多长度的电线都只能唯一地弯折成整数边直角三角形,例如:

12厘米: (3,4,5)
24厘米: (6,8,10)
30厘米: (5,12,13)
36厘米: (9,12,15)
40厘米: (8,15,17)
48厘米: (12,16,20)

相反地,有些长度的电线,比如20厘米,不可能弯折成任何整数边直角三角形,而另一些长度则有多个解;例如,120厘米的电线可以弯折成三个不同的整数边直角三角形。

120厘米: (30,40,50), (20,48,52), (24,45,51)

记电线长度为L,对于L ≤ 1,500,000,有多少种取值只能唯一地弯折成整数边直角三角形?

这题我想错了,我用的勾股树算法

后来想到干嘛不用广义勾股数组,所有的勾股数组都能写成这个形式:

$${({a^2} - {b^2})^2} + {(2ab)^2} = {({a^2} + {b^2})^2}$$

嗯,我们来看一看一个流程完整的函数是什么样子的:

一个标准的函数同时要包括说明,属性设定和错误捕捉,可以的话要有必要的注释.

换行这种东西就无所谓了,看个人风格,我喜欢写成砖头的样子,一行一赋值,有模块或者循环就缩进.If尽量写一行.该代码已整合进BGG.本来还想加上并行化的,但是并行循环这玩意儿实在是难写,写了会儿不想动了...

然后可以直接调用RTCount[15*^5].


P76:加和计数

将5写成整数的和有6种不同的方式:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

将100写成整数的和有多少种不同的方式?

F1,内置水过...


P77:素数加和

将10写成素数的和有5种不同的方式:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

写成素数的和有超过五千种不同的方式的数最小是多少?

你以为换成素数我就秒杀不了了吗,直接数?


P78:硬币分拆

记p(n)是将n枚硬币分拆成堆的不同方式数。例如,五枚硬币有7种分拆成堆的不同方式,因此p(5)=7。

OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O

找出使p(n)能被一百万整除的最小n值。

秒杀吧.......Well,失败了,要跑好久,让他跑着吧,我做下一题了....


P79:密码推断

网上银行常用的一种密保手段是向用户询问密码中的随机三位字符。例如,如果密码是531278,询问第2、3、5位字符,正确的回复应当是317。

在文本文件keylog.txt中包含了50次成功登陆的正确回复。

假设三个字符总是按顺序询问的,分析这个文本文件,给出这个未知长度的密码最短的一种可能。

不想解释,这个问题推广一下就能黑密保卡了....

如果我能一直监听一个用户输密保密码,足够多的次数后就能得知这张密保卡上写了啥啦!


P80:平方根数字展开

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

对于前一百个自然数,求所有无理数平方根小数点后一百位数字的总和。

最近几道压轴题里最水的,RealDigits秒了.....

Total@Flatten@Table[RealDigits[Sqrt@i, 10, 100, -1], {i, 100}]

大叉,纳尼???然后我看了半天发现要求的是无理数,Well,还要额外处理一下.......

还有是求前100位不是小数点后100位,不过我记得Decimal digits不是小数位的意思吗...

Total@Flatten[First@RealDigits[#,10,100]&/@Cases[Sqrt@Range@100,Except[_Integer]]]


连续计时26分59秒,P75看上去简单但是还是有点难,P80题没看懂瞎搞,一次冻30秒,无妄之灾...