免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 13个城市需要几个快递?2014浙江省数学竞赛第17题

本帖最后由 realnumber 于 2014-4-30 07:51 编辑

假设每个快递最多可以负责4个城市两两之间的直接联络(即6条线路),那么13个城市任何2个需要保持直接联络的话,最少需要几个快递?

p=4,n=13.13个点记为 M,$A_i,B_i,C_i,D_i(i=1,2,3)$.
那么13个$K_4$为$(M,A_1,A_2,A_3),(M,B_1,B_2,B_3),(M,C_1,C_2,C_3),(M,D_1,D_2,D_3)$,
$(A_1,B_1,C_1,D_1),(A_1,B_2,C_2,D_2),(A_1,B_3,C_3,D_3)$,
$(A_2,B_1,C_2,D_3),(A_2,B_2,C_3,D_1),(A_2,B_3,C_1,D_2)$,
$(A_3,B_1,C_3,D_2),(A_3,B_2,C_1,D_3),(A_3,B_3,C_2,D_1)$.
本问题的推广见6楼,未解决,欢迎加入.
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

$13$个城市任意取$2$个组成的数对个数:$C_{14}^2=78$
一个人负责$4$个城市,对应这$4$个城市任意取$2$个组成的数对个数:$C_4^2=6$
$\dfrac{78}6=13$

TOP

回复 5# realnumber
,还要考虑每$6$对数对中包含的城市不超过$4$个……

TOP

RE: (z)13个城市,需要几个快递负责?

本帖最后由 乌贼 于 2014-4-14 22:40 编辑

分两类:$1)2n$时  $s=1+2+3+\cdots+n-1=\dfrac{n(n-1)}2$
           $2)  2n+1$时  $s=1+2+3+\cdots+n-1+[\dfrac{2n}3]=\dfrac{n(n-1)}2+[\dfrac{2n}3]$
          其中$n\geqslant2,[x]$表示$\geqslant x$的最小整数
211.png
2014-4-14 22:37

TOP

回复 10# realnumber
推理混乱,重复计数……不玩了

TOP

本帖最后由 realnumber 于 2014-5-29 20:38 编辑

完全图是每对顶点之间都恰连有一条边的简单图.n个端点的完全图有个n端点及$\frac{n(n-1)}{2}$条边,以$K_n$表示.
高中毕业照1.jpg
2014-4-17 21:43

(以上来自维基百科,以下分析1楼问题的一般情景)

为方便叙述,先定义一个概念.
分割:某一个$K_n$的一些子图$K_p$,$K_p$之间无公共边,且$K_n$中的任意一边必定在某个$K_p$中,则称$K_n$被这些$K_p$分割,并记为$K_p\mid K_n$.不满足定义称$K_n$不被$K_p$分割,记为$K_p\nmid K_n$.

$K_n$被$K_p$分割的一个必要条件是$p(p-1)\mid {n(n-1)}$,且$(p-1)\mid {n-1}$,且$n-1\ge p(p-1)$.

证明:因为$K_n$有$C_n^2$条边,要被有$C_p^2$条边的$K_p$分割,则有$C_p^2\mid C_n^2$,即$p(p-1)\mid {n(n-1)}$.
$K_n$中从某一个顶点A出发的边有$n-1$条,点A还是$K_p$中某点,$K_p$中与A连接的边有$p-1$条,如此$(p-1)\mid {n-1}$.
接下来证明$n-1\ge p(p-1)$,取定一点M,含有点M的$K_p$共有$\frac{n-1}{p-1}$个,接下来另外的$K_p$所需要的p个点,最多从刚才的含M的每个$K_p$中分别取一点,因此有$\frac{n-1}{p-1}\ge p$,即$n-1\ge p(p-1)$.

很明显这个问题应该有实际的应用,如1楼问题.

以下检验它的充分性,还是从几个特例开始,不知道深浅,继续探索,本贴问题起因是张小明教授和同事徐的猜测.
因为手工检验,n,p(n>p)取值较小,若有擅长编程序的能一起来就好了.
p=2时,任意$n\ge2$符合条件,分割显然成立.
p=3时,符合上述条件的依次有n=7,9,13,15(7,9,13成立.15未验证或否定).
p=4时,同上,n=13,16,25(13,16成立,25未检验).
p=5时,同上,n=21,25(21成立,25未检验)
p=6时,同上,n=31,36(31成立,36未检验).
p=7时,同上,n=43,49(n=43检验中,49未检验).


