找回密码
 欢迎注册
查看: 83113|回复: 135

[擂台] 自然数前段的均衡样本

[复制链接]
发表于 2010-4-21 22:19:39 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
Sn:={1, 2, 3, …, n}称为自然数的前段,它的总体平均值a=(n+1)/2. 如果Sn的某个真子集的均值也是a,  就称为Sn的一个均衡样本。
一个均衡样本若包含更小的均衡样本,即为可约均衡样本,否则为不可约均衡样本。
精华

可约均衡样本可以划分为若干个更小的均衡样本,迭代划分,直至划分为若干个不可约均衡样本。
将 Sn 划分为若干个不可约均衡样本,称为 Sn 的一个极大划分。
问:Sn有多少个
1)  k元均衡样本
2)  k元不可约均衡样本
3)  不可约均衡样本
4)  极大划分(将{1, 2, 3, …, n}划分成若干个不可约均衡样本)
前两问是中间结果,我们的重点在于后两问。

例1:{1,2,3,4,5,6}有3个不可约均衡样本:{1,6},{2,5},{3,4},它们构成`S_6`的唯一一个极大划分{{1,6},{2,5},{3,4}}.

例2:{1,2,3,4,5,6,7}有6个不可约均衡样本:{4},{1,7},{2,6},{3,5},{1,5,6},{2,3,7},和2个极大划分:
        第1个极大划分是{{4},{1,7},{2,6},{3,5}},第2个极大划分是{{4},{1,5,6},{2,3,7}}.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-22 08:16:22 | 显示全部楼层
这道题跟/thread-2251-1-1.html很相似

以下是第3)和第4)问的n=1~10的数据。其中极大划分模型指极大划分之子集长度的提取。极大划分和极大划分模型在表中皆直观表达为加号连接。
当 n 为奇数时,中数(n+1)/2总是唯一的1元样本,极大划分中总是少不了{(n+1)/2}, 所以下表把这个不变东东给省略了。
n极大划分数既约样本数既约均衡样本
(n为大奇数时省略中数)
极大划分模型极大划分
(n为大奇数时省略中数)
111{1}1{1}
211{1,2}2{1,2}
312{1,3}1+2{1,3}
412{1,4},{2,3}2+2{1,4}+{2,3}
513{1,5},{2,4}1+2+2{1,5}+{2,4}
613{1,6},{2,5},{3,4}2+2+2{1,6}+{2,5}+{3,4}
726{1,7},{2,6},{3,5}1+2+2+2{1,7}+{2,6}+{3,5}
{1,5,6},{2,3,7}1+3+3{1,5,6}+{2,3,7}
826{1,8},{2,7},{3,6},{4,5}2+2+2+2{1,8}+{2,7}+{3,6}+{4,5}
{1,4,6,7},{2,3,5,8}4+4{1,4,6,7}+{2,3,5,8}
9411{1,9},{2,8},{3,7},{4,6}1+2+2+2+2{1,9}+{2,8}+{3,7}+{4,6}
{2,4,9},{1,6,8},{2,6,7},{3,4,8}1+2+3+3{3,7}+{2,4,9}+{1,6,8}
{1,4,7,8,},{2,3,6,9}{1,9}+{2,6,7}+{3,4,8}
1+4+4{1,4,7,8,}+{2,3,6,9}
10513{1,10},{2,9},{3,8},{4,7},{5,6}2+2+2+2+2{1,10}+{2,9}+{3,8}+{4,7}+{5,6}
{1,4,8,9},{1,5,7,9},{1,6,7,8}2+4+4{3,8}+{2,4,6,10}+{1,5,7,9}
{2,3,7,10},{2,4,6,10},{2,5,7,8}{5,6}+{2,3,7,10}+{1,4,8,9}
{3,4,6,9},{3,4,5,10}{1,10}+{2,5,7,8}+{3,4,6,9}
{2,9}+{3,4,5,10}+{1,6,7,8}

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-22 08:32:26 | 显示全部楼层
这个题目有点深度。感觉像是个组合难题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-4-22 08:54:14 | 显示全部楼层

第3)、4)问,n=11、12的数据

