微信群个数最值

guanmo1

realnumber

试着转化为平面图形,把人看作点,同一个微信群里的人看作同一直线上的点
这样一个三角形三点以及边上三个中点和重心,一共7个点,有6条线
(1)猜是这种k最大,k=6  (也可以是,一个四边形顶点及对边交点及对角线交点,7个点)
(2)猜是最大k=7

realnumber

n=7,k=6如图,点表示人,直线表示微信群

以下用反证法说明k≥7不成立,
若有k≥8成立,则保留其中7个群,解散其余微信群,因解散多出来没加群的人都加入某个群,此时得到符合要求的7个群,
也即只需说明k=7不成立,即可说明k≥7不成立.以下进行证明,
每群至少有3人,7个群,得至少有21人次(模仿战斗机出动次数,比如5架飞机,每架出动2次,共出动10架次)
21÷7=3,平均每人出现3次,即有人同时出现在3个群,如图

此时已有n=7人,说明余下的4个群只能由除这个人以外6人组建.(若这个人在第四个群的话,那么人数至少有9人>n=7)
又由之前21÷7=3得到每人都恰好在3个群
这样得到如下7个群,7个人依次编号1~7,同一个集合表示一个群
{1,2,3}{1,4,5}{1,6,7}
{2,4,6}{2,5,7}{3,4,7}{3,5,6}amazing,也就是说n=7时,$k_{max}=7$(最初的图,可以把三边中点组成一个群的,对应转化可以参考,需要考虑是否可以转化)

以下证明k=8不成立,8群,每群至少3人,那么有24人次,24÷7>3,说明有人加了4个群,之前已经说明矛盾了,至少9人了

realnumber

(2)以下证明n=9时,k最大还是7
假设某成员A最多只能出现在4个微信群,如图,(5个或以上的话,人数会多于9)

在上图基础上,新的微信群必须在集合{B,C},{D,E},{F,G},{H,I}各选一个构成新群,比如微信群{B,D,F,H},微信群{B,E,G,I}
至此,已经有6个微信群,如图所示的6条直线,

第7个微信群已经不能建了,新建的群总会和(第5,6两个之一)微信群{B,D,F,H}或微信群{B,E,G,I}有2个公共元素,

如此可得每个成员最多只能出现在3个微信群,如图比如A

新建的群,只能在(除掉A)三线上各选1点,此时过B,C最多各有2个微信群,合计7条.
而每个成员最多只能出现在2个微信群显然是不够k=7.
综上所得k最大为7.

realnumber

提问:一个要使k最大为9,n是否有,有的话最小n多大?