2009-08-10 1:34| 
29 Comments | 本文内容遵从 
考虑直线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
沙发
板凳
的确诡异，自然就是这样~
考虑这根射线扫过的两个相邻的标记点，它们与原点所组成的三角形面积一定为1/2
————————
为什么呢……
地板
@楼上 内部没有点
根据皮克定理得到面积为1/2
最后那个很NB
Farey序列让我想起可恶的USACO
第一个问题跟江苏09高考数学附加题最后一题真神似。嗯，我没做出来。
Orz
就是说(x,y)和原点的连线不会经过其它格点.
请问如何理解“都不会经过其它格点”？
谢谢！
就是说(x,y)和原点的连线不会经过其它格点
请问 为什么？
谢谢
Pick定理的证明显然用到了微积分中的思想~~~
http://www.matrix67.com/blog/archives/92
dd回复:
matrix67同学 今欠 广大OIers：
1.一篇日志纠正黑书的错误
2.对《组合数学》一书中部分内容的形象理解
特立此凭证……
http://www.matrix67.com/blog/archives/92
引用dd回复:
{
matrix67同学 今欠 广大OIers：
1.一篇日志纠正黑书的错误
2.对《组合数学》一书中部分内容的形象理解
特立此凭证……
}
我也很想看
囧...真雷我...
= =|||。。。。。。一夜没睡。。。。
尝试着看吧。。。。
看到CounterBalance这个游戏：
http://www.pouet.net/prod.php?which=53620
不知M67是否感兴趣
cool
USACO...好遥远
Farey那个挺有意思！
大牛，我们acm组队，您给推荐个名字吧！英文的，先谢啦~
很久没来看看了
21L队名就叫“M67神牛”吧
是英文的啊……刚才没看到……
干脆“M67”算了
17L，Balance这类游戏的话就去找Perfect Balance，难度狂高！
好久没到处看看文章了。
强烈建议M67牛修改一下super-cache... 这东西貌似对cookie的支持很混乱.
I+B = I+B/2-1 + B/2+1 ≤ n^2 + 4n/2 + 1 = (n+1)^2
中为什么是 ≤ 啊，pick定理好像没有说 I+B/2-1 最大只能等于面积，应该要证明吧。
pick定理还有妙用：全部顶点都在格点上的正多边形，只有正方形一种。