Author Topic: 灵机一动十二月:公平分组  (Read 14988 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
灵机一动十二月:公平分组
« on: 十二月 16, 2009, 10:12:55 am »
快过节了,俱乐部内部要搞一个比赛活跃气氛。计划是分两组搞对抗赛。为了比赛
更有趣,就要尽可能的好坏搭配,否则一边倒就没有意思了。这个月的题目就是如
何搞这样一个公平分组。

灵机一动十二月:公平分组

假设俱乐部有八个人,他们的技术水平是从1到8。要分成两组,每组4个人。对
抗赛是打双打。双打的实力是两个队员的实力和。比如,实力为3与实力为5的人
配对,他们的实力就是8。4个人共有6种配对方法。所以对抗赛要赛6场。我们
的问题是,8个人要分两组,还要求每组的6个双打组合实力完全匹配。也就是说
这组的6对双打实力与另一组的6对双打实力是同一组数。双方可以安排出两边实
力相同的六场比赛,而且没有同一个组合打两次。


注1:这题初看起来很麻烦,好象要试很多组合。实际上几乎可以完全硬推出来。
比如1和2不可能在同一组,因为不可能再有实力和为3的组合。因为是推出来的,
所以解唯一。

注2:当N=16时,也就是说16个队员分成两个8人组,每组的双打实力匹配,
也有唯一解。比N=8时麻烦一些,但也差不多可以推出来。

注3:我猜想N=2^K时都有唯一解。构造部分比较容易想到,但唯一部分还不
是太清楚。


wanxiang

  • Jr. Member
  • **
  • Posts: 35
Re: 灵机一动十二月:公平分组
« Reply #1 on: 十二月 16, 2009, 08:45:35 pm »
看了老半天才看懂,我帮你改一下题目
将一到八这八个数分成相同数目的两组,使得这两组数的两个不同数的组合有一一对应关系,对应法则为两个不同数的和相等
用归纳法唯一性也容易证明
« Last Edit: 十二月 16, 2009, 09:14:15 pm by wanxiang »

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: 灵机一动十二月:公平分组
« Reply #2 on: 十二月 17, 2009, 04:42:08 pm »
Quote
看了老半天才看懂,我帮你改一下题目

将一到八这八个数分成相同数目的两组,使得这两组数的两个不同数的组合
有一一对应关系,对应法则为两个不同数的和相等

数学题目是很多的,随便找一本数学教科书就可以找到解不完的题目。但是,有背景的趣味
题目就不多了。我花了大力气把一个数学题变成一个趣味题(找到有用的背景),你却把它
又转会数学题目。:)当然,数学题目的好处是简洁,清楚,准确。


Quote
用归纳法唯一性也容易证明


构造可以用归纳法,但唯一性好象不好归纳。

wanxiang

  • Jr. Member
  • **
  • Posts: 35
Re: 灵机一动十二月:公平分组
« Reply #3 on: 十二月 17, 2009, 09:04:55 pm »
构造的同时就可以证明唯一性,你再想想
我倒觉得漂亮简洁的问题更有意思
« Last Edit: 十二月 18, 2009, 06:31:03 am by wanxiang »

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: 灵机一动十二月:公平分组
« Reply #4 on: 十二月 18, 2009, 11:57:59 am »
Quote
构造的同时就可以证明唯一性,你再想想

存在性的证明只需两行字,唯一性大概不是两行可以说清楚的。

你找一找N=12或N=24的解就知道我说的意思了。

Quote
我倒觉得漂亮简洁的问题更有意思

说得不错,漂亮简洁都是褒义词,当然有意思。可是象FERMAT大定理那样漂亮简洁的东西
不是很多。更关键的是不能以数学题的面目出现。比如,我给一个数列,让大家证明它发散,
大家的感觉就是,我到这里来是找趣味的,不是做数学题的。但是,如果你说这数列来自某
个大银行,它的发散性会导致经济危机,那就比较有意思了。如果你说这数列来自某个大赌
场,它的发散性表明赌场总是赚,那也很有意思。再比如,让大家求 f = B/sin u + A/cos u
的最小值,大家就不会太有兴趣。如果让大家考虑搬沙发拐角,这题目顿时就变得有趣多了。
搬沙发

wanxiang

  • Jr. Member
  • **
  • Posts: 35
Re: 灵机一动十二月:公平分组
« Reply #5 on: 十二月 18, 2009, 08:30:28 pm »
我觉得有用的问题可以找物理书或者应用数学书,上面有很多
这个问题4n时解都存在,例如12这样分组:1,4,6,7,10,11;2,3,5,8,9,12
唯一性的证明和注1一样

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: 灵机一动十二月:公平分组
« Reply #6 on: 十二月 18, 2009, 08:45:32 pm »
Quote
例如12这样分组:1,4,6,7,10,11;2,3,5,8,9,12

