新未名空间

别处看到的，简化版

2N张牌，初始1,2,3,4,...2N-1, 2N

按照如下规则洗牌，拆成前后两半，然后间隔插入
比如1 2 3 4 5 6 7 8-> 1 2 3 4 + 5 6 7 8 -> 1 5 2 6 3 7 4 8

请证明，一副牌，洗最多2N次就能还原

补充一问，根据混元形意太极门的解可知2N-2次洗牌可以使得牌洗回原样，2N-2为最小resetting shuffle的上界。那么使得需要最少洗2N-2次才能还原的条件是什么(in terms of N).

（ヅ） 写了： 2023年 1月 22日 16:14 别处看到的，简化版

2N张牌，初始1,2,3,4,...2N-1, 2N

按照如下规则洗牌，拆成前后两半，然后间隔插入
比如1 2 3 4 5 6 7 8-> 1 2 3 4 + 5 6 7 8 -> 1 5 2 6 3 7 4 8

请证明，一副牌，洗最多2N次就能还原

提一个问题：似乎达到第一次还原需要的次数是固定的。为啥要用“最多”这个限定语，让人感觉似乎某些情况下少于这个数也可以？

这个真可以用群论，有限群元素的阶小于等于群元素个数

verdelite 写了： 2023年 1月 22日 16:31 提一个问题：似乎达到第一次还原需要的次数是固定的。为啥要用“最多”这个限定语，让人感觉似乎某些情况下少于这个数也可以？

可以比较容易验证

N = 4, (1 5 2 6 3 7 4 8) = (1)(2 5 3)(4 6 7)(8), 3次
N = 5, (1 6 2 7 3 8 4 9 5 10) = (10)(2 6 8 9 5 3)(4 7)(10), 6次
N = 6, (1 7 2 8 3 9 4 10 5 11 6 12) = (1)(2 7 4 8 10 11 6 9 5 3)(12), 10次
N = 7, (1 8 2 9 3 10 4 11 5 12 6 13 7 14) = (1)(2 8 11 6 10 12 13 7 4 9 5 3)(14), 12次

（ヅ） 写了： 2023年 1月 22日 16:41 可以比较容易验证

N = 4, (1 5 2 6 3 7 4 8) = (1)(2 5 3)(4 6 7)(8), 3次
N = 5, (1 6 2 7 3 8 4 9 5 10) = (10)(2 6 8 9 5 3)(4 7)(10), 6次
N = 6, (1 7 2 8 3 9 4 10 5 11 6 12) = (1)(2 7 4 8 10 11 6 9 5 3)(12), 10次
N = 7, (1 8 2 9 3 10 4 11 5 12 6 13 7 14) = (1)(2 8 11 6 10 12 13 7 4 9 5 3)(14), 12次

哦就是里cycle长度的公倍数

Caravel 写了： 2023年 1月 22日 16:51 哦就是里cycle长度的公倍数

是，问题实际上是，为什么不会拆成1+7+3+1这种

（ヅ） 写了： 2023年 1月 22日 16:41 可以比较容易验证

N = 4, (1 5 2 6 3 7 4 8) = (1)(2 5 3)(4 6 7)(8), 3次
N = 5, (1 6 2 7 3 8 4 9 5 10) = (10)(2 6 8 9 5 3)(4 7)(10), 6次
N = 6, (1 7 2 8 3 9 4 10 5 11 6 12) = (1)(2 7 4 8 10 11 6 9 5 3)(12), 10次
N = 7, (1 8 2 9 3 10 4 11 5 12 6 13 7 14) = (1)(2 8 11 6 10 12 13 7 4 9 5 3)(14), 12次

没看懂你这表示是什么意思。括号代表什么意思？逗号隔开又代表什么意思？

verdelite 写了： 2023年 1月 22日 17:34 没看懂你这表示是什么意思。括号代表什么意思？逗号隔开又代表什么意思？

置换群的元素写法

(1)表示单元素自己到自己映射，就是不动映射(可以省略)

