最多和为整数的三元组
给定整数n,请找出[0,1)中n个互不相同的实数,使其中和为整数的三元组尽量多。比如n=3,那么显然只有一组,比如可选0,1/3,2/3
而n=4时,由于要求数字互不相同,也只有一组。
而n=5时,可以有两组,比如0,1/6,1/3,1/2,2/3有两三元组0+1/3+2/3,1/6+1/3+1/2
n=6
对于\(n=6\), 最多能有4组,如下图所示。图中在一条直线段上的3个小数之和为整数。图1
由于要求为不同的纯小数,故两个整和三元组最多只能有1个公共元。表现在图中就是两条直线段最多只有一个交点。
x为整数可以表为\(x\equiv0\pmod1\),(以下省略\(\mod1\)简写为\(x\equiv0\))于是上图所示4个三元组对应一个四行的同余方程组:
\[\begin{align}x+y+z&\equiv0\tag1\\x+v+w&\equiv0\tag2\\u+y+w&\equiv0\tag3\\u+v+z&\equiv0\tag4\end{align}\]
\((2)+(3)+(4)-(1)\)得
\
由于\(u+v+w\not\equiv0\)(因与既有三元组\((2),(3),(4)\)皆有2个交点)
故可得\
与\((2),(3),(4)\)比较即得\
任取纯小数\(x,y,z\),保持\(x+y+z=1,x\not\equiv y+1/2,y\not\equiv z+1/2,z\not\equiv x+1/2\)即可得到一组符合要求的解.
比如取\(x=1/12,y=2/12,z=9/12\),可得到图2所示的有理解。
图2
由\((1)+(5)\)可得\
这是任意6点构成4线的必然要求。
n=7
\(n=7\)的时候最多有5组解。可以分为两种情况讨论。一、存在两条平行线(即两个无公共元的三元组)
如图1(鼠标悬停可见插图编号),易得\(3t\equiv0\), 即\(t\equiv0 or \frac13\). 这两种解都存在,实例见图1-1和图1-2
二、不存在平行线
解的拓扑必是以下图2的子图。图2包括7点7线(中间的圆也看作1条线),最大解的拓扑必定比图2少2条线。用反证法易证。
假如只少1条线,即有6条线,不妨去掉中心的圆(因为7线平等对称),则不含\(y,v,t\)中任何1点的其它6点都构成6点4线图,那么由2#的\((6)\)得
\(x\equiv z\equiv w\equiv u+1/2\)
这违反了各数不同的要求。
5线解是容易得到的(略). 删除 这个问题是不是埃及分数问题的一个特例? 删除 删除 删除 应该不是新序列,但是很难证明 方程组无解判断有点困难,比如下面n=7和n=8问题都无解,但是让计算机判断感觉挺麻烦的 BCEADEACFBDFABGCDGEFG +1A+1D+1F+3G +1B+1D+1F +1C+1D+1G +2D+4G +1E+1F+1G +2F+4G +6G6G=0 i)D=4G,F=D+1/2 1A-1G+12=0 1B+2G+1/2=0 1C-1G=0 1E-G+1/2=0 ii) D=F+1/2, F=4G 1A-1G+12=0 1B+2G+1/2=0 1C-1G+1/2=0 1E-1G=0ABEACFBDFADGCEGBCHDEHFGH +1A+2E+1G+2H +1B+2E+2G+1H +1C+1E+1G +1D+1E+1H +3E +1F+1G+1H +3G +3H =>E+G+H=0=>A=G,B=H,C=H,D=G,F=E