在集合 {1, 2, ..., n} 中选出尽可能多的子集，使得每个子集所含的元素个数都是奇数，但是任意两个子集的交集都含有偶数个元素。那么，我们最多能够选出多少个这样的子集来？
容易看出，我们至少可以选出 n 个子集。例如，当 n = 4 时， {1} 、 {2} 、 {3} 、 {4} 就满足要求。我们还能选出更多的子集来吗？简单地尝试后，你会觉得似乎不行。不过，这却并不是显然的，因为存在一些不那么平凡的方案，也能让子集的数量达到 n ，例如 {1, 2, 3} 、 {1, 2, 4} 、 {1, 3, 4} 、 {2, 3, 4} 这 4 个子集也是满足要求的。看来，证明最多只能选出 n 个子集，好像并不那么容易。
今天的趣题来自 UyHiP 今年十月的趣题。
许多快递公司都依据物件的长、宽、高三边之和来收费，一些航空公司也要求托运行李的三边长相加不能超过某个限制。那么是否有人想过，有没有可能把一个三边之和较大的盒子装进一个三边之和较小的盒子里，从而骗取更低的费用呢？有人会说，恐怕不行吧，长宽高之和更大的盒子体积不也应该更大一些吗？不见得。比方说，盒子 A 的长宽高分别是 10 、 10 、 10 ，盒子 B 的长宽高分别是 9 、 9 、 12.1 。盒子 B 的三边长之和显然比盒子 A 要大，但体积只有 980.1 ，比前者要小近 20 个单位。那么，为什么就不能把盒子 B 沿斜线方向塞进盒子 A 呢？有人会敏锐地发现，在上面的例子中，盒子 A 的体对角线长为 17.3205 ，但盒子B的对角线长度达到 17.5616 ，显然无法完全放进盒子 A 里。不过且慢，我也能举出这样的例子，三边和更大的盒子其体积和对角线都比小的盒子的要小。盒子 A 的长宽高分别为 10 、 10 、 20 ，盒子 B 的长宽高分别为 7.1 、 16.5 、 16.5 。盒子 B 的长宽高之和比盒子 A 大，体积为 1932.98 ，对角线长度比前者小大约 0.1 。看来，为了解决这个问题，我们还需要从一些更巧妙的方面入手。
假设 X 、 Y 是两个有限集合，f:X→Y 和 g:Y→X 是两个函数。求证：复合函数 g∘f 和 f∘g 拥有相同数量的不动点（也就是说 g(f(x)) = x 和 f(g(y)) = y 的解的个数相同）。
下面先提供一个“正常”的解法。观察函数 g∘f 的不动点，可以看出它有以下两个性质：首先，如果某个 x 是 g∘f 的不动点，即 x = g(f(x)) ，那么 f(x) = f(g(f(x)))，这就说明 f(x) 是 f∘g 的一个不动点；另外，如果 x1 和 x2 是 X 中两个不同的不动点，则函数 f 不可能把它们映射到 Y 中的同一个元素，否则 g 没办法把它分别还原成 x1 和 x2 。结合上面两点可以看出， f∘g 中的不动点至少和 g∘f 的一样多。
同理，考察 f∘g 的不动点，可知 g∘f 的不动点至少和 f∘g 的一样多。这就说明了 g∘f 和 f∘g 拥有相同数量的不动点。
在准备前一篇日志时，我查阅了很多经典的悖论。我发现，虽说数学悖论大多是一些让人越想越糊涂的逻辑思维游戏，但也有不少悖论来自于实实在在的数学问题。在缺乏现代数学工具的年代，这些反直觉的结论和看似不可调和的矛盾让数学家们百思不得其解，那些最难解决的悖论甚至为数学新分支的开创带来了足够的动机。不太为人熟知的 Cramer 悖论就是一个漂亮的例子。
在描述 Cramer 悖论之前，让我们先来考虑一个简单的情况。两条直线交于一点。反过来，过一点可以做两条不同的直线。事实上，过一点可以做无数条直线。确定一条直线需要两个点才够。一切都很正常。
现在，考虑平面上的两条三次曲线。由于将两个二元三次方程联立求解，最多可以得到 9 组不同的解，因此两条三次曲线最多有 9 个交点。另外，三次曲线的一般形式为
x^3 + a·x^2·y + b·x·y^2 + c·y^3 + d·x^2 + e·x·y + f·y^2 + g·x + h·y + i = 0
这里面一共有 9 个未知系数。代入曲线上的 9 组不同的 (x, y) ，我们就能得出 9 个方程，解出这 9 个未知系数，恢复出这个三次曲线的原貌。也就是说，平面上的 9 个点唯一地确定了一个三次曲线。这次貌似就出问题了： “两条三次曲线交于 9 个点” 和 “ 9 个点唯一地确定一条三次曲线” 怎么可能同时成立呢？既然这 9 个点是两条三次曲线所共有的，那它们究竟会“唯一地”确定出哪条曲线呢？在没有线性代数的年代，这是一个令人匪夷所思的问题。
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 |
2011-11-16 13:11 | 