实例:
p=3,n=7:
七个点依次为$A_i,i=1,2,3,4,5,6,7$,则7个$K_3$为$(A_1,A_2,A_3),(A_1,A_4,A_5),(A_1,A_6,A_7),(A_2,A_4,A_7),(A_2,A_5,A_6),(A_3,A_5,A_7),(A_3,A_4,A_6)$.
换个记法7点为$M,A_i,B_i,C_i,i=1,2$,有$(M,A_1,A_2),(M,B_1,B_2),(M,C_1,C_2)$,
$(A_1,B_1,C_1),(A_1,B_2,C_2,)$,$(A_2,B_1,C_2,),(A_2,B_2,C_1,)$.

p=3,n=9,九个点依次为$A_i,B_i,C_i,i=1,2,3$,排列成$3\times3$的矩阵,12个$K_3$正好是这个矩阵的行列与主副对角线.
换个记法$M,A_i,B_i,C_i,D_i,i=1,2$,
有$(M,A_1,A_2),(M,B_1,B_2),(M,C_1,C_2),(M,D_1,D_2),$
$(B_1,C_1,D_1),(B_2,C_2,D_2)$
$(A_1,B_1,C_2),(A_1,B_2,D_1),(A_1,C_1,D_2)$
$(A_2,B_1,D_2),(A_2,B_2,C_1),(A_2,C_2,D_1)$


p=3,n=13有26个$K_3$,
$M,A_i,B_i,C_i,D_i,E_i,F_i,i=1,2$,有26个$K_3$.
$(M,A_1,A_2),(M,B_1,B_2),(M,C_1,C_2),(M,D_1,D_2),(M,E_1,E_2),(M,F_1,F_2),$(本行$C_1$出现1次.)
$(A_1,B_1,?_),(A_1,B_2,?_?),(A_1,?_?,?_?)(A_1,?_?,?_?)(A_1,?_2,?_?)$(本行$C_1$出现1次.)---①
$(A_2,B_1,?_),(A_2,B_2,?_?),(A_2,?_?,?_?)(A_1,?_?,?_?)(A_2,?_2,?_?)$(本行$C_1$出现1次.)---②
$(B_1,),(B_1,),(B_1,),(B_2,),(B_2,),(B_2,)$(本行$C_1$出现1或2次.)---③
--以上累计22个$K_3$,点$M,A_1,A_2,B_1,B_2$都已经出现6次.
还有4个$K_3$,从只能由$C_i,D_i,E_i,F_i,i=1,2$取三个构成.
$(C_1,D_1,E_1),(C_2,D_2,F_2),(C_2,E_2,F_1),(D_2,E_1,F_1)$.本行出现一次的点是$C_1,D_1,E_2,F_2$,出现两次的点$C_2,D_2,E_1,F_1$.考虑到每一个点都恰好出现6次,因此在①②中与$B_1,B_2$搭配的只能是$C_2,D_2,E_1,F_1$.
$(M,A_1,A_2),(M,B_1,B_2),(M,C_1,C_2),(M,D_1,D_2),(M,E_1,E_2),(M,F_1,F_2),$
$(A_1,B_1,C_2),(A_1,B_2,E_1),(A_1,C_1,D_2)(A_1,D_1,F_1)(A_1,E_2,F_2)$
$(A_2,B_1,D_2),(A_2,B_2,F_1),(A_2,C_1,E_2)(A_1,C_2,E_1)(A_2,D_1,F_2)$
$(B_1,C_1,F_1),(B_1,D_1,E_2),(B_1,E_1,F_2),(B_2,C_1,F_2),(B_2,C_2,D_1),(B_2,D_2,E_2)$
$(C_1,D_1,E_1),(C_2,D_2,F_2),(C_2,E_2,F_1),(D_2,E_1,F_1)$.
如此$K_3\mid K_{13}$.


p=4,n=13.13个点记为 M,$A_i,B_i,C_i,D_i(i=1,2,3)$.
那么13个$K_4$为$(M,A_1,A_2,A_3),(M,B_1,B_2,B_3),(M,C_1,C_2,C_3),(M,D_1,D_2,D_3)$,
$(A_1,B_1,C_1,D_1),(A_1,B_2,C_2,D_2),(A_1,B_3,C_3,D_3)$,
$(A_2,B_1,C_2,D_3),(A_2,B_2,C_3,D_1),(A_2,B_3,C_1,D_2)$,
$(A_3,B_1,C_3,D_2),(A_3,B_2,C_1,D_3),(A_3,B_3,C_2,D_1)$.

