mathe 发表于 2014-3-22 10:25:11

最多和为整数的三元组

给定整数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

mathe 发表于 2014-3-26 11:38:33

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线的必然要求。

mathe 发表于 2014-3-26 12:04:45

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线解是容易得到的(略).

hujunhua 发表于 2014-3-27 10:39:19

删除

liangbch 发表于 2014-3-27 13:11:00

这个问题是不是埃及分数问题的一个特例?

hujunhua 发表于 2014-3-27 16:37:31

删除

mathe 发表于 2014-3-27 18:41:57

删除

mathe 发表于 2014-3-27 20:32:57

删除

mathe 发表于 2014-3-27 20:59:36

应该不是新序列,但是很难证明

mathe 发表于 2014-3-28 12:51:58

方程组无解判断有点困难,比如下面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
页: [1] 2 3
查看完整版本: 最多和为整数的三元组