一
在无限大的平面上有3匹马，求证不可能每两对马都可以通过奇数步走到对方（By 毒菇松）
反证+奇偶显然
二
在8*8的棋盘上A和B交替放黑马白马，每次放下不能使对方攻击到自己，判断谁胜谁负？（《奥赛经典·高二》）
由对称性知后手必胜
三
有一个n*n棋盘上（n>100），n-1个格子填1，其余填0，每次选择一个格子，将其减1，且同行同列其他数加1，是否能全部相等？（《奥赛经典·高二》）
考虑C=aij-akj+akm-aim，每次操作模3不变
取i,j为空行空列，考察akm=1，此时C=1(mod 3)，所以不可能
四
n*n的棋盘上每个方格都被染成m种颜色的一种，且不存在两行一样。证明一定可以对某列染成白色后任意两行不会一样（《奥赛经典·高二》）
反证，假设把任何一列染成白色后，都会有两行相同。
用v1…vn表示1-n行。如果把第i列染成白色且两行相同就连一条边，若有多个随便连一条。
那么可以得到n个点n条边的图。
由图论知识可知，必然存在一个环，记作vi1,vi2...vik
设vi1与vi2第j列颜色不同
由于对每列染成白色后，只连了一条边
故vi2,vi3...vik,vi1行在第j列上的小方格颜色相同。矛盾
五
有个人上楼梯，一次可以上a层或下b层
假设楼梯最高n层，若他可以从0层上到n层，并且返回到0层而不出边界
求n的最小值（《命题人讲座·初等数论》）
若a，b不互质，那么一阶楼梯相当于(a,b)阶，转化为互质
下证(a,b)=1时，答案为a+b-1
不妨设a>b>0
1）一方面，n=a+b-1时一定可以走到
考虑他在第i阶楼梯时
1.i+a>a+b-1 =>i>b-1，那么他一定可以下楼梯，在模b的同余类中不变
2.i-b<0 =>i<b=n-a+1，那么他一定可以上楼梯，在模b的同余类中相当于走了a%b层
所以他是可以始终不停上升的，根据裴蜀定理，他一定可以走到n，返回同理
2）另一方面，n<a+b-1一定不能走到（下面是书上证的，我太弱没想出来）
如果他可以从0走到n再从n走到0，那么他一定会经过a,2a,...,ba所代表b的同余类各一次（(a,b)=1）
考虑他返回的时候，当它走到b-1代表的模b的同余类时，设他的位置为 lb-1
此时，他不能上升（a+lb-1>=a+b-1>n）
以他会永远被禁锢在这个剩余类中，永远不可能回到0
Q.E.D.
因此最终的答案为a+b-(a,b)
六
整数1，2……，n的排列满足：每个数或者大于它前面所有树，或者小于前面所有数的方案数为an。求通项公式。（《小丛书·组合数学》）
n=1时a1=1.n=2时a2=2
对于n>2考虑第n个数插入1...n-1的排列中得an=1+a1+...+a[n-1]，错位相减得an=2^(n-1)
七
6个红球，3个蓝球，3个黄球，同色不相邻，求方案数（《小丛书·组合数学》）
若蓝球与黄球均不相邻，则红球与非红球交替放，2*C(6,3)*C(3,3)=40种
若蓝球与黄球有一个相邻，可以合并为一个“花球”，2!*(5!/(2!*2!*1!))=60种
所以答案为100种
八
AHOI2003特等奖学金
显然的差分约束题，但是最长长度应该如何计算呢？打表找规律？
其实个问题可以转化为问题五，慢慢想吧~~~
先放这么多，其他要么太数学化了要么还没懂要么我太懒要么种种原因。。。
以上选题基本上是xx章节第一道例题或者第一道练习题等等。。。原因嘛，，，本人太弱了。。。
感谢毒菇松