由互质点织成的一块布

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 所以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

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