从1~n的n个数中选出一些数，使得两两之间不能整除。问最多能选出多少。
答：每个数可以写成a*2k的形式，其中a是奇数。那么如果两个数的a相同，就能整除。因此必定每个数的a不同，最多的数就是1~n的奇数个数，即n/2向上取整。一种方案是取n/2至n的数。
1~n的数打乱顺序，每次可以交换任意两个数，问使之有序至少要多少次交换？
答：最开始做的时候只是从左向右扫描数组，如果哪个位置上的数字不对，则与有正确数字的位置交换。总觉得不放心，又想了下。其实这些数字构成了一些环（已经在正确位置的数字也可以当成一个指向自身的环）。
图中圆圈中的数字表示数组位置，旁边的数字表示现在此位置的数字。那么箭头指向了数字应该去到的正确位置。当然环不一定是1-->2-->3这样，不过这无关紧要，位置重新编号一下即可。
可以看出（或者猜），一个n个点的环要变成n个点，需要n-1次交换。比如1,2位置的数字交换后，变成下面这样
其实也可以不沿箭头交换，比如交换1,4位置的数字，如下
根据我们的假设，总共需要1+2*(3-1)=5次交换，与按箭头交换的次数（6-1）是一样的。
一条杆上有n只随机朝向运动的蚂蚁，两只蚂蚁碰面后则掉头走，问碰面次数的期望值。
这题倒不是说难，只是原来推导复杂了。。实际上也就是求2n种情况中总的碰面次数啦。碰面后往回走可以等价为继续沿原方向走这个大家都知道吧？把向东走用1表示，向西用-1，也就是求(1, -1)的有序对有多少。用f(n)表示n个数字的总数。当第一个数是-1时，为f(n-1)。当第一个数是1时，为f(n-1)加上这个1与后面的-1形成的对数。也就是n-1个数的所有情况中有多少-1？答案当然是(n-1)*2n-1/2，因为1和-1的数量相等嘛。所以：
f(n)=(n-1)*2n-2 + 2*f(n-1) f(1)=0
这个还是很好求的，展开一下就知道了。f(n)=n*(n-1)*2n-3.
那么期望是f(n)/2n=n*(n-1)/8. 这个结果倒是挺简洁的。
update：看了题解发现这个还是复杂了。。。由于碰面后往回走可以等价为继续沿原方向走，那么任意一对蚂蚁是否会碰面是与其他蚂蚁无关的，只与它们的方向有关。4种可能情况中，只有相向走会碰面，也就是概率1/4。乘以蚂蚁对数C(n,2)即可。难怪结果很简洁。。