p=4,n=16有20个$K_4$,16个点依次为$M,A_i,B_i,C_i,D_i,E_i,i=1,2,3$,
$(M,A_?,A_?,A_?),(M,B_?,B_?,B_?),(M,C_?,C_?,C_?),(M,D_?,D_?,D_?),(M,E_?,E_?,E_?)$,与点M搭配的三点下标先不区分.
$(B_1,C_1,D_1,E_1),(B_2,C_2,D_2,E_2),(B_3,C_3,D_3,E_3)$,不与MA搭配的下标依次标记为1,2,3.
$(A_1,B_1,C_2,D_3),(A_1,B_2,C_1,E_3),(A_1,B_3,D_1,E_2),(A_1,C_3,D_2,E_1)$
$(A_2,B_1,D_2,E_3),(A_2,B_2,C_3,D_1),(A_2,B_3,C_2,E_1),(A_2,C_1,D_3,E_2),$
$(A_3,B_1,C_3,E_2),(A_3,B_2,D_3,E_1),(A_3,B_3,C_1,D_2),(A_3,C_2,D_1,E_3),$
如此得到$K_4\mid K_{16}$.





p=5,n=21,共有21个$K_5$,$M,A_i,B_i,C_i, D_i,E_i,i=1,2,3,4$共21点,$(M,A_?,A_?,A_?,A_?),(M,B_?,B_?,B_?,B_?),(M,C_?,C_?,C_?,C_?),(M,D_?,D_?,D_?,D_?),(M,E_?,E_?,E_?,E_?)$,
(与M搭配的4点,下标可以先不作区分,都是A点(或B,C,D,E))
与$A_1$搭配的,从各个含M的$K_5$中必定取出的一点,且只能取一点,下标统一依次标记为1,2,3,4,
$(A_1,B_1,C_1,D_1,E_1),(A_1,B_2,C_2,D_2,E_2),(A_1,B_3,C_3,D_3,E_3),(A_1,B_4,C_4,D_4,E_4)$
$(A_2,B_1,C_2,D_3,E_4),(A_2,B_2,C_1,D_4,E_3),(A_2,B_3,C_4,D_1,E_2),(A_2,B_4,C_3,D_2,E_1)$
$(A_3,B_1,C_3,D_4,E_2),(A_3,B_2,C_4,D_3,E_1),(A_3,B_3,C_1,D_2,E_4),(A_3,B_4,C_2,D_1,E_3)$
$(A_4,B_1,C_4,D_2,E_3),(A_4,B_2,C_3,D_1,E_4),(A_4,B_3,C_2,D_4,E_1),(A_4,B_4,C_1,D_3,E_2)$
即$K_5\mid K_{21}$
想不到还是成立的.以前想当然以为穷举了,可就错了.



