欧拉挑战:初阶6段

Aster 未完成 Leave a Comment

P161:三联骨牌

三联骨牌是由三个正方形方块拼接而成的骨牌,它一共有两种基本形状:

如果计入旋转,则一共有六种可能的形状:

任何n乘m的方阵,只要nxm能够被3整除,就能用三联骨牌拼出来。
如果我们认为翻转或旋转是不同的拼法,那一个2乘9的方阵有一共有41种拼法:

一个9乘12的方阵有多少种拼法?

 

 

 

P162:十六进制数

十六进制数系统使用16个不同的数字:

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
十六进制数AF在十进制下等于10x16+15=175。

三位十六进制数10A,1A0,A10和A01都包含数字0,1和A。
和十进制下一样,在十六进制中没有前导零。

有多少至多十六位的十六进制数同时包含0,1和A?
用十六进制数表示你的答案。

(A,B,C,D,E和F均为大写字母,没有前导零或末尾标识符来表明该数字为十六进制,例如,1A3F不能写成:1a3f或0x1a3f或$1A3F或#1A3F或0000001A3F)

 

P163:纵横交错的三角形

考虑一个等边三角形,从三角形的每个顶点向对边的中点引一条线段,构成如下图所示的1级三角形。

我们可以从这个三角形中数出16个不同形状、不同大小、不同方向、不同位置的三角形。使用1级三角形作为材料,我们可以构成更大的三角形,比如右边的2级三角形。在2级三角形中可以输出一百零四个不同形状、不同大小、不同方向、不同位置的三角形。

可以看出一个2级三角形包含有4个1级三角形。一个3级三角形包含有9个1级三角形,而一个n级三角形包含有n2个1级三角形。

如果我们用T(n)表示n级三角形中能够数出的三角形个数,那么

T(1) = 16
T(2) = 104

求T(36)。

 

 

 

 

P164:没有连续三位数字的和超过给定值的数

有多少个20位数字n(不包括前导0)满足,不存在连续三位数字的和超过9?

 

 

P165:交点

一条线段由其两个端点唯一决定。考虑平面几何中的两条线段,一共有如下三种可能性:
两条线段没有、有一个或者有无数个交点。

进一步地,当两条线段恰好有一个交点时,可能这个交点是其中一条或两条的端点。如果这个交点不是任一条线段的端点,那它一定是这两条线段的内点。
当两条线段L1和L2的交点T是这两条线段唯一的交点且是这两条线段的内点时,我们称T为这两条线段的真交点。

考虑以下三条线段L1,L2和L3

L1: (27, 44) to (12, 32)
L2: (46, 53) to (17, 62)
L3: (46, 70) to (22, 40)

可以验证,线段L2和L3有一个真交点。注意到L3的一个端点(22,40)恰好在L1上,因此这不是一个真交点。L1和L2则没有交点。因此在这三条线段中,一共有一个真交点。

现在我们来对5000条线段求真交点数。首先,我们用“布鲁姆-布鲁姆-舒布”伪随机数生成算法生成2000个数。

s0 = 290797
sn+1 = sn×sn (modulo 50515093)
tn = sn (modulo 500)

为了生成每一条线段,我们使用tn的连续四项,也就是说,第一条线段是:

(t1, t2)至(t3, t4)

由上述算法生成的前四个数是:27,144,12和232,因此第一条线段是(27,144)至(12,232)。

在这5000条线段中,有多少个真交点?

 

 

P166:

 

 

 

 

 

 

 

 

 

 

P167:乌拉姆序列研究

任取两个正整数a和b,乌拉姆序列U(a,b)按如下方式定义:U(a,b)1 = a,U(a,b)2 = b,对于k > 2,U(a,b)k是比U(a,b)(k-1)更大,且存在用U(a,b)之前的这些项中的不同两项之和唯一表示的最小整数。

例如,序列U(1,2)的开头部分如下所示
1, 2, 3 = 1 + 2, 4 = 1 + 3, 6 = 2 + 4, 8 = 2 + 6, 11 = 3 + 8;
5不在这个序列是,因为5 = 1 + 4 = 2 + 3,有两种表示方法,同样地7也是如此因为7 = 1 + 6 = 3 + 4。

对于2 ≤ n ≤10,求∑U(2,2n+1)k,其中k = 1011.

 

 

P168:数字轮换

考虑数142857,我们可以将它的数字右移一位并把最后一个数字7放到最前面,得到714285。
可以验证714285=5×142857。
这表明了142857的一个特殊性质:它右移一位并把末位数字移至最前得到的数是它的倍数。

找出所有10 < n < 10100范围内满足这一性质的整数n,求它们的和的最后五位数字。

 

 

 

P169:探索将数表达为2的幂之和的方式数目

记f(0)=1,f(n)是将n表达为2的幂之和,且不同的幂至多使用两次的方式数目。

例如,f(10)=5,即有五种不同的方式表示10:

1 + 1 + 8
1 + 1 + 4 + 41 + 1 + 2 + 2 + 4
2 + 4 + 4
2 + 8

求f(1025)。

 

 

P170:求用乘积拼接而成的最大0至9全数字数

将6分别乘以1273和9854:

6 × 1273 = 7638
6 × 9854 = 59124

连接这两个乘积我们得到1至9全数字数763859124.我们称763859124为“6和(1273,9854)乘积的连接”。注意到,被乘的这些数的连接612739854,同样也是1至9全数字数。

对于0至9全数字数也存在同样的可能。

在所有由一个整数和另外至少两个整数的乘积连接而成且被乘的整数连接起来也是0至9全数字数的0至9全数字数中,求其中最大的一个。

 

发表评论