|
|
战巡
Posted 2014-1-17 03:17
回复 1# 乌贼
不算很难吧.......
$f_2(4)$的话，$1,2$不能放一起，$2,4$不能放一起，就是说$1,4$必然在一起，$2$放另一边，$3$爱放哪放哪，于是
\[f_2(4)=2·2=4\]
$f_2(5)$差不多，$3,5$都可以随便乱放
\[f_2(5)=2·2·2=8\]
第二问求$f_3(2013)$，首先把$U=\{1,2,3,...,2013\}$中所有$3$的倍数踢出来，组成一个新集合$B$，剩下的元素互不影响，是可以随便乱摆的，总共有$1342$个
这些元素先摆好，就有$2^{1342}$种搞法
然后考虑$3$的倍数，首先考虑第一批：$x\in B \& \frac{x}{3}\notin B$，这时$\frac{x}{3}$已经在前面的1342个数里，而且摆好了，于是这批$x$都只有一种摆法，那就是避开$\frac{x}{3}$的那一组
接下来考虑$B$中剩下的元素，这个元素组成集合$C$，第二批考虑：$x\in C \& \frac{x}{3}\notin C$，结果和前面一样，每个元素只有一种摆法
以此类推，直到所有元素被放好
所以最后得到
\[f_3(2013)=2^{1342}\]
最后一问完全可以从上面推广
可知
\[f_k(pk+q)=2^{p(k-1)+q}\]
而又知道，当一个集合$A$满足条件时，它的补集$\complement_UA$也满足条件，这两个两两对应，每一组的总和都是$\frac{n(n+1)}{2}$，全部的$2^{p(k-1)+q}$里面有$2^{p(k-1)+q-1}$组这样的东西
总和为
\[n(n+1)·2^{p(k-1)+q-2}\] |
|
kuing
Posted 2014-1-17 00:31
