由互质点织成的一块布

mathe

问题二中n可以任意大。这里需要采用构造的方法，其中可以用到中国剩余定理

northwolves

问题二中n可以任意大。这里需要采用构造的方法，其中可以用到中国剩余定理
mathe 发表于 2009-11-21 20:34

mathe给构造一个,比如:n=3

mathe

取前$n^2$个素数排成n*n方阵。
设方阵中每行n个数乘积为$u_i$,每列n个数乘积为$v_i$
那么所有的$u_i$之间互素，同样所有$v_i$之间互素。
根据中国剩余定理
$x-=-(i-1) (mod u_i) ,1<=i<=n$有解
同样
$y-=-(i-1) (mod v_i), 1<=i<=n$有解
方阵[x,x+n-1]*[y,y+n-1]满足条件

KeyTo9_Fans

很巧妙的构造。

不过也许可以少取几个素数？

例如i行j列放2的话，

(i,j+2)，(i+2,j)，(i+2,j+2)都可以被2管到，所以可以不care了。

不过对于楼上的构造来说，这样做就显得画蛇添足了，因为楼上的构造是描述最简洁的。

但考虑到将来也许要提出 让(x+y)的值最小 这个要求，并为此摆设一个编程擂台。

那么上面的想法也许就会成为一个最基本的优化手段了。

另外，第一问是经典问题，所以自然会有很巧妙的做法。

但不知道所谓的巧妙解法是否被大部分人认同呢？

geslon

10#楼说：

问题三我们可以得到更好的结论，所有的黑点连通。
对于任意(x,y)=1,容易得出(x-1,y)或(x,y+1)互素，由此可以容易通过数学归纳法得出上面的结论
mathe 发表于 2009-11-21 20:23

是吗？
比如对于（35，6），它们互素，但是（34，6），（36，6），（35，5）（35，7）都不互素啊~~

mathe

我弄错了，关于问题三我的结论不成立

KeyTo9_Fans

我说一下第一问的经典解法，不知道大家是否认同。

当n足够大时，所求比例等于

3/4 * 8/9 * 24/25 * 48/49 * 120/121 * 168/169 * 288/289 * 360/361 * ...... * (p^2-1)/p^2 * ......

其中，p取遍所有素数。

考虑上式的倒数，它等于

4/3 * 9/8 * 25/24 * 49/48 * 121/120 * 169/168 * 289/288 * 361/360 *......* p^2/(p^2-1)*......

其中，p取遍所有素数。

其中，

4/3 = 1+1/4+1/16+1/64+1/256+......+1/4^k+......
9/8 = 1+1/9+1/81+1/729+1/6561+......+1/9^k+......
25/24 = 1+1/25+1/625+1/15625+1/390625+......+1/25^k+......
49/48 = 1+1/49+1/2401+1/117649+1/5764801+......+1/49^k+......
121/120 = 1+1/121+1/14641+1/1771561+1/214358881+......+1/121^k+......
...... ...... ...... ......

其中 k = 0, 1, 2, 3, ......

上述各式相乘并展开，等于

1+1/4+1/9+1/16+1/25+1/36+1/49+1/64+1/81+1/100+1/121+1/144+1/169+1/196+1/225+1/256+1/289+1/324+1/361+1/400+......

它恰好是所有正整数的平方倒数和。（大家想一想，这是为什么？）

因为所有正整数的平方倒数和为π^2/6，

所以所求比例是它的倒数，为6/π^2。

上述解答虽然是我自己想出来的，但书本上好像早就有这种解法了。不知道是谁最先想出来的呢？

另外，上述解答过程是否正确无误？是否严密无漏洞？

如果是正确严密的话，应该作为历史的经典载入史册，广为流传的。

不知道之前为什么没人贴上来，最后只好自问自答，像王婆卖瓜一样，颇为无奈。

mathe

第一问牵涉到这个概率的定义的问题。
准确的定义应该是设N*N的布上比率为P(N)(这是一个固定的整数），然后让N趋向无穷。
所以，没有足够的理由说明上面的方法得出的结果是准确的。

KeyTo9_Fans

我第一问的原文是“在[1,n]*[1,n](n→∞)的范围内，黑色方块所占的比例是否有极限？如何求这个极限值？”

意思和你说的定义完全一样嘛。是我表述得不够准确吗？

另外，P(N)有一个准确的上界：

我们只取p1,p2,...pn。

其中，(p1*p2*...*pn)^2<N

记M=sqrt(N)，取下整。

记T=p1*p2*...*pn

那么k关于素数p1、p2、... 、pn的余数在k=1到k=N之内至少完成了M个周期的变化。

在一个周期T里面，P(T)严格等于

(p1^2-1)/p1^2 * (p2^2-1)/p2^2 * ...... * (pn^2-1)/pn^2

虽然至少完整地跑完了M个周期，但第(M+1)个周期并不完整。

（实际上可能不止M个完整的周期，但讨论的是上界，就放缩到M/(M+1)好了）

由于讨论的是上界，所以不完整的部分认为全满，一个空洞也没有。



所以P(N)小于或等于

(P(T)*M^2+2M+1)/(M+1)^2

小于

(P(T)*M^2+3M)/(M^2+3M)

等于

(P(T)*M+3)/(M+3)

等于

P(T)*M/(M+3) + 3/(M+3)

小于

P(T) + 3/M

所以随着N的增大，这个上界单调递减。

另一方面，P(N)有一个准确的下界：

不完整的部分被清得一个不剩。



所以P(N)大于

P(T)*M^2/(M+1)^2 - ......

大于

P(T)*M^2/(M^2+3M) - ......

等于

P(T)*M/(M+3) - ......

大于

P(T)*(M-3)/M - ......

等于

P(T) - 3/M - ......

除此之外，还要考虑剩下的素数

p_(n+1)、p_(n+2)、......

的影响。

在N*N的范围内，素数p造成的空洞不多于(N/p)*(N/p)个，所占比例不多于1/p^2。

我们假设剩下的素数造成的空洞与之前的素数完全不重叠。

所以P(N)大于

P(T) - 3/M - 1/p'1^2 - 1/p'2^2 - 1/p'3^2 - ......

其中

p'1表示p_(n+1)，p'2表示p_(n+2)，……，依次类推。

记 S = 1/p'1^2 + 1/p'2^2 + 1/p'3^2 + ......

则P(N)大于

P(T) - 3/M - S

综上：

P(T) - 3/M - S < P(N) < P(T) + 3/M

其中，

(P(T) - 3/M - S)单调递增，极限与P(T)的极限相同。

(P(T) + 3/M)单调递减，极限与P(T)的极限相同。

由极限的夹逼性，P(N)的极限与P(T)的极限相同。

而P(T)的极限正是17#的做法。

所以17#的解答有效，不过确实需要补充上述内容。

另外，上述解答过程全部是即兴发挥，所以会有很多疏漏之处，我会仔细检查，找出来并改正。

mathe

使用两边夹来证明应该是正确的方法。不过严格证明起来应该是有些罗嗦的