combinatorics – Zyymat: Mathematics

Label-connected graphs and the gossip problem

Nov 082012

问题的提出

\(n\) 个人, 每人有一个独家八卦消息. 任意人都可以打电话给别人, 交换双方目前已知的所有消息. 要想所有人都知道所有 \(n\) 条消息, 最少需要通多少次电话?

这个冠名为 gossip problem 的问题在不少的书上都有, 甚至小学的奥数, 但都不会有答案, 仿佛是一个很简单的问题. 其实不然! 单墫在数学竞赛研究教程 有一个习题, 采用数学归纳法证明了在 \(n\geqslant4\) 时, \(2n-4\) 次电话可以解决问题. 但这是平凡的, 不是困难所在.

这个问题还有另一个版本: 假设这 \(n\) 个人的联系方式不是打电话, 而是发邮件. 也就是说, 每个人都可以发邮件给随便挑选的他人, 把自己掌握的消息告知对方, 但对方了解的秘密不会泄漏. 那么, 要想每个人都知道所有 \(n\) 条消息, 最少需要发多少封邮件?

一些交待

我真正思考这个问题, 应该是06年的10-11月的一个晚上在北大南门街对面的上海城隍庙(已经消失2-3年), 遇上数学院一个朋友. 他在给学生讲奥数, 把这个题目发邮件的版本拿来问我. 在此之前是否看到过这问题, 不清楚, 但之后在奥数之家论坛有人问这个. 我在奥数之家回帖说明思路, 但没写详细证明. matrix67的博客引起我的注意后, 翻了一遍, 发现里面有打电话这种情况的一个证明, 并且交待此问题名 gossip problem. 我开始 Google, 于是回忆往事, 有了这个文章.

写这个文章的目的, 是谈论一个叫做 Label-connected graph 的事物, 这是我自己引进的第一个数学概念. 尽管在数学历史上, 已经有人在先, 但我是独立完成的. 当然, 也会交待清楚我以Label-connected graph为工具给出的解法, 以及收集到的别人的解答.

Brenda Baker 和 Robert Shostak 1972年的证明

这个证明转自matrix67.

显然, \(n=2\) 时只需要\(1\) 通电话, \(n=3\) 时必须要\(3\) 通电话. \(n=4\) 时, 可以让AB互相通话, CD互相通话, 此时每个人都知道了(包括自己的)两条消息;然后A和C通话, B和D通话, 从而使得每个人都获知另外两条自己还不知道的消息. 显然, 对于\(4\)个人的情况, \(4\)通电话已经是最少的了.
\(n>4\)的情况, 有一种算法可以保证在\(2n-4\)通电话内解决问题. 首先, 选出\(4\)个人作为消息汇总人. 其余每个人都选择一个汇总人并与之通话; 然后\(4\)个汇总人再用\(4\)通电话互相更新一下消息(用\(n=4\)的办法); 最后\(4\)个汇总人把电话再打回去, 实现所有消息全部共享.

下面我们证明, \(2n-4\) 已经是最少的了. 证明方法很多, 也都很复杂. 最常见的证明由Brenda Baker和Robert Shostak在1972年给出.

证明的关键在于这个引理: 如果我们可以在\(2n-5\)次电话以内达到要求, 则整个过程中绝对不会有人在电话中听到对方八卦自己的消息. 我们将用反证法来证明这一点. 首先找出最小的\(n\)使得\(n\)个人可以在\(2n-5\)次通话中传遍消息. 如果某个人\(G\) 听到了自己的消息, 表明整个过程中存在这么一条通话线路: \((G- G_1)(G_1-G_2)\dotsm(G_r-G)\). 现在, 我们把\(G\) 这个人去掉, 再重新安排一些通话线路, 使得剩下的\(n-1\)个人同样能在\(2(n-1)-5\) 次通话后传遍信息, 从而与\(n\)的最小性矛盾. 直接忽略上述”通话环”中的\((G – G_1)\)和\( (G_r-G )\)两条边.对于其他某个人\(P\)和\(G\)之间的通话\((P-G)\), 找出\((P-G)\)通电后最先出现的”通话环”中的其中一链(比如\((G_i-G_{i+1})\)). 在新方案中, 让 \(P\) 把电话打给\(G_i\). 这样, 原方案中任何一条由 \(P_1\) 带给 \(G\) 再带给\(P_2\) 的消息, 都由对应的 \(G_i\), \(G_j\) 以及他们之间的链条来完成, 即\((P_1-P_i)(G_i-G_{i+1})\dotsm(G_j-P_2)\). 新方案与原方案一样满足要求, 且通话次数减少了两次, 同样小于等于\(2n-5\).