(3 5 7) 就是f(3) = 5, f(5）= 7， f(7) = 3

https://en.wikipedia.org/wiki/Permutation_group

Caravel 写了： 2023年 1月 22日 16:33 这个真可以用群论，有限群元素的阶小于等于群元素个数

这里 “群元素” 好像并不是很少吧，如果你考虑的是置换群的话。

这个看上去确实是个群的问题，并且看上去好像比较初等。但我并不会，哈哈。
只能写前几步，希望老师给步骤分：
把 position i => position j 的变动看做一个映射，所有这些映射构成了一个置换群。题目中的是一个特殊映射，其实就是说这个特殊映射生成的子群的阶不超过 2N（但我并不知道为什么）。
置换可以被进一步分解为若干个不相交的轮换。每个轮换的阶都是轮换的长度。这样的话，题目里实际是说，形如：
1 2 3 4 5 6 7 8 => 1 5 2 6 3 7 4 8
这样的置换，分解为单个轮换之后，所有轮换的公倍数是 <= 2N。
好了就只会写这么多了，老师看在没有功劳也有苦劳的基础上给一分吧。

（ヅ） 写了： 2023年 1月 22日 16:41 可以比较容易验证

N = 4, (1 5 2 6 3 7 4 8) = (1)(2 5 3)(4 6 7)(8), 3次
N = 5, (1 6 2 7 3 8 4 9 5 10) = (10)(2 6 8 9 5 3)(4 7)(10), 6次
N = 6, (1 7 2 8 3 9 4 10 5 11 6 12) = (1)(2 7 4 8 10 11 6 9 5 3)(12), 10次
N = 7, (1 8 2 9 3 10 4 11 5 12 6 13 7 14) = (1)(2 8 11 6 10 12 13 7 4 9 5 3)(14), 12次

看到这些例子之后并没看出啥规律。尤其是 N=5 的时候居然有一个 size2 和一个 size6
唯一看出的 “规律” 就是首和尾都显然不变，所以这俩都是 size 1 的平凡轮换。惭愧，哈哈！

lbs 写了： 2023年 1月 22日 22:49 这里 “群元素” 好像并不是很少吧，如果你考虑的是置换群的话。

如果洗牌操作对应的置换群中的元素g, 要证明g的阶不大于2N.
如果置换前的位置是n=2k+1，置换后是k+1;
如果置换前的位置是n=2k，置换后是N+k.

1和2N显然不变。从2开始，第一次置换后是N+1.
如果N=2N'，第二次置换后是N'+1;
如果N=2N'+1，第二次置换后是N+N'+1.
如果N'是偶数，...

不知道还有什么更好的方法？

如果N是2的幂，那么2 -> N+1 -> N/2+1 -> N/4+1 -> N/8+1 -> ... -> 2，长度为log_2(N)+1.
4 -> N+2 -> N+N/2+1 -> N/2+N/4+1 -> ... -> 4，

发现除了2的幂（最容易的情况），其它需要的次数都是偶数，而且在中途会出现：
1, 2N-1, 2N-2,...,2,1,2N
多个次数恰好是2N-2。也有少的。

（ヅ） 写了： 2023年 1月 22日 16:14 别处看到的，简化版

2N张牌，初始1,2,3,4,...2N-1, 2N

按照如下规则洗牌，拆成前后两半，然后间隔插入
比如1 2 3 4 5 6 7 8-> 1 2 3 4 + 5 6 7 8 -> 1 5 2 6 3 7 4 8

请证明，一副牌，洗最多2N次就能还原

This problem has been solved. It's on wiki. a little trick.
one way shuffle :1 2 3 4 5 6 7 8-> 1 2 3 4 + 5 6 7 8 -> 1 5 2 6 3 7 4 8
the other way shuffle :1 2 3 4 5 6 7 8-> 1 2 3 4 + 5 6 7 8 -> 5 1 6 2 7 3 8 4.

（ヅ） 写了： 2023年 1月 22日 16:41 可以比较容易验证

N = 4, (1 5 2 6 3 7 4 8) = (1)(2 5 3)(4 6 7)(8), 3次
N = 5, (1 6 2 7 3 8 4 9 5 10) = (10)(2 6 8 9 5 3)(4 7)(10), 6次
N = 6, (1 7 2 8 3 9 4 10 5 11 6 12) = (1)(2 7 4 8 10 11 6 9 5 3)(12), 10次
N = 7, (1 8 2 9 3 10 4 11 5 12 6 13 7 14) = (1)(2 8 11 6 10 12 13 7 4 9 5 3)(14), 12次

Look up Faro Shuffle on Wikipedia.

有对称性：1和2N对称，2和2N-1对称，等等。洗牌保持这个对称：如果洗牌把x变成y，那么x的对称牌一定变成y的对称牌。

所以，如果一对对称的数出现在同一循环中，那么这一循环的长度必是偶数。如果一对对称的数分别出现在不同的循环中，那么这两个循环是对称的（长度可奇可偶），两循环长度之和为偶。

别的我就不知道了。

猜测：所有循环中，最长的长度是别的长度的倍数（包括相等，一倍），很有可能2所在循环长度就满足这个条件。猜测对不对我没信心。但如能证出此猜测，那么本楼的问题就做出来了。

其实，为了更节省符号的话，可考虑（举例4张牌的情况）1234 --》12 + 34 --》 3142，这样4张牌都动了。按一楼的洗牌法，中间那2N-2张牌就遵从我刚说的洗牌法，同时第一张和第2N张牌不动。当然这对解决问题无实质性帮助，只是省去两张牌。

根据wiki的提示，
https://en.wikipedia.org/wiki/Faro_shuffle#cite_note-7
搞明白该怎么做。考虑另一种洗牌：
1 2 3 4 5 6 7 8
5 1 6 2 7 3 8 4
这种的2N张牌和楼主的2N+2张牌是一一对应。

然后只需要观察到一个现象：洗一次牌后，n号牌到达2n mod (2N+1)的位置。

CalCat 写了： 2023年 1月 23日 12:17 This problem has been solved. It's on wiki. a little trick.
one way shuffle :1 2 3 4 5 6 7 8-> 1 2 3 4 + 5 6 7 8 -> 1 5 2 6 3 7 4 8
the other way shuffle :1 2 3 4 5 6 7 8-> 1 2 3 4 + 5 6 7 8 -> 5 1 6 2 7 3 8 4.

不错

FGH 写了： 2023年 1月 23日 12:55 根据wiki的提示，
https://en.wikipedia.org/wiki/Faro_shuffle#cite_note-7
搞明白该怎么做。考虑另一种洗牌：
1 2 3 4 5 6 7 8
5 1 6 2 7 3 8 4
这种的2N张牌和楼主的2N+2张牌是一一对应。

然后只需要观察到一个现象：洗一次牌后，n号牌到达2n mod (2N+1)的位置。

赞！我洗牌公式都写出来了，但没往mod (2N+1)的方向想，失之交臂！