洗牌问题（已解决）

123wyx

假设我们有 2n 张牌，它们以 1, 2, ..., n, n+1, ..., 2n 编号并在开始时保持着这种顺序.一次洗牌就是将牌原来的次序变为 n+1, 1, n+2, 2, ..., 2n, n，也就是将原来的前 n 张牌放到位置 2, 4, ..., 2n，并且将余下的 n 张牌按照他们原来的次序放到奇数位置 1, 3, ..., 2n-1.
(1)对于一个特定的 n，设需要k次洗牌才能将牌洗回原来的次序，求k.
(2)对于任意取定的 n，设第一张牌需要m次洗牌才能归位，是否恒有m=k?

这是一个由编程题引出的数学问题，困惑好几天了还没想出答案，望各位魔友指点。

[ 本帖最后由 123wyx 于 2010-5-19 19:04 编辑 ]

limite034

我看出来，在搞上帝之数呢吗？

Pyrenees

这似乎是扑克牌洗牌方法里面的完美洗牌？
我记得貌似八次完美洗牌可以还原。。。。。。

lulijie

n=100以内的结果：
n=1，k=2，m=2
n=2，k=4，m=4
n=3，k=3，m=3
n=4，k=6，m=6
n=5，k=10，m=10
n=6，k=12，m=12
n=7，k=4，m=4
n=8，k=8，m=8
n=9，k=18，m=18
n=10，k=6，m=6
n=11，k=11，m=11
n=12，k=20，m=20
n=13，k=18，m=18
n=14，k=28，m=28
n=15，k=5，m=5
n=16，k=10，m=10
n=17，k=12，m=12
n=18，k=36，m=36
n=19，k=12，m=12
n=20，k=20，m=20
n=21，k=14，m=14
n=22，k=12，m=12
n=23，k=23，m=23
n=24，k=21，m=21
n=25，k=8，m=8
n=26，k=52，m=52
n=27，k=20，m=20
n=28，k=18，m=18
n=29，k=58，m=58
n=30，k=60，m=60
n=31，k=6，m=6
n=32，k=12，m=12
n=33，k=66，m=66
n=34，k=22，m=22
n=35，k=35，m=35
n=36，k=9，m=9
n=37，k=20，m=20
n=38，k=30，m=30
n=39，k=39，m=39
n=40，k=54，m=54
n=41，k=82，m=82
n=42，k=8，m=8
n=43，k=28，m=28
n=44，k=11，m=11
n=45，k=12，m=12
n=46，k=10，m=10
n=47，k=36，m=36
n=48，k=48，m=48
n=49，k=30，m=30
n=50，k=100，m=100
n=51，k=51，m=51
n=52，k=12，m=12
n=53，k=106，m=106
n=54，k=36，m=36
n=55，k=36，m=36
n=56，k=28，m=28
n=57，k=44，m=44
n=58，k=12，m=12
n=59，k=24，m=24
n=60，k=110，m=110
n=61，k=20，m=20
n=62，k=100，m=100
n=63，k=7，m=7
n=64，k=14，m=14
n=65，k=130，m=130
n=66，k=18，m=18
n=67，k=36，m=36
n=68，k=68，m=68
n=69，k=138，m=138
n=70，k=46，m=46
n=71，k=60，m=60
n=72，k=28，m=28
n=73，k=42，m=42
n=74，k=148，m=148
n=75，k=15，m=15
n=76，k=24，m=24
n=77，k=20，m=20
n=78，k=52，m=52
n=79，k=52，m=52
n=80，k=33，m=33
n=81，k=162，m=162
n=82，k=20，m=20
n=83，k=83，m=83
n=84，k=156，m=156
n=85，k=18，m=18
n=86，k=172，m=172
n=87，k=60，m=60
n=88，k=58，m=58
n=89，k=178，m=178
n=90，k=180，m=180
n=91，k=60，m=60
n=92，k=36，m=36
n=93，k=40，m=40
n=94，k=18，m=18
n=95，k=95，m=95
n=96，k=96，m=96
n=97，k=12，m=12
n=98，k=196，m=196
n=99，k=99，m=99
n=100，k=66，m=66

lulijie

验证n=1000以内，都有m=k。

lulijie

设牌的初始位置为x0，那么洗一次牌后的位置为2x0 mod (2n+1).
洗m次牌后的位置为x(m)，那么有以下递推公式：
    x(0)=x0
        x(m)=2*x(m-1) mod (2n+1)
--------------------------------------------------
也就是说题目相当于：
     对于一个数x，乘以2（若结果大于2n，那么结果减去2n+1），一直进行下去，直到回到原来的数x为止。

chuchudengren

按楼上的方法确实有m=k啊

123wyx

楼上已经有高手出现了

现在仍然没有头绪

第二题 我考虑把全部的牌看成几个循环来分析。那么第一张牌所在循环的元素个数就是m值，各循环元素个数的最小公倍数就是k值。
手算了前几个n的循环的元素个数：
（第二列第一个数是1参与的循环的元素个数）

[ 本帖最后由 123wyx 于 2010-5-19 19:01 编辑 ]

123wyx

n=1    2
n=2    4
n=3    3/3
n=4    6/2
n=5    10
n=6    12
n=7    4/4/4/2
n=8    8/8
n=9    18
n=10   6/6/3/3/2
n=11   11/11
n=12   20/4
n=13   18/6/2
n=14   28
n=15   5/5/5/5/5/5
n=16   10/10/10/2
n=17   12/12/4/3/3
…………

确实没看出规律，现在越来越困惑。

[ 本帖最后由 123wyx 于 2010-5-17 16:45 编辑 ]

tm__xk

由6l,有m=k=2对模2n+1的阶.
不能再化简了吧..