每个人都不会听到自己的消息, 这可以推出一个很有趣的东西: 记一通电话的双方为A和B, 则要么A和B都还没打完, 要么这通电话对双方来说都是最后一通.原因很简单, 假如这通电话是A的最后一电, 这表明A和B都知道了所有的消息, 但B还要给别人打电话, 别人就会听到自己的消息. 类似地, 一通电话的双方要么都是第一次打, 要么都不是第一次打: 假如A的第一通电话是跟B打的, 但B之前已经和C通过话了, 那A的消息将永远与C的消息一起传递, 因此最终C听到A的消息时也会听到她自己的.

于是, 对于所有电话次数不超过\(2n-5\)的情况, \(n\)只能是偶数. 并且情况只可能是这样: 先两两配对拨打\(\frac n2\)通”处女电”, 然后中间打很多” 中介电话”, 最后再两个两个地打\(\frac n2\)个”最后一电”. 由于所有的”处女电”和”最后一电”加起来恰好有\(n\)通, 那么”中介电话”最多只能有\(n-5\)通. 又由于连通所有\(n\)个点至少要\(n-1\)条边, 可知这些”中介电话”构成了至少\(5\)个连通分量. 对于任何一个人来说, 在任何“最后一电”拨打之前, 她的消息最多只能够在其中两个连通分量内传递(她所在的连通分量和她“处女电”的对象所在的连通分量); 类似地, 所有“处女电”都打完了后, 每个人都只能收到两个连通分量内的消息(她自己的和“最后一电”的对象的). 对于一个特定的人\(G\)来说, 除去她自己, “处女电”的对象和“最后一电”的对象所在的连通分量, 至少还有两个连通分量, 里面的所有“中介电话”对她没有任何意义: 这些“中介电话”既不会把她的消息传出去, 也不会把别人的消息带给她.

设与G不相干的电话通数为\(c(G)\).

反过来, 又有多少通电话与\(G\)有关呢? 让我们继续把目光停留到G身上. 要想把她的消息传给所有人, 至少需要\(n-1\) 通电话; 要想让所有消息都传到她那里, 同样也得要n-1通电话. 某些电话可以同时起到这两种作用, 但有一个前提条件: 这些电话必需是她亲自打的. 否则, 她自己的消息将“捆绑”进那些将会传给她的消息里, 从而与引理矛盾. 假设她自己打了 \(v(G)\) 通电话, 那么总共有\(2n-2-v(G)\) 通电话负责传出她的消息并把别人的消息传给她. 由\(2n-5 \geqslant 2n-2-v(G)+c(G)\) 可知 \(v(G)\geqslant3+c(G) \geqslant 3\). 既然每个人都打了至少\(3\)电话, 这表明每个人都打过”中介电话”, 直接推出每个连通分量都有至少一条边. 前面说了, \(c(G)\)包含了至少两个连通分量中的所有边, 因此\(c(G)\geqslant2\). 因此, \(v(G)\geqslant5\). 每个人都打了至少\(5\)次电话? 这当然是不可能的, 这将导致总的电话数目比 \(2n\) 还大了.

What day of the week is it?

combinatorics No Responses »

Jul 312012

好多年前, 我看到过一个计算某年某月某日是星期几的公式, 一下子想不起来了, 只记得公式大概是什么结构, 有 “\(+\)”, 有 “\(-\)”, 等等. Google 了一下, 找出了这个公式, 现在写在这里, 做个档案.

公元 \(Y\) 年第 \(D\) 天是星期几, 即是

\[W=Y-1+\left[\frac{Y-1}4\right]-\left[\frac{Y-1}{100}\right]+\left[\frac{Y-1}{400}\right]+D\]

模 \(7\) 的余数. (这里 \(\left[x\right]\) 表示不超过 \(x\) 的最大整数)