你再想想。8+12=?

Quote
唯一性的证明和注1一样

所以我说不是很清楚。

wanxiang

  • Jr. Member
  • **
  • Posts: 35
Re: 灵机一动十二月:公平分组
« Reply #7 on: 十二月 18, 2009, 11:00:45 pm »
对不起,我犯低级错误了,昨天晚上很晚临睡前想的,我找了一下根本就没有草稿,刚才也只是试了头几个组合。唉,这是我在这里第二次犯错误了,看来以后得小心了
这个证明是那天吃饭的时候想到的,现在重新检查并补充没有发现问题,你再帮我检查一下

n=4时,解存在并且是唯一的
1和2不可能在同一组,因为不可能再有和为3的组合
3和1不可能在同一组,因为不可能再有和为4的组合
这样解为1,4;2,3
n=8时,1到4只有一种分法,考虑5到8,和上面的论证一样
7和8不可能在同一组,因为不可能再有和为15的组合
6和8不可能在同一组,因为不可能再有和为14的组合
从而5到8也只有一种分法
5和1不可能在同一组,因为不可能再有和为6的组合
得到可能的唯一解1,4,6,7;2,3,5,8。经验证确实为解
假设n=2^k(k>1)有唯一解,n=2^(k+1)时
由于1到2^k只有一种分法,反过来从大到小考虑,可得2^k+1到n=2^(k+1)也只有一种分法
1和2^k+1不可能在同一组,因为不可能再有和为2^k+2的组合
从而得到可能的唯一解。这个解很有规律,容易验证确实为解

对于n为其它数的情况应该是不存在解,但是我想了很久也没有想到怎么证明
« Last Edit: 十二月 19, 2009, 07:26:01 am by wanxiang »

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: 灵机一动十二月:公平分组
« Reply #8 on: 十二月 19, 2009, 06:19:23 pm »
存在性的证明很简单:如果A,B是N的解,则,【A,B+N】,【B,A+N】 是2N的解。
唯一性就不是这么简单。

Quote
唉,这是我在这里第二次犯错误了,看来以后得小心了

不小心的事谁都可以发生,不必在意。

Quote
由于1到2^k只有一种分法,

问题就出在这里。如果一个一个地推,当然可以证明唯一性,但对任意N=2^K是不能一个一
个推的,必须要归纳。可是,一归纳就要用到你上面这句话。1到2^k的唯一性是假设最大的
数是2^k,当最大的数大于2^k时,我们不知道有没有别的解(我想是没有,但这不算证明)。
我们的推导都是4个一组或8个一组(所以你才会认为4N的情况都有解)。我让你考虑N=12及
N=24的解就是想说,后面的数会影响前面的解(N=24没有解而N=32却有解)。所以,需要说
明1到2^k只有一种分法在有大于2^k的数时也是成立的。我想这是成立的,但还是那句话,没
有存在性那么简单。

wanxiang

  • Jr. Member
  • **
  • Posts: 35
Re: 灵机一动十二月:公平分组
« Reply #9 on: 十二月 19, 2009, 08:03:19 pm »
这个证明确实有漏洞,还很难弥补
证明看样子很难,不想了
换个简单一些的题目
把1到4n(n>0)这4n个数分成数目相同总和相等的两组数,问有多少种分法
我还没有做出来
« Last Edit: 十二月 20, 2009, 08:12:56 pm by wanxiang »

warren

  • Full Member
  • ***
  • Posts: 148
Re: 灵机一动十二月:公平分组
« Reply #10 on: 一月 01, 2010, 07:17:34 am »
结论似乎比较简单

1. 只有当N=2^K时才有解.
2. 当N=2^K时,分组方法唯一.

分组方法: 为方便起见, 设N个数是0,1,2,...,N-1. 把这些数用二进制表示出来,各位数字之和是偶数的分在A组,各位数字之和是奇数的分在B组.

双人组合的对应:  任意一个双人组合, 先在高位数字补上0, 使两个数数字一样长. 从高位起, 第一个数字不同的等位位置上交换数字, 两个数之和不变, 但是两个数数字之和改变奇偶性, 也就是说从A组变到B组,也就是说从B组变到A组.  例如, 1111+0011对应0111+1011. 这种映射是单射(不一定是满射), 当N=2^K时是一一对应.

过几天再贴证明.



warren

  • Full Member
  • ***
  • Posts: 148
Re: 灵机一动十二月:公平分组
« Reply #11 on: 一月 08, 2010, 05:04:22 am »
结论似乎比较简单

1. 只有当N=2^K时才有解.
2. 当N=2^K时,分组方法唯一.

分组方法: 为方便起见, 设N个数是0,1,2,...,N-1. 把这些数用二进制表示出来,各位数字之和是偶数的分在A组,各位数字之和是奇数的分在B组.

