14. 有意思的是，在数学历史上，一些很简单的结论竟然几百年来都未曾发现。直到 1977 年， Paul Erdős 和 George Szekeres 才发现，除了两头的 1 以外，杨辉三角同一行内的任意两个数都有公因数。证明这个结论。
答案：只需要注意到， a 乘以一个比 b 小的数之后还能成为 b 的倍数，这说明 a 和 b 一定有公因数。不妨设 0 < i < j < n ，则 C(j, i) < C(n, i) 。我们的命题可以由下述关系直接推出。
C(n, j) · C(j, i)
= n! / (j! (n - j)!) · j! / (i! (j - i)!)
= n! / (i! (n - j)! (j - i)!)
= n! / (i! (n - i)!) · (n - i)! / ((j - i)! (n - j)!)
= C(n, i) · C(n-i, j-i)
这里有一个有趣的问题：在集合{1, 2, ..., n}中选取尽可能多的子集，使得任意两个子集的交集有且仅有一个元素。例如，当n=7时，选取{1,2,3,4}、{4,5,6,7}、{1,7}这3个集合可以满足条件。子集数还可以更大一点吗？最大是多少？给出一种构造，然后证明这个数目不可能更大了。
当n=7时，仅仅取3个子集实在是太弱了。一种最简单的办法就可以让子集数达到6，只需取{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}即可。再仔细观察，我们发现这个结果还可以进一步改进：我们还可以再往里面添加进一个子集{1}，使得这7个子集两两间仍然恰有一个公共元素。这下我们似乎不能再往里面添加任何新子集了。我们还可以做得更好吗？一个新的思路是在{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}里面加上{2,3,4,5,6,7}，这同样可以让子集数达到7个，可惜我们仍然无法再往里面添加新的子集了。经过若干次尝试后，我们逐渐开始确信，在集合{1, 2, ..., n}里面最多只能选出n个两两恰有一个公共元素的子集，并且构造方法无外乎上面两种。这一猜想不但与直觉相符，而且貌似也很好证明。你或许会从一些看似很直观的结论出发开始证明：“显然不可能有两个大小为1的子集”，“选取多个元素个数大于2的子集显然不划算”……但牛B就牛B在，偏偏就有这样一种子集数为n的取法，每个子集里都有不止两个元素，但仍然保证任意两个子集间恰有一个公共元素：
{1,2,3}、{1,4,5}、{1,6,7}、{2,4,7}、{3,4,6}、{3,5,7}、{2,5,6}
这一个例子对我们的猜想足以构成威胁：子集数为n真的已经到极限了吗？证明结论有那么容易吗？看来，情况貌似比我们想象中的要复杂得多。
一个完全图K_n是指一个有n个顶点的图，其中每两个点之间都有一条边相连。一个完全二分图是指这样一种图，图中的顶点分为两个点集L和R，L里的每个顶点都和R里的所有点相连。上图显示了一种把K_5划分为四个完全二分图的方法（分别用红蓝绿灰四种颜色来表示这四个子图）。你觉得，最少可以把完全图K_n划分成多少个完全二分图？给出一种划分方案，并证明这个数目已经不能再少了。
Stetson大学的一个非常可爱的MM（以后本Blog将简称她为Stetson MM）和我分享了一个很神奇的东西。她们正在做一个线性代数的课题研究，题目的大致意思是“用矩阵来构造分形图形”。Stetson MM叫我试着做下面这个实验：对于一个坐标点(x,y)，定义下面4个矩阵变换：
然后，初始时令(x,y)等于(0,0)，按照 T1 - 85%, T2 - 6%, T3 - 8%, T4 - 1% 的概率，随机选择一个变换对该点进行操作，生成的点就是新的(x,y)；把它画在图上后，再重复刚才的操作，并一直这样做下去。我心里觉得奇怪，这为什么会得到分形图形呢？于是我写了一个简单的Mathematica程序：
list = {{0, 0}};
last = {{0}, {0}};
For[i = 0, i < 50000, i++, r = Random[];
If[r < 0.85, last = {{0.83, 0.03}, {-0.03, 0.86}}.last + {{0}, {1.5}},
If[r < 0.91, last = {{0.2, -0.25}, {0.21, 0.23}}.last + {{0}, {1.5}},
If[r < 0.99, last = {{-0.15, 0.27}, {0.25, 0.26}}.last + {{0}, {0.45}},
last = {{0, 0}, {0, 0.17}}.last + {{0}, {0}}
]
]
];
list = Append[list, First[Transpose[last]]];
]
ListPlot[list, PlotStyle -> PointSize[0.002]]
程序运行的结果真的是令我大吃一惊：竟然真的是一个分形图形！！我不禁再次对数学产生了一种崇敬和畏惧感！！
Matrix67 |
2010-05-04 12:53 | 