比如, 你不记得今天是星期几了, 没关系, 拿起铅笔, 算一算, 很快就知道了: 今天是公元 \(2012\) 年 \(7\) 月 \(31\) 日, 那么 \(Y=2012, D=31+29+31+30+31+30+31.\) 算一下
\[2012-1+\left[\frac{2012-1}4\right]-\left[\frac{2012-1}{100}\right]+\left[\frac{2012-1}{400}\right]=2498, D=213,\]
因而
\[W=2498+213=2711\equiv2\pmod7,\]
于是 \(2012\) 年 \(7\) 月 \(31\) 日是星期二.

理解这个公式的关键在于: 每过一个平年, 把同一日期是星期几向后推 \(1\); 每过一个闰年, 把同一日期是星期几向后推 \(2\).

“星期制” 是把公元 \(1\) 年 \(1\) 月 \(1\) 日规定为星期一. 只要数一数从公元元年到这一年已经过了多少个平年, 多少个闰年, 就可算出从公元 \(1\) 年 \(1\) 月 \(1\) 日的星期一往后推了多少才到了这一年的元旦的星期几. 然后, 从这一年的元旦是星期几, 推算这一年的某一天是星期几, 只要算下过了多少天就行了.

具体说来, 公式中各部分的含义是:

\(Y-1\): 从公元元年开始已经过去的年数, 先按平年把元旦是星期几向后推 \(Y-1\);
\(\left[\dfrac{Y-1}4\right]\): 从公元元年开始已经过去了多少个 \(4\) 年, 按照”年份是 \(4\) 的倍数的一般都是闰年”的规定, 把元旦是星期几再向后推这么多;
\(\left[\dfrac{Y-1}{100}\right]\): 从公元元年开始已经过去了多少个 \(100\) 年, 按照“年份是 \(100\) 的倍数的一般不是闰年”的规定, 把向后多推的数减去;
\(\left[\dfrac{Y-1}{400}\right]\): 已经过去了多少个 \(400\) 年, 按照”年份是 \(400\) 的倍数的是闰年”的规定, 把多减去的数补上;
\(D\): 这一天是这一年的第几天.

于是, \(W\) 就是从公元元年元旦是星期一到这一天, 需要把星期几向后推的总数. 因之, \(W\) 模 \(7\) 的余数是几, 这一天就星期几.

Chessboard,Knight’s tour and Hamiltonian

combinatorics No Responses »

Jun 072012

有这么一个问题: 国际象棋中马按照“马跳日”的规则行走. 一匹马从下图标记为 \(A\) 的点出发, 能否不重复不遗漏的走过每个点, 最后停在标记为 \(33\) 的点?

Chessboard and Knight’s tour problem

答案是: 不可以! 但是, 最后可以停在标记为 \(B\) 的点, 按照这个顺序行走, 就可以

\begin{equation}A\rightarrow1\rightarrow2\rightarrow\cdots\rightarrow43\rightarrow B.\end{equation}

这是一个 \(5\times9\) 的棋盘. 可以考虑从任意一点出发, 不重复不遗漏的走过每个点, 最后停在某个指定的点. 这个最后的落脚点当然也可以是出发点. 显然的, 这个事情, 有时候可以实现, 有时候令人遗憾. 赋予处于第 \(i\) 行第 \(j\) 列的点一个数 \(i+j\), 那么, 有下述性质：

当马从一个点跳到另一个点的时候, 这两个点所赋予的数, 奇偶性是不同的.

注意, 对于这个 \(5\times9\) 的棋盘, 赋予的 \(45\) 个数, 有 \(23\) 个偶数, \(22\) 个奇数. 于是, 只有从赋予的数是偶数的点出发, 才有成功的可能. 那么, 是不是随意指定两个赋予的数是偶数的点, 马就可以从一个出发, 不重复不遗漏的走过每个点, 最后停在另一个? 这个比较困难. 事实上, 这个问题, 和图论（graph theory）中的哈密尔顿道路（Hamiltonian path）或哈密尔顿圈（ Hamiltonian cycle）有关. 不过, 把 \((1)\) 稍作修改, 就可证明: 马从任意一个赋予的数是偶数的点出发, 不重复不遗漏的走过每个点,最后停在某个赋予的数是偶数的点.

