几个平面整点问题

constant · 发表于 2005-12-3 16:09:12

平面上的整点是x, y 坐标都是整数的点。设n为正整数，证明：

1。（难度：++）存在一个圆，使得圆内恰有n个整点。

2。（难度：++）存在一个正方形，使得正方形内恰有n个整点。

3。（难度：+++）设P是任意多边形，存在一个与P相似的多边形P'，使得P'内恰有n个整点。

4。（若没有提示，难度应该是+++++。给两个提示大约能降到+++）Schinzel 定理。存在一个圆，使得圆周上恰有n个整点。

Schinzel 圆的定义如下，对任意正整数n，

n = 2k 时，C_n: (x-1/2)^2 + y^2 = (1/4)*5^(k-1),
n = 2k+1 时，C_n: (x-1/3)^2 + y^2 = (1/9)*5^(2k)。

提示1。Schinzel 圆 C_n 上恰有n个整点。

提示2。用下列Fermat定理的推广证明提示1：

对任意正整数n，方程 x^2 + y^2 = n 的整数解个数为 4*(a-b)，其中a为n的形如4k+1的因子个数，b为n的形如4k+3的因子个数。

constant · 发表于 2005-12-6 06:37:36

一个都没人做

QL · 发表于 2005-12-7 01:21:39

Let me try 1, although I don't like very much the proof myself.

For any n, it is fairly clear that we can pick a disk large enough, centered at (0.5,0.5), such that it covers N>n number of grid points.

Now, we can shrink the radius, so that at least one of the covered point is on the circle. If there are more than one grid points on the circle, we can pick any one of them, move the center slightly away from it, make the radius a little bit larger, so that the new disk covers exactly the same grid points except that picked one. This way, we can reduce the number of covered grid points by 1. This process can continue, till desired number of grid points is reached.

During this process, we can make sure that the distance between the new and old center is as small as desired, and that is the reason that the procedure can continue.

野菜花 · 发表于 2005-12-7 01:54:52

因为笨, 加上忙(学期快结束), 仅有的一点时间又花在那个++++的脑坛聚餐的黑洞问题上(看起来不难，实际很难，怪自己没有自知之明)

这个第一题，我就用以前2N点的题的方法交个差吧！

以原点为园心， n 为半径先作一个园，这园里含有有限个格点m(>n^2)。所以只有有限对(C(m,2))，作每一对格点的垂直平分线，只有有限条，在原点周围找一点A不在任何这些垂直平分线上，这样这点到园内这m点的距离两两不同，将这些距离排序 : d1

以A为园心，[dn+d(n+1)]/2 为半径画园，园内恰好有 n 个格点。

constant · 发表于 2005-12-7 03:57:20

野菜花的方法和我的差不多，但我不先做一个圆，是做可数条线。

QL · 发表于 2005-12-10 16:07:26

With the hint, the difficulty of the n=2k case for question 4 is easy:

Consider: u^2+v^2 = 5^(k-1), by hint, the number of solutions is 4*k. Compare the original equation, for each solution (u,v), we have 2*x-1 = u, 2y = v or 2*x-1 = v, 2*y = v. Notice that one of u,v is odd, the other is even, so each pair of solutions (u,v) and (v,u) only lead to one integer solution (x,y). So the total number of solutions is 2*k = n

constant · 发表于 2005-12-10 17:05:47

Nicely done. The other part is similar.

QL · 发表于 2005-12-10 19:12:44

3. Similar idea used to solve 1 can be applied here.

For any n, we can make enlarge the polygon so that it covers N>n grid points, and no grid points on edges. Now, connecting every pair of the N points to get a set of segments A. Let B be the set of edges of the plygon. By rotating the polygon a little bit, so that none of the edges in B is parallel to any of the segments in A, and so that the polygon still cover the same set of grid points.

Now, shrink the polygon, so that at least one of the covered grid points is on an edge. Pick anyone of such grid points, by enlarging and shifting (but no rotation) a little bit, we can make sure that this grid point is the only grid point on the boundary. Now, shrink the polygon a little bit, and the number of grid points covered is reduced by one.

This procedure can be repeated till desired number of covered grid points reached.

constant · 发表于 2005-12-10 22:16:41

This is more complicated. Because the polygon may not be convex, when you shrink it you may actually add lattice points to it.

QL · 发表于 2005-12-10 23:50:41

Agree. Consider it as an proof for question 2 then.

		自动登录	找回密码
密码			立即注册

动态微博

几个平面整点问题

一个都没人做[:((][:((][:((]

回复：几个平面整点问题

第一题，交个差[:P]

两个都对

回复：几个平面整点问题

Nicely done. The other part is similar.

回复：几个平面整点问题

回复：回复：几个平面整点问题

回复：回复：回复：几个平面整点问题