n极大划分数既约样本数既约均衡样本(n为大奇数时省略中数)极大划分模型极大划分(n为大奇数时省略中数)
111420{1,11},{2,10},{3,9},{4,8},{5,7}1+2+2+2+2+2{1,11}+{2,10}+{3,9}+{4,8}+{5,7}
{1,7,10},{1,8,9},{2,5,11},{2,7,9}1+2+2+3+3{1,11}+{2,10}+{3,7,8}+{4,5,9}
{3,4,11},{3,5,10},{3,7,8},{4,5,9}{2,10}+{5,7}+{1,8,9}+{3,4,11}
{1,4,9,10},{1,5,8,10},{2,3,8,11}{1,11}+{4,8}+{2,7,9}+{3,5,10}
{2,4,7,11},{2,5,8,9},{3,4,7,10}{3,9}+{4,8}+{1,7,10}+{2,5,11}
1+3+3+4{1,7,10}+{3,4,11}+{2,5,8,9}
{1,7,10}+{4,5,9}+{2,3,8,11}
{2,7,9}+{3,4,11}+{1,5,8,10}
{1,8,9}+{2,5,11}+{3,4,7,10}
{3,7,8}+{2,5,11}+{1,4,9,10}
{1,8,9}+{3,5,10}+{2,4,7,11}
1+2+4+4{1,11}+{2,5,8,9}+{3,4,7,10}
{5,7}+{1,4,9,10}+{2,3,8,11}
{3,9}+{1,5,8,10}+{2,4,7,11}
121926{1,12},{2,11},{3,10},{4,9},{5,8},{6,7}2+2+2+2+2+2{1,12}+{2,11}+{3,10}+{4,9}+{5,8}+{6,7}
{1,4,10,11},{1,5,9,11},{1,6,8,11}2+2+4+4{1,12}+{2,11}+{3,6,8,9}+{4,5,7,10}
{1,6,9,10},{1,7,8,10},{2,3,9,12}{1,12}+{2,7,8,9}+{3,10}+{4,5,6,11}
{2,4,8,12},{2,5,7,12},{2,5,9,10}{1,12}+{2,6,8,10}+{3,5,7,11}+{4,9}
{2,6,8,10},{2,7,8,9},{3,4,7,12}{1,12}+{2,10,5,9}+{3,4,8,11}+{6,7}
{3,5,6,12},{3,4,8,11},{3,5,7,11}{2,11}+{1,6,9,10}+{5,8}+{3,4,7,12}
{3,6,8,9},{4,5,6,11},{4,5,7,10}{2,11}+{1,7,8,10}+{4,9}+{3,5,6,12}
{1,3,7,8,9,11},{2,4,5,6,10,12}{3,10}+{1,5,9,11}+{6,7}+{2,4,8,12}
{3,10}+{1,6,8,11}+{4,9}+{2,5,7,12}
{5,8}+{6,7}+{1,4,10,11}+{2,3,9,12}
4+4+4{1,4,10,11}+{2,5,7,12}+{3,6,8,9}
{1,4,10,11}+{2,7,8,9}+{3,5,6,12}
{1,5,9,11}+{2,6,8,10}+{3,4,7,12}
{1,6,8,11}+{2,3,9,12}+{4,5,7,10}
{1,6,8,11}+{2,5,9,10}+{3,4,7,12}
{1,6,9,10}+{2,5,7,12}+{3,4,8,11}
{1,6,9,10}+{2,5,7,12}+{3,4,8,11}
{1,7,8,10}+{2,3,9,12}+{4,5,6,11}
6+6{1,3,7,8,9,11}+{2,4,5,6,10,12}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-22 09:04:19 | 显示全部楼层

我最开始也根据 33,17,102之间的关系作了一般化处理。。。

只是未公开而已,呵呵,
还是你的比较彻底,比较专业
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-22 09:59:02 | 显示全部楼层
我来开一个头,第一问:
对于三元均衡样本,n应该为奇数,   样本个数为 Ceiling [(n-1)^2/8]

评分

参与人数 1威望 +2 金币 +2 贡献 +2 经验 +2 鲜花 +2 收起 理由
hujunhua + 2 + 2 + 2 + 2 + 2 完全正确

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-4-22 14:31:51 | 显示全部楼层
这道题跟http://bbs.emath.ac.cn/thread-2251-1-1.html很相似
qianyb 发表于 2010-4-22 08:16

那里是优劣程度,这里是是非问题,数学上完全不同,算法上应该也有较大差别吧。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-22 15:15:07 | 显示全部楼层
这个感觉还是可解的吧。
将中点做为数轴0点,于是应该是左边的数+右边的数相等
而对于“k个正整数相加=定值”的计数是个经典的结论,所以总的计数再求一下和。但不知能否写成close形式。
分划也容易,对于所有分划的计数可能还有些困难。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-4-23 00:22:07 | 显示全部楼层
n极大划分数既约样本数既约均衡样本(n为奇数时省略中数)极大划分模型极大划分(n为奇数时省略中数)

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-23 07:36:22 | 显示全部楼层
评分是可以撤销的。
至少管理人员有该权限。不知你现在有没有?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 19:05 , Processed in 0.051253 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表