怎么证明 \(4\times4\) 或 \(5\times5\) 的棋盘, 不存在哈密尔顿道路? 看下图, 从标记为 \(A\) 的点出发, 只能落在标记为 \(B\) 的点:

Chessboard and Knight’s tour

很自然的一般性问题是: 考虑 \(m\times n\)\(（m\leq n)\) 的长方形棋盘.

A trivial proof of Ramsey’s theorem

combinatorics No Responses »

Jun 072012

Ramsey’s theorem 给定正整数 \(c(\geqslant2), m(\geqslant3)\), 则存在正整数 \(N\), 当 \(n\geqslant N\) 时, 任意 \(c\) 色完全图 \(K_n\)必有单色完全子图 \(K_m\).

这两天读 terence tao的文章” What is good mathematics?”, 里面提到了这个定理. 当然, 很早以前我就学过这个组合中有名的结果, 那时我是一个高中生. 李炯生的书, “数学竞赛中的图论方法”(中国科学技术大学出版社,1992年)有一章是谈这个定理的, 还有一章谈应用. 这书证明了两色的情况, 用的归纳法(Mathematical induction), 和一般的书籍没有不同. 比如, 在这里可以找到一个这样的证明. 李炯生的书给出的实际上就是这个证明的前半部分.

我的证明严重依靠抽屉原理(Pigeonhole principle)(这也难怪, Ramsey’s theorem 本身就是Pigeonhole principle 的推广)不用归纳法. 当然, 我也想不出什么了不起的办法, 说来也只不过是世上任意 \(6\) 人中, 必有\( 3\) 人互相认识或互不认识这个广为人知的结果的流传最广的证明的发扬光大而已:

下面对 \(8\)个人证明必有 \(3\) 人互相认识或互不认识.

\( 2\) 种颜色为\( a,b\). 记这 \( 8\)个人是 \(v_1, v_2, \dotsc, v_8\). 可以认为边 \(v_1v_2, v_1v_3, v_1v_4, v_1v_5 \) 颜色相同, 是 \(c_1, c_1\) 为 \( a\) 或 \(b\) . 边 \(v_2v_3, v_2v_4, v_2v_5 \) 必有两条颜色相同, \(v_2v_3, v_2v_4\) 颜色都是 \(c_2, c_2\) 为 \(a\) 或 \(b\). 下面再看边 \(v_3v_4\) 的颜色, 是 \(c_3, c_3\) 为 \(a\) 或\(b\).

注意 \(c_1, c_2, c_3\) 必有两个相同. 于是不管怎样, \( 2\) 色 \(K_8\)都有单色三角形.

一般情况下的证明也差不多.

\(c\) 种颜色\(t_1, t_2,\dotsc, t_c\). 我们来证明当 \( n\geqslant c^{cm}\) 时, 任意 \(c\) 色完全图 \( K_n\) 必有单色完全子图 \(K_m\).

事实上, 任取顶点 \( v_1\), 以\(v_1\) 为一端点的边至少有 \(c^{mc- 1}\)条是同色的. 设这个颜色是 \( c_1, c_1 \)为 \( t_1, t_2,\dotsc, t_c\) 之一. 只要考虑这 \(c^{mc – 1}\)条边及这些边的 \(c^{mc-1}+1\)个顶点就够了.

设 \(v_1v_2\)是这 \(c^{mc- 1}\)条边中的任意一条. 同理, 以\(v_2\) 为一端点的边至少有 \( c^{mc- 2}\)条是同色的, 设这个颜色是 \(c_2, c_2\) 为\(t_1, t_2,\dotsc, t_c\)之一. 依次类推, 最后得到以\(v_{mc}\) 为一端点的边至少有 \(1\)条边, 把这条边颜色记为 \(c_{mc}, c_{mc}\) 为 \(t_1, t_2,\dotsc, t_c \) 之一.

请注意: \(c_1, c_2, \dotsc, c_{mc}\) 中至少有 \( m\) 个相同, 不妨设为 \( c_{i_1}, c_{i_2}, \dotsc, c_{i_m}\) . 考虑 \(v_{i_1}, v_{i_2}, \dotsc, v_{i_m}\), 显然存在单色 \(K_m\).

[本文完成于 2009年 8月 19 日]