洗牌问题（已解决）

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 编辑 ]

123wyx

明白了，谢谢各位！

lulijie

11楼的证明太漂亮了。本帖的两个提问都圆满的解答了

yq_118

引用6#的结果。

位置 i 的牌经过一次洗牌后位置变为 2*i mod (2n+1)
第一张牌经过m次洗牌后回到初始位置，那么m满足 2^m mod (2n+1) =1。

所以位置 i 的牌经过m次洗牌后位置变为 (2^m)*i mod (2n+1) =i。
即m次洗牌后每张牌都归位，整副牌还原。

m=k 为方程  2^x mod (2n+1) =1 的最小正整数解。

tm__xk

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

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 编辑 ]

123wyx

楼上已经有高手出现了

现在仍然没有头绪

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

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

chuchudengren

按楼上的方法确实有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为止。

lulijie

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