[原创]一道组合问题的猜想

fuzhineng

[watermark]有4个人，其中2个中国人，2个美国人；2个男人，2个女人，那么必然可以找出两个人，他们在国籍和性别上都不相同。
推广如下：
有2的n次方个元素，n种属性，每种属性都将这2^n个元素等分为两半，每一半的此属性相同，和另一半的属性不同。那么必然可以找出两个元素，它们在所有属性上都不相同。[DISABLELBCODE][/watermark]

fuzhineng

没有人回吗

ccmmjj

有点意思，这要让人有思考的时间

fuzhineng

n=3的时候有反例了，用n位2进制表示n个特征，以下4个特征：000,110,101,011，各2个人。那么每一位上有0有1的都有4个人，但是每两类特征都至少有一个相同特征。

fuzhineng

我还有一个猜想,也一直都证明不出来.
A={a1,a2,…,an}是一个n元素的集合，α1, α2,…, αm都是A的子集。满足如下条件：
1。若i≠j则αi交αj=空
2。任意k+1个αi的元素个数和大于任意k个αi的元素个数和。
那么称α={α1, α2,…, αm}是A的一个好划分。
从每个αi中各取出一个元素构成的A的子集称为α的一个代表。
p是A上的一个置换，如果X是α的一个代表，经过p置换后子集p(X)仍然是α的一个代表，那么称X为置换p在α上的一个代表解。
求证：只要α是好的划分，那么任意p都至少存在一个α上代表解。[br][br]-=-=-=-=- 以下内容由 fuzhineng 在 时添加 -=-=-=-=-
这个猜想的一般描述理解起来特别费事,为了简单起见,列出它的一个特例;
在1到2*n中选出n个数A={a1,…,an},如果这n个数中任意两个数ai,aj,对n的余数都不相同,这称此n个数A为n代表.p是1到2*n中的一个置换,那么对任意 p总存在一个n代表A,使得p(A)也是n代表

ccmmjj

下面引用由fuzhineng在 2013/09/10 10:54am 发表的内容：
n=3的时候有反例了，用n位2进制表示n个特征，以下4个特征：000,110,101,011，各2个人。那么每一位上有0有1的都有4个人，但是每两类特征都至少有一个相同特征。

我认为你的猜想是正确的。而且这恐怕不是猜想，而是事实。你的反例不对，那只是三个特征，而不是4个。[br][br]-=-=-=-=- 以下内容由 ccmmjj 在 时添加 -=-=-=-=-
看来还真是你对

ccmmjj

我改一下题目
有2的n次方个元素，n种特征，每种特征都有两种属性，将这2^n个元素等分为两半，每一半的属性和另一半的属性不同。如果没有完全相同的两个元素，那么必然可以找出两个元素，它们在所有特征的属性上都不相同。

fuzhineng

如果没有完全相同的两个元素,那么这2^n个元素将穷尽所有2^n种可能,题目显然成立.
个人认为这个猜想很失败,再研究下去没有什么意思了.