证明：在坐标平面任意给定13个整点,则必有一个以它们中的三个点为顶点的三角形,其重心也是整点

Question

证明：在坐标平面任意给定13个整点,则必有一个以它们中的三个点为顶点的三角形,其重心也是整点

Answer 1

设 13个点为 Pi =(xi,yi),i=1,2,...,13
当取Pi,Pj,Pk 3点构成三角形时,其重心坐标为 (（xi+xj+xk)/3,(yi+yj+yk)/3).
除3的同余类只有3个.于是Pi中必有5个点的x坐标在同一个除3的同余类中,而这5个点的任意3个点的 x坐标平均值必是整数.下面在这5点中,考虑y坐标,只有以下两种情形：
1.在三个同余类都存在,即存在Pi,Pj,Pk 使得：3|yi ,3|(yj-1),3|(yk-2),
取这三点构成三角形,其重心必为整数.
2.在某个同余类至少有三个点的y坐标.则取此三点构成三角形,其重心必为整数.