Power, Simplicity and Beauty
Combinatorics
问题的提出 \(n\) 个人, 每人有一个独家八卦消息. 任意人都可以打电话给别人, 交换双方目前已知的所有消息. 要想所有人都知道所有 \(n\) 条消息, 最少需要通多少次电话? 这个冠名为 gossip problem 的问题在不少的书上都有, 甚至小学的奥数, 但都不会有答案, 仿佛是一个很简单的问题. 其实不然! 单墫在数学竞赛研究教程 有一个习题, 采用数学归纳法证明了在 \(n\geqslant4\) 时, \(2n-4\) 次电话可以解决问题. 但这是平凡的, 不是困难所在. 这个问题还有另一个版本: 假设这 \(n\) 个人的联系方式不是打电话, 而是发邮件. 也就是说, 每个人都可以发邮件给随便挑选的他人, …
Label-connected graphs and the gossip problem Read More好多年前, 我看到过一个计算某年某月某日是星期几的公式, 一下子想不起来了, 只记得公式大概是什么结构, 有 “\(+\)”, 有 “\(-\)”, 等等. 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\) 的最大整数) 比如, …
What day of the week is it? Read More有这么一个问题: 国际象棋中马按照“马跳日”的规则行走. 一匹马从下图标记为 \(A\) 的点出发, 能否不重复不遗漏的走过每个点, 最后停在标记为 \(33\) 的点? 答案是: 不可以! 但是, 最后可以停在标记为 \(B\) 的点, 按照这个顺序行走, 就可以 \begin{equation}A\rightarrow1\rightarrow2\rightarrow\cdots\rightarrow43\rightarrow B.\end{equation} 这是一个 \(5\times9\) 的棋盘. 可以考虑从任意一点出发, 不重复不遗漏的走过每个点, 最后停在某个指定的点. 这个最后的落脚点当然也可以是出发点. 显然的, 这个事情, 有时候可以实现, 有时候令人遗憾. …
Chessboard,Knight’s tour and Hamiltonian Read MoreRamsey’s theorem 给定正整数 \(c(\geqslant2), m(\geqslant3)\), 则存在正整数 \(N\), 当 \(n\geqslant N\) 时, 任意 \(c\) 色完全图 \(K_n\)必有单色完全子图 \(K_m\). 这两天读 terence tao的文章” What is good mathematics?”, 里面提到了这个定理. 当然, 很早以前我就学过这个组合中有名的结果, 那时我是一个高中生. 李炯生的书, “数学竞赛中的图论方法”(中国科学技术大学出版社,1992年)有一章是谈这个定理的, 还有一章谈应用. 这书证明了两色的情况, …
A trivial proof of Ramsey’s theorem Read More