双人组合的对应:  任意一个双人组合, 先在高位数字补上0, 使两个数数字一样长. 从高位起, 第一个数字不同的等位位置上交换数字, 两个数之和不变, 但是两个数数字之和改变奇偶性, 也就是说从A组变到B组,也就是说从B组变到A组.  例如, 1111+0011对应0111+1011. 这种映射是单射(不一定是满射), 当N=2^K时是一一对应.

过几天再贴证明.




下面证明上述结论.

1. 当N=2^K时, 根据上述分组规则, 数字之和是偶数的分在A组,各位数字之和是奇数的分在B组.  容易验证上述双人组合对应是一一对应.

2. 公平分组方法唯一. 设N <= 2^K, N个数的公平分组记为A(N),B(N), 2^K个数的符合上述分组规则的公平分组记为A(2^K), B(2^K). 不妨设 0 在A(N)和A(2^K)中. 以下称和为S的双人组合为S-组合. 可以直接验证 I <= 8 时公平分组一定符合上述分组规则. 设当 I <= J 时公平分组符合上述分组规则, 下面考虑J+1分在哪一组. 若J+1的各位数字之和是偶数, 则J+1在A(2^K)中, 而且A(2^K)和B(2^K)中的(J+1)-组合数相等.如果J+1在B(N)中, 则与A(2^K)相比,A(N)中的(J+1)-组合少了一个,而B(N)和B(2^K)中的(J+1)-组合数相等,因此 A(N)和B(N)不是公平分组,矛盾.故J+1在A(N)中. 若J+1的各位数字之和是奇数, 则J+1在B(2^K)中. 如果J+1在A(N)中, 则与A(2^K)相比,A(N)中的(J+1)-组合多了一个,而B(N)和B(2^K)中的(J+1)-组合数相等,因此A(N)中的(J+1)-组合比B(N)中的(J+1)-组合多一个,矛盾.故J+1在B(N)中. 总之,J+1符合上述分组规则. 由归纳法, 任何数都必须符合上述分组规则.

3. N != 2^K 时, 不存在公平分组. 假设存在 N 个数0,1,2,...,N-1的公平分组A,B. 对每一个数作对称变换:X-->X'=N-1-X. 这个变换将0,1,2,...,N-1变成N-1,N-2,...,1,0. 将S-组合变成(2N-2-S)组合. 因此它将公平分组A,B变成公平分组A',B'. 由公平分组的唯一性, A',B'也符合分组规则: 同一组内每一个数的各位数字之和奇偶性相同. 如果 N != 2^K, 则 N-1 的二进制表示中必然有 0. 设 N-1 的二进制表示中前 J 位都是 1, 第J+1位是0. 令X=N-1,Y为X的第J位和第J+1位交换次序后得到的数. 则X和Y在同一组. 但是它们作对称变换后变成0和 0...010...0( 第J+1位是1), 不在同一组, 矛盾. 故若存在公平分组, 一定有N = 2^K.


wanxiang

  • Jr. Member
  • **
  • Posts: 35
Re: 灵机一动十二月:公平分组
« Reply #12 on: 一月 08, 2010, 06:24:03 am »
没看明白,我的感觉是这个证明是不对的,例如“设N <= 2^K, N个数的公平分组记为A(N),B(N)”,怎么可以这样假设?要假设也应该是N=2^(K-1),还是等万精油来检查吧
利用二进制来分组我早想到了,但是想了非常久也没有想到怎样利用二进制来证明。我猜可能不存在简单的证明,应该要用到比较复杂的代数或组合知识,可惜我水平太差,不敢问津

warren

  • Full Member
  • ***
  • Posts: 148
Re: 灵机一动十二月:公平分组
« Reply #13 on: 一月 08, 2010, 07:34:38 am »
没看明白,我的感觉是这个证明是不对的,例如“设N <= 2^K, N个数的公平分组记为A(N),B(N)”,怎么可以这样假设?要假设也应该是N=2^(K-1),还是等万精油来检查吧
利用二进制来分组我早想到了,但是想了非常久也没有想到怎样利用二进制来证明。我猜可能不存在简单的证明,应该要用到比较复杂的代数或组合知识,可惜我水平太差,不敢问津

“设N <= 2^K, N个数的公平分组记为A(N),B(N)”, 这个假设没有问题. 这之前并没有证明只有N是2的幂才有公平分组. 这一段是要证明任何公平分组都服从前面提到的分组法则.

wanxiang

  • Jr. Member
  • **
  • Posts: 35
Re: 灵机一动十二月:公平分组
« Reply #14 on: 六月 08, 2010, 11:49:06 pm »
见鬼,居然没有注意到网上已经有解答了。相当漂亮,不愧是高手
http://cms.math.ca/cmb/v2/cmb1959v02.0085-0089.pdf