最多和为整数的三元组

zhouguang

n=7的时候最多有5组解。
如下图，如果共线的数的和为整数，那么图（1）中的两个红点的差一定是半整数（即等于1/2mod1），同理黄色点对和绿色点对的差也是半整数。如此一来，图（2）中的三个红点两两之差为半整数就没法安排了。故，n=7时没法安排6组。而图（3）的5组是可以的。

zhouguang

n=8时，可以有7组。

hujunhua

可否先解决一个较简单的问题：从一个n元集S中取最多的3元子集组成集合G，使得G中的任意两个集合最多只有一个公共元。
记G的阶为\(g_n\)，易得\(g_0=g_1=g_2=0, g_3=g_4=1,g_5=2,g_6=4\).
\(g_7=7,g_8=8,g_9=12\).
我觉得这应该是一个简单的具有多项式通项的数列。

这是一个与主帖密切相关的问题。

wayne

$n=9$,$a_9$最多是$10$,因为上确界就是n棵树每行3棵的植树问题.http://oeis.org/A003035

弄不好,该数列是http://oeis.org/A007997

\(\displaystyle a_n=\lceil\frac{(n-1)(n-2)}{6}\rceil\)

1                0
2                0
3                1
4                1
5                2
6                4
7                5
8                7
9                10
10                12
11                15
12                19
13                22

mathe

其实可以之间选择i/n,i=0,1,…,n-1,然后看看有多少组

mathe

还是wayne厉害，看出同植树问题的关联。当然hujunhua的上界也没有问题，只是有点宽松

无心人

存在代数数的解么？

wayne

噢,A007997允许实数相同,不同的就是A058212了, 虽然这两个差别只是初始项.

For n >= 3, number of solutions to x+y+z=0 (mod n) with 0<=x<y<z<n. E.g. for n=3 there is a unique solution, x=0, y=1, z=2.

这个跟mathe的命题应该是等价的吧

wayne

无心人 发表于 2014-3-29 08:53
存在代数数的解么？

你说的是无理数吧, 很有可能.

hujunhua

在计算了\(g_7,g_8\)后搜到了13#定义的\(g_n\)，是A01839
\[g_n=\begin{cases}
\displaystyle\lfloor\frac{n}3\rfloor\lfloor\frac{n-1}2\rfloor-1,&\text{if}\quad n\equiv5\pmod6\\
\displaystyle\lfloor\frac{n}3\rfloor\lfloor\frac{n-1}2\rfloor,&\text{if}\quad n\not\equiv5\pmod6
\end{cases}\]