如果集合A的每个元素都是集合B的子集，则称A是B上的一个集族。
那么，给定一个集合S，S上的集族共有多少个呢？
Read the rest of this entry »

某班有30个学生，每个学生在班内都有相同个数的朋友。朋友是相互的。班里进行了一次测验，结果大家的成绩均不相同。一个学生被称为“好学生”，当且仅当他的朋友中有超过一半(不包括正好一半)的朋友成绩低于他。试问：班里最多有多少“好学生”?
Read the rest of this entry »

两个事物之间的关系称之为二元关系。在数学上，二元关系指的是这样的一个集合S，它的所有元素都为二元有序对。它反映的是有序对中第一个元素组成的集合与第二个元素组成的集合之间的关系。举个例子，集合S={<天秤座,libra>,<狮子座,leo>} 就表示了中文集合{天秤座,狮子座}与英文集合{libra,leo}之间的对应关系。
二元关系可以用集合表示，就像我们上面提到的。而除此之外，还可以用其他数学工具来描述它——矩阵和图。
矩阵的基本元素是数字及其所处的位置。直觉上，我们很自然的想到用它的下标来体现两个集合中的元素，用数字体现它们是否具有关系。这便得出了以下定义：
【定义】设集合A={x₁,x₂,…,x_m},B={y₁,y₂,…,y_n}，R为A,B之间的二元关系。称矩阵M(R)=(r_ij)_m×n为R的关系矩阵，其中

这样我们定义了一个映射，把集合R映射为一个矩阵M。如此定义，首先保证了R的集合表达式和R的关系矩阵是一一对应的。其次，这样的定义会带来很多好的性质。我们可以应用矩阵的语言把整个二元关系的理论重新叙述一遍： Read the rest of this entry »

当两个连续函数都趋于无穷时，我们常用洛必达法则来比较它们趋向无穷的快慢。函数的阶越高，它趋向无穷的速度就越快。在定义在正整数域上的函数中，n!趋向于正无穷的速度非常快，所以在算法设计中如果出现这样的时间复杂度就太糟糕了。logn趋向无穷的速度则非常慢。
今天你将看到一个增长速度比n!快的多的函数和一个比logn慢的多的函数，它们都源于一个函数–’Ackerman Function’。
并非一切的递归函数都有通项公式，Ackerman函数就是这么一个例子。它是一个双递归函数，有两个自变量(独立)。定义如下： 
 
Read the rest of this entry »

鸽笼原理英文是Pigeonhole Principle。但是它有很多中文名字，比如鸽巢原理，抽屉原理，鞋盒原理等等。它指的是如下一个定理：
如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。
我们来证明一下(这不是显然么！)。用反证法。假设每个盒子中都至多有一个物体，那么物体的总数至多是n。这与共有n+1个物体矛盾。所以定理成立。
别看这个定理很简单，用它却可以巧妙的解决很多问题，一个简单的例子就是13个人中至少有两个人的生日在同一个月份里。下面我们来考虑一些更具挑战性的例子：
1 证明给定m个整数a1,a2,…,am，存在整数k和l，0<=k<l<=m，使得a(k+!)+a(k+2)+…+a(l)能够被m整除。
证明：对于m个和 a1 , a1+a2 , a1+a2+a3 , … , a1+a2+…+am 。如果这些和当中的任意一个可以被m整除，问题便得证了。假设这m个和都不整除m，那么它们除以m的余数可能是1,2,…,m-1。由于存在m个数，而余数只有m-1种，所以必然有两个和除以m有相同的余数(鸽笼原理)。因此存在整数k和l，0<=k<l<=m，使得a1+a2+…+ak=bm+r , a1+a2+…+al=cm+r，两式相减，得到a(k+!)+a(k+2)+…+a(l)=(c-b)m，从而命题得证。
2 距离全国大学生数学建模竞赛还有11周时间。我决定每天至少做一道建模题，但为了不让自己陷入题海战略，给自己一些总结和思考的时间，我还是决定每周不能做题超过12道。证明存在连续的若干天，期间我恰好做了21道题。 Read the rest of this entry »