尝试中....
p=5,n=25,$M,A_i,B_i,C_i,D_i,E_i,F_i,i=1,2,3,4$,有30个$K_5$,
依次是$(M,A_1,A_2,A_3,A_4),(MB...),(MC...),(MD...),(ME...),(MF)$
$(B_1,C_1,D_1,E_1,F_1),(B_2,C_2,D_2,E_2,F_2),(B_3,C_3,D_3,E_3,F_3),(B_4,C_4,D_4,E_4,F_4)$,不与MA搭配的下标依次标记为1,2,3,4.
$(A_1,B_1,C_2,D_4,E_3),(A_1,B_2,C_3,D_1,F_4),(A_1,B_3,C_1,E_4,F_2),(A_1,B_4,D_2,E_1,F_3),(A_1,C_4,D_3,E_2,F_1)$
$(A_2,B_1,D_2,E_4,F_3),(A_2,B_2,C_4,D_3,E_1),(A_2,B_3,C_2,D_1,F_4),(A_2,B_4,C_3,E_2,F_1),(A_2,C_1,D_4,E_3,F_2)$
$(A_3,B_1,C_3,E_2,F_4),(A_3,B_2,D_4,E_3,F_1),(A_3,B_3,C_4,D_2,E_1),(A_3,B_4,C_1,D_3,F_2),(A_3,C_2,D_1,E_4,F_3)$
$(A_4,B_1,C_4,D_3,F_2),(A_4,B_2,C_1,E_4,F_3),(A_4,B_3,D_4,E_2,F_1),(A_4,B_4,C_2,D_1,E_3),(A_4,C_3,D_2,E_1,F_4)$.
不能得到$K_5\mid K_{25}$.--因为这条还有错误缺少$C_1D_2$,多了$C_2D_1$以及其它.
$(A_1,B_1,C_3,D_2,E_4),(A_1,B_2,C_1,D_4,F_3),(A_1,B_3,C_2,E_1,F_4),(A_1,B_4,D_1,E_3,F_2),(A_1,C_4,D_3,E_2,F_1)$
$(A_2,B_1,D_2,E_3,F_4),(A_2,B_2,C_4,D_1,E_3),(A_2,B_3,C_2,D_1,F_4),(A_2,B_4,C_3,E_2,F_1),(A_2,C_3,D_4,E_1,F_2)$
$(A_3,B_1,C_4,E_2,F_3),(A_3,B_2,D_4,E_3,F_1),(A_3,B_3,C_4,D_2,E_1),(A_3,B_4,C_1,D_3,F_2),(A_3,C_2,D_1,E_4,F_3)$
$(A_4,B_1,C_4,D_3,F_2),(A_4,B_2,C_1,E_4,F_3),(A_4,B_3,D_4,E_2,F_1),(A_4,B_4,C_2,D_1,E_3),(A_4,C_1,D_2,E_3,F_4)$.





p=6,n=16,共有8个$K_6$,$M,A_i,B_i,C_i,i=1,2,3,4,5$共16点,$(M,A_1,A_2,A_3,A_4,A_5),(M,B_1,B_2,B_3,B_4,B_5),(M,C_1,C_2,C_3,C_4,C_5),$,此时M有关的$K_6$已经考虑完毕.而再要构成一个$K_6$,从集合$\{A_i│i=1,2,3,4,5\}$中最多取一点,已经不够6点的要求.所以p=6,n=16时,有$K_6\nmid K_{16}$.从这个例子再得到一个必要条件$n-1\ge p(p-1)$.





