[组合] 一道2014年某市一模试卷中的集合问题

longma

2014-1-12 17:18

kuing

对于 $[1,n]$ 中的某个整数 $k$，在 $\{1,2,\ldots,n\}$ 的所有非空子集中，以 $k$ 作为最大元素的集合个数等于集合 $\{1,2,\ldots,k-1\}$ 的子集个数，共 $2^{k-1}$ 个；以 $k$ 作为最小元素的集合个数等于集合 $\{k+1,k+2,\ldots,n\}$ 的子集个数，共 $2^{n-k}$ 个。
（注：当 $k=1$ 或 $n$ 时容易验证也符合此数目，故不必另作讨论）
故此在所有的 $G(B)$ 中，$k$ 共出现了 $2^{k-1}+2^{n-k}$ 次，因此，设所有 $G(B)$ 的和为 $S$，则
\begin{align*}
S&=\sum_{k=1}^nk(2^{k-1}+2^{n-k})\\
& =\sum_{k=1}^nk2^{k-1}+\sum_{k=1}^nk2^{n-k} \\
& =\sum_{k=1}^nk2^{k-1}+\sum_{k=1}^n(n+1-k)2^{n-(n+1-k)} \\
& =\sum_{k=1}^nk2^{k-1}+\sum_{k=1}^n(n+1-k)2^{k-1} \\
& =(n+1)\sum_{k=1}^n2^{k-1} \\
& =(n+1)(2^n-1),
\end{align*}
而 $G(B)$ 共有 $2^n-1$ 个，故所求的平均值就是 $n+1$。

goft

$设1\le i \le j \le n,且i+j=n+1,易知:i的最小值次数=j的最大值次数,i的最大值次数=j的最小值次数，故i+j的最值和平均值为n+1，故G（B）=n+1$

kuing

有道理

isee

$设1\le i \le j \le n,且i+j=n+1,易知:i的最小值次数=j的最大值次数,i的最大值次数=j的最小值次数，故i+j ...
goft 发表于 2014-1-12 18:50

   

建议楼主把中文与数学公式分开打。

LaTeX毕竟是老外的，一是代码优良；二是兼容各种浏览器~


＝＝＝＝＝＝＝＝＝＝＝＝

opera 看不完整，重新输入看一下：

设$1\le i \le j \le n,$且$i+j=n+1,$易知:$i$的最小值次数$=j$的最大值次数,$i$的最大值次数$=j$的最小值次数，
故$i+j$的最值和平均值为$n+1$，故$G(B)=n+1$. by goft

kuing

回复 5# isee

别要求太多了，少有写过程……

isee

回复  isee

别要求太多了，少有写过程……
kuing 发表于 2014-1-12 20:50

   

建议，非要求

其次，绝对不是因为我看完整代码而建议





磨刀不误砍柴工，如果，熟悉数学公式后，“移植”也方便，不论是纯LaTeX，还是LaTeX插件……

isee

对于 $[1,n]$ 中的某个整数 $k$，在 $\{1,2,\ldots,n\}$ 的所有非空子集中，以 $k$ 作为最大元素的集合个数 ...
kuing 发表于 2014-1-12 18:21

晕，直接看不懂首行

还有 “易知:$i$的最小值次数$=j$的最大值次数,$i$的最大值次数=$j$的最小值次数”

是不是与你首行同质？




这种高智商的题，果然玩不转~


~

kuing

回复 8# isee

看3#好了……

isee

回复 9# kuing

太费脑子了，到时真的，考试试卷上有了再说吧~

哈哈~

其妙

FAQ，觉得是竞赛题，居然没查到。
http://bbs.pep.com.cn/thread-409205-1-1.html
http://bbs.pep.com.cn/thread-426964-1-1.html
用合情推理，
令n=2，得到3.
令n=1，得到2，故n+1.

kuing

回复 11# 其妙
咦，我居然没注意这个FAQ？第二个链接我还回过呢，虽然是水贴……

其妙

回复 12# kuing
还有个什么类似的题目：关于“交替和”的，
也有变式：把“和”改成“乘积”的，找不到链接了……

爪机专用

回复 13# 其妙
旧版论坛找找看?

其妙

回复 14# 爪机专用
只有版主出马了！

kuing

回复 15# 其妙

噢，“交替和”在人教http://bbs.pep.com.cn/forum.php?mod=viewthread&tid=2375299

kuing

回复 15# 其妙

旧版论坛那个叫“容量”http://kkkkuingggg.haotui.com/viewthread.php?tid=1320