2002年 T1
1、在书架上放有编号为1 ，2 ，．．．，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。
例如：n = 3时：
原来位置为：1 2 3
放回去时只能为：3 1 2 或 2 3 1 这两种
问题：求当n = 7时满足以上条件的放法概率是__________
解释：
这里运用到了错排的思想，我在这里大致的讲解一下错排的公式
f(n)=(n-1)(f(n-1)+f(n-2))
其本质就是，在前n-1本书都已经完成错排的情况下，对于第n本书，
我们先简化地把它放在第一个位置，然后在对于第一本书进行分类讨论
（1）把第一本书放在第n位；（2）把第一本书放在2-n-1位
这两种情况，希望读者自行理解或查阅错排公式
因此这道题就是错排数/总数=1854/7!=103/280
2006年 T1
1、将 2006 个人分成若干不相交的子集，每个子集至少有 3 个人，并且：
(1) 在每个子集中，没有人认识该子集的所有人。
(2) 同一子集的任何 3 个人中，至少有 2 个人互不认识。
(3) 对同一子集中任何 2 个不相识的人，在该子集中恰好只有 1 个人认识这两个人。 则满足上述条件的子集最多能有多少个？
解释:
可以运用图论的思想,把每个人看做一个节点,认识的人就表示两个点相连,那么条件就变成
(1) 每个点集中,没有一个点连向其他所有点
(2) 每个点集中,任意3个点中,至少有两个点之间没有相连
(3) 每个点集中,任何两个没有被相连的点,都刚好只能通过一个点到达
那么我们就可以一个一个进行尝试,
从三角形,到四边形,最后可以发现五边形符合题意.
所以答案即为2006/5=401个
2007 T2
2、N 个人在操场里围成一圈，将这N 个人按顺时针方向从1 到N 编号，然后，从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N) ，例如，J(5)=3 ，J(10)=5 ，等等。则J(400)=______________。（提示：对 N=2m+r 进行分析，其中 0≤r<2m ）。
解释:
根据题目提示：把N写成2的m次方加上r
那么答案J(n)就是2*r+1
400=2^8+144,则答案是144*2+1=289
2008 T2
2、书架上有21本书，编号从1到21，从其中选4本，其中每两本的编号都不相邻的选法一共有______种。
解释:我们可以预先选出三本书作为四本书的间隔,所以之后就可以用C(4,18)来做=3060种
2012 T1
1、 本题中，我们约定布尔表达式只能包含p,q,r三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（?）三种布尔运算。如果无论p,q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p∨q)∨r和p∨(q∨r)等价，p∨?p和q∨?q也等价；而p∨q和p∧q不等价。那么，两两不等价的布尔表达式最多有_________个。
解释:
希望读者不能被题面的复杂所迷惑(就像我一样),
由于无论怎么取，两个式子的值恒等。p,q,r可以取0,1中的任意一个数，总共有2³=8种情况，每种情况对应一个不同的值，0或1。
因此每种情况都对应一个字符串，保证字符串的值不等，两两都不等价，至少有2^8种取法，因此答案就是256
2012 T2
2、对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集。那么，图3有_________个不同的独立集。
解释:
这道题可以用树形DP的思想来做
我们用f[i]表示以i为根的子树选i的方案数,而g[i]则是不选i的方案数
那么转移就是f[i]=g[左子树]*g[右子树], g[i]=(f[左子树]+g[左子树])*(f[右子树]+g[右子树])
最后答案就是f[根]+g[根]=5536
2016 T1
1、一个 1×8 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果 每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_________种填 涂方案。
解释：
你可以通过枚举出前几个的答案，2,3,5,8，发现是一个斐波那契数列
同时用可以用类似动态规划的方法，来推导出是斐波那契数列