p=6,n=31 31个点为$M,A_i,B_i,C_i,D_i,E_i,F_i,i=1,2,3,4,5$,共31个$K_6$,
含M的6个$K_6$为$(M,A_1,A_2,A_3,A_4,A_5),(M,B_1,B_2,B_3,B_4,B_5),(M,C_1,C_2,C_3,C_4,C_5),(M,D_1,D_2,D_3,D_4,D_5),(M,E_1,E_2,E_3,E_4,E_5),(M,F_1,F_2,F_3,F_4,F_5),$其余25个$K_6$每个必定从以上6个$K_6$中各取一点(M除外),如下:
$(A_1,B_1,C_1,D_1,E_1,F_1),(A_1,B_2,C_2,D_2,E_2,F_2),....$
$(A_2,B_1,C,D,E,F),(A_2,B_2,C,D,E,F),....$
$(A_3,B_1,C,D,E,F),(A_3,B_2,C,D,E,F),....$
$(A_4,B_1,C,D,E,F),(A_4,B_2,C,D,E,F),....$
$(A_5,B_1,C,D,E,F),(A_5,B_2,C,D,E,F),....$以上5行,每行5个$K_5$.
模仿p=5,n=21,考虑上述最后四行的BCDE的下标,因为A的缘故,1不能出现在第一列的$K_5$中,2不能在第二列,3,4,5依次也如此.
下面一行排不下了,为观察方便去掉AB,每行$K_6$依次去掉$A_1A_2A_3A_4A_5$,每列$K_6$依次去掉$B_1B_2B_3B_4B_5$,如下:
$(C_2,D_3,E_4,F_5),(C_3,D_5,E_1,F_4),(C_5,D_4,E_2,F_1),(C_1,D_2,E_5,F_3),(C_4,D_1,E_3,F_2)$
$(C_3,D_4,E_5,F_2),(C_5,D_1,E_4,F_1),(C_4,D_2,E_1,F_5),(C_2,D_5,E_3,F_1),(C_1,D_3,E_2,F_4)$
$(C_4,D_5,E_2,F_3),(C_1,D_4,E_4,F_5),(C_2,D_1,E_5,F_4),(C_5,D_3,E_1,F_2),(C_3,D_2,E_4,F_1)$
$(C_5,D_2,E_3,F_4),(C_4,D_1,E_5,F_1),(C_1,D_5,E_4,F_2),(C_3,D_1,E_2,F_5),(C_2,D_4,E_1,F_3)$
如此$K_6\mid K_{31}$.注意到每一列4个$K_6$下标循环轮换的特点,不妨取$A_2$所在行的每组CDEF的下标组成一个矩阵
\begin{pmatrix} 2&3&4&5\\ 3&5&1&4\\ 5&4&2&1\\ 1&2&5&3\\ 4&1&3&2\end{pmatrix}
其它的特征矩阵,随意地写了第一行,暂时发现都有特征矩阵,而且不是唯一的,如下表最后2个.
\begin{array}{|c|c|c|c|c|}
\hline
\begin{pmatrix} 3&2&4&5\\ 4&3&5&1\\ 5&4&1&2\\ 1&5&2&3\\ 2&1&3&4\end{pmatrix} &\begin{pmatrix} 2&4&5&3\\ 3&5&1&4\\ 4&1&2&5\\ 5&2&3&1\\ 1&3&4&2\end{pmatrix}  & \begin{pmatrix} 2&3&5&4\\ 3&4&1&5\\ 4&5&2&1\\ 5&1&3&2\\ 1&2&4&3\end{pmatrix}& \begin{pmatrix} 2&4&3&5\\ 5&3&1&4\\ 1&5&4&2\\ 3&2&5&1\\ 4&1&2&3\end{pmatrix} &\begin{pmatrix} 2&4&3&5\\ 4&5&1&3\\ 1&2&5&4\\ 5&3&2&1\\ 3&1&4&2\end{pmatrix}\\
\hline
\end{array}
此矩阵第i行,没有下标i,i=1,2,3,4,5.每一列每个下标必须出现一次.
因为任意一行都要循环轮换(这里的循环轮换意义,例如5421的循环轮换仅限于这样四种5421,4215,2154,1542;而不包括诸如4521等等),对应着4个$K_6$,那么矩阵任意两行各自取出一个循环轮换,总是不会有2个(或以上)下标在相同位置(若有,则意味着这2个字母搭配有重复).这个矩阵不妨定义为p=6,n=31的特征矩阵.通过观察p=6的特征矩阵,可以发现任意两行不能交换,任意两列不能交换.
特征矩阵在n个下标时,要符合如下三个条件:
1.此矩阵第i行,没有下标i,i=1,2,3,...,n.
2.每一列每个下标必须出现一次.
3.任意两行各自取出一个循环轮换,总是不会有2个(或以上)下标在相同位置.
显然每一行可以同时作同一方向的循环一格或继续再一格等等.如前面表格中,第一个矩阵的每一行同时左移一格,就变换为第2个矩阵.通过这样变换,总能使一个特征矩阵的第一行第一列为2.
当n-1=p(p-1)时,若能证明存在特征矩阵,即说明了$K_p\mid K_{p(p-1)+1}$.反之,不一定有$K_p\nmid K_{p(p-1)+1}$,除非每行必定对应着n个循环轮的$K_p$.





p=7,n=43,43个点为$M,A_i,B_i,C_i,D_i,E_i,F_i,G_i,i=1,2,3,4,5,6$,共43个$K_7$.
按用找特征矩阵的办法,当第一行为23456时分别按3,5在第2行的位置一共穷举了三次,发现p=7时,特征矩阵不存在.又按24365作为第一行,也不存在特征矩阵,都仅仅排到第三行就矛盾了.看来够古怪的,也许又能发现些什么了.
而第一行不为23456,24365的话,有$A_4^4-2=22$种需要尝试.隐隐觉得有办法否定掉p=7,而不是通过穷举.








以上修改了n次,特别p=4,n=16所花时间恐怕最多,不保证上面没错.


http://bbs.emath.ac.cn/thread-5555-1-1.html的3楼6楼的zhouguang推荐了http://www.ccrwest.org/cover.html
非常好用.如此知道了有$K_7\nmid{K_{43}}$,一般性地证明$K_P\nmid{K_{p(p-1)+1}},p\ge7$,--这个猜测错误,具体见http://www.ccrwest.org/cover/steiner.html

TOP

群论
211.png
2014-4-22 13:26

TOP

回复 11# 乌贼
现在只残留群、环、域之类的了,还有什么加群、整数环、……

TOP

返回列表 回复 发帖