免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 转人教之集合个数

转自:http://bbs.pep.com.cn/forum.php? ... &extra=page%3D1

题目:已知全集 $U=\{1,2,3,\ldots,n\}$,集合 $A$ 满足
① $A\subseteq U$;
② 若 $x\in A$,则 $kx\notin A$;
③ 若 $x\in\complement_UA$,则 $kx\notin\complement_UA$(其中 $k$, $n\in\mbb N^+$)。
$f_k(n)$ 表示满足条件的集合 $A$ 的个数。
(1)求 $f_2(4)$, $f_2(5)$;
(2)求 $f_3(2013)$;
(3)记集合 $A$ 的所有元素之和为集合 $A$ 的“和”,当 $n=pk+q$ 时(其中 $p$, $q\in\mbb N$, $0\leqslant q<k$),求所有集合 $A$ 的“和”的和。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

高一就玩这么难
只懂第一问

TOP

看上去是这道题(http://kuing.orzweb.net/viewthread.php?tid=336)的推广形式……

PS、人教论坛的图片可以直接链接过来,不必重新上传。

TOP

本帖最后由 乌贼 于 2014-1-17 01:20 编辑

回复 3# kuing
我不会链接,会了,谢谢
是推广题

TOP

回复 4# 乌贼

点击图片,如果图弹出来,点击右上方第一个东东“在新窗口打开”,然后你会看到打开的图片,地址栏上是图片的地址,将它复制,然后这边发贴时再插入图片(操作是点击 “图片”-“网络图片”,粘贴地址,确定)。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

本帖最后由 战巡 于 2014-1-17 03:19 编辑

回复 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}\]

TOP

回复 6# 战巡
很强的逻辑推理

TOP

话说我隐约记得有人说这道是以前的竞赛题。。。

TOP

反正你们是通吃型的~咯~

TOP

回复 9# isee
这种配对法,倒是有好几道类似的竞赛题是这种方法。

TOP

题目没有了

TOP

回复 11# 乌贼

人教那边贴子2#的图自己变了,这里也跟着变了,只能说那个图床太坑爹……

TOP

回复 12# kuing
那以后不用这种方式转贴了。

TOP

回复 13# 乌贼

那也不必如此,主要还是看情况吧。
如果那边的图是上传到人教论坛上的,那是肯定不会自己变的,可以放心粘过来。
这次主要是因为那边2#的图用的是外链而且那图床不稳定,所以才这样。

PS、我将1#编辑了一下,将题目重新输入了一遍。

TOP

回复 14# kuing
谢谢

TOP

返回列表 回复 发帖