萌新问个题【数学吧】

数学吧关注：931,076贴子：8,914,558

1.某班有2n个学生，n张课桌，2人一桌，若每周调换一次座位，要使每次调换后都是以前没有同桌过的，那么最多可以调换几周?
2.使调换周数最多的调换方案有几种？

送TA礼物

IP属地:陕西

来自Android客户端1楼2018-08-28 22:11回复

第一问我验证了n为2，3，4的情况，答案应该是2n-1，但是不懂证...
第二问也没有头绪。

IP属地:陕西

来自Android客户端3楼2018-08-28 22:19

不感兴趣

开通SVIP免广告

哇，沉的好快QAQ

IP属地:陕西

来自Android客户端4楼2018-08-29 12:27

收起回复

考虑2n阶完全图K2n，（也就是有2n个顶点，每两点之间连一条线的图)。你的问题也就是问，能否将K2n分解为2n-1个完美匹配。答案是能，这个构造解法很容易。就是固定1，后面2n-1个数循环一遍。

IP属地:湖北

来自Android客户端5楼2018-08-31 13:35

第二问我猜测是(2n-3)!!因为K2n的完美匹配个数为(2n-1)!!。这个很容易证明，与1匹配的有2n-1个，去掉这个匹配后，就是K2n-2的完美匹配个数。也就是f(2n)=(2n-1)f(2n-2)。然后每次分解用掉2n-1个匹配，所以共有(2n-3)!!次

IP属地:湖北

来自Android客户端6楼2018-08-31 13:55

IP属地:湖北

来自Android客户端7楼2018-08-31 13:58

IP属地:湖北

来自Android客户端8楼2018-08-31 20:50

下载贴吧APP
看高清直播、视频！

贴吧热议榜

发表回复

内容:

使用签名档查看全部

发表

保存至快速回贴