趣题:不等式背后的直观意义

有时,为了说明某个式子始终成立,我们会为它构造一个情境。例如,为了说明

C(m, 0) · C(w, r) + C(m, 1) · C(w, r – 1) + … + C(m, r) · C(w, 0) = C(m + w, r)

始终成立,只需要注意到,等号的左边和右边计算的都是同一个东西:假如一个班上有 m 个男生 w 个女生,从中选出 r 个人有多少种方案。等号左边的计算方式是,分别计算 0 男 r 女、 1 男 r – 1 女、 2 男 r – 2 女等 r + 1 种情况的方案数,然后把它们加起来。等号右边则是直接算出了从这 m + w 个人中选出 r 个人的方案数。两种算法所得的答案应该是相等的。

现在,请你构造一个情境,来说明不等式

(1 – pm)n + (1 – qn)m ≥ 1

总成立,其中 m 、 n 是任意正整数, p 、 q 是任意正实数,并且满足 p + q ≤ 1 。

Read more…

整数分拆中的一个出人意料的结论

把 6 分成一个或多个正整数之和,本质不同的方案只有以下 11 种:

分拆方案 含有多少种不同的数
6 1
5 + 1 2
4 + 2 2
4 + 1 + 1 2
3 + 3 1
3 + 2 + 1 3
3 + 1 + 1 + 1 2
2 + 2 + 2 1
2 + 2 + 1 + 1 2
2 + 1 + 1 + 1 + 1 2
1 + 1 + 1 + 1 + 1 + 1 1

其中,每一行右边的那个数表示,该分拆方案中含有多少种不同的数。把右列的所有数全部加起来,结果是 19 。神奇的是,如果你数一数所有分拆方案中 1 出现的总次数,你会发现结果也是 19 。

这并不是巧合。事实上,对于任意一个正整数来说,各个分拆方案中不同的数的个数之和,一定都等于所有方案中 1 出现的总次数。这是为什么呢?这个结论还有一个比较直接的推广,你能想到吗?

Read more…

趣题:构造点集使得每条直线上的点都一样多

我们很容易在平面内放置很多点,使得任意两点确定的直线都只经过这两个点——你需要做的,仅仅是让任意三点都不共线就行了。那么,能否在平面内放置若干个点,使得任意两点确定的直线总是恰好经过三个点呢?更一般地,对于任意正整数 n > 2 ,能否在平面内放置若干个点,使得任意两点确定的直线总是恰好经过 n 个点呢?当然,我们要排除掉所有点都共线这种平凡的情况。

记得我很小的时候就想过这个问题。小时候有一种经典的智力题,大致就是叫你把多少多少棵树种成多少多少行,使得每行都有多少多少棵树。比方说,如何把 9 棵树种成 10 行,使得每行都有 3 棵树?答案如下图所示。但请注意,其实图中还有不少直线上只有 2 棵树,比如那条蓝色的虚线。

当时,我就曾经想过,如果树苗足够多,能否让每条可能的直线上都种有 3 棵树呢?于是,我没事儿就来尝试一番,但每一次都以失败告终。后来我才知道,这是不可能的。根据 Sylvester–Gallai 定理,在任意一个有限点集中,一定有一条直线恰好只经过两个点,除非所有的点都是共线的。这个定理有一个非常漂亮的证明,这里不得不提。假设存在某个点集,满足任意两点确定的直线上都存在其他的点。画出所有可能的直线,作出每一个点到每一条直线的垂线段,然后找出所有这些垂线段中最短的一条。不妨假设这条最短的垂线段是点 P 到某条直线 l 的垂线段,垂足点记作 H 。由假设, l 上至少有三个点,因此至少有两个点分布在垂足 H 的同一侧(允许和垂足重合)。不妨把这两个点记作 R 、 Q ,如下图所示。由于我们画出了所有可能的直线,因此 P 、 R 两点之间也有一条直线;此时, Q 到 PR 的垂线段就是更短的垂线段,于是产生矛盾。要想避免这样的矛盾,唯一的方法就是,所有的垂线段长度都为 0 ,换句话说我们根本作不出所谓的垂线段。这也就是所有点全都共线的情况。

我们刚才证明了,在一个点集中,只经过两点的直线一定存在,除非所有点全都共线;因此,当 n > 2 时,我们自然就无法让每条可能的直线上都有 n 个点,除非所有点全都共线。

Read more…