Pick定理的几个出人意料的应用

   

    考虑直线x+y=n，其中n是一个素数。这条直线将恰好通过第一象限里的n-1个格点（如上图，图中所示的是n=11的情况）。将这n-1个点分别和原点相连，于是得到了n-2个灰色的三角形。仔细数数每个三角形内部的格点数，你会发现一个惊人的事实：每个三角形内部所含的格点数都是一样多。这是为什么呢？


   

    Pick定理是说，在一个平面直角坐标系内，如果一个多边形的顶点全都在格点上，那么这个图形的面积恰好就等于边界上经过的格点数的一半加上内部所含格点数再减一。例如，上图多边形的边界上有8个格点，内部含有7个格点，那么其面积就等于8/2+7-1=10。我们曾经在这里看到过一个非常神奇非常诡异的证明。这个定理有一些非常巧妙的应用。在上面的问题里，所有三角形都是等底等高的，因此它们的面积都相等。另外，注意到x与y的和是一个素数，这表明x和y是互素的（否则x+y可以提出一个公因数d，与和为素数矛盾），也就是说(x,y)和原点的连线不会经过其它格点。既然所有三角形的面积都相等，边界上的格点数也相等，由Pick定理，我们就能直接得出每个三角形内部的格点数也相等了。

    另一个有趣的问题则是，一个n*n的正方形最多可以覆盖多少个格点？把这个正方形中规中矩地放在直角坐标系上，显然能够覆盖(n+1)^2个格点。貌似这已经是最多的了，不过如何证明呢？利用Pick定理，我们能够很快说明它的最优性。注意到由于任两个格点间最近也有一个单位的间距，再考虑到正方形的周长为4n，因此该正方形的边界上最多有4n个格点。把正方形边界上的格点数记作B，内部所含格点数记为I，于是它所能覆盖的总格点数等于I+B，由于I+B = I+B/2-1 + B/2+1 ≤ n^2 + 4n/2 + 1 = (n+1)^2，结论立即得证。

    一个东西最出神入化的运用还是见于那些与它八杆子打不着的地方。Farey序列是指把在0到1之间的所有分母不超过n的分数从小到大排列起来所形成的数列，我们把它记作F_n。例如，F_5就是

0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1

   

    Farey序列有一个神奇的性质：前一项的分母乘以后一项的分子，一定比前一项的分子与后一项分母之积大1。用Pick定理来证明这个结论异常简单。把分母不超过n的每一个0和1之间的分数都标在平面直角坐标系上，例如0/1就对应点(1,0)，1/5就对应点(5,1)。考虑一根从原点出发的射线由x轴正方向逆时针慢慢转动到y轴正方向，这根射线依次扫过的标记点恰好就是一个Farey序列（因为Farey序列相当于是给每个标记点的斜率排序）。考虑这根射线扫过的两个相邻的标记点，它们与原点所组成的三角形面积一定为1/2——由于分数都是最简分数，因此它们与原点的连线上没有格点；又因为这是射线扫过的两个相邻的标记点，因此三角形内部没有任何格点。另外注意到，由于三角形面积等于叉积的一半，因此两个点(m,n)和(p,q)与原点组成的三角形面积应该为(mq-np)/2。于是，对于Farey序列的两个相邻分数n/m和q/p，我们有(mq-np)/2 = 1/2，即mq-np=1。

来源：
http://www.cut-the-knot.org/ctk/PickApps.shtml
http://www.cut-the-knot.org/ctk/PickToFarey.shtml

31 条评论

发表评论




Enter Captcha Here :