近日，有同学问我一道俄罗斯数学竞赛题：两个罐子中共有2p+1个球，每一秒中都把放有偶数个球的罐子中的一半的球投入另一个罐子，设k为小于2p+1的自然数，p和2p+1都是素数，证明:或迟或早某一个罐子正好装有k个球。
俄罗斯、罗马尼亚、巴尔干等东欧地区，总能出现一些数论、组合方面的好题，此题可以供高中同学思考。.

此题主要的难点在于，并不是每次都针对一个罐子进行减半操作，这样也就无法递推，难以找到明显的规律。
找不到“一致的步伐”。.

此题甚妙。
是不是只要p和2p+1都是质数，其循环就是p步？.

出现P对
而且数字不重复.

有群论或者原根的思想就比较简单。
当p=2时显然，
当p>=3时，由于2p+1是素数，因此2^2p=1(mod 2p+1)
又由于p是素数，因此2^k=1(mod 2p+1) 大于0小于2p+1的解只可能为p,2p，后面就简单了。.

没有群论或者原根的思想呢？.

主要是“步伐”统一起来就可以了。
要能做出此题的学生，需要扎扎实实学半年数论。

[ 本帖最后由 wood 于 2008-3-12 23:10 编辑 ].

通过初等判断，除p=2、3，必须满足质数p=6n-1，n是除0外自然数
比如：n=1，p=5；n=2,p=11；n=4,p=23；n=5,p=29都可以
但n=3,p=17时不行，因为2p+1=35是合数
n=6,p=35时又不行了。

不过试验了下p=17，2p+1=35，发现个满有意思的东东：
打个循环先
17，18
26，9
13，22
24，11
12，23
6，29
3，32
19，16
27，8
31，4
33，2
34，1
17，18
除了数字5、10、15、20、25、30、
        7，14，21，28
外，其余1~34都出现了。
而没出现的数字的规律是显而易见的：
35的约数的整数倍，且都成对
（5，30）、（10、25）（15、20）、（7、28）、（14、21）
是否是个普遍规律呢？.

p=47,2p+1=95
也是这样的，除了5、19的整数倍，1~94都出现了。.

探索者。.

有意思.

能编出这样的题，的确很厉害，我很喜欢东欧国家的题。.

俺觉得可能有如下命题：
按上述变换规则，
两个相邻自然数m、m+1，
若有2m+1=n是素数，则1~2m都出现；
若有2m+1=n=p*k*...是合数，则除合数n的约数p、k、...及其整数倍外，1~2m都出现。

理由：
m、m+1必能按上述变换规则变换，变换后的数字亦如此；
每一次变换都是唯一的、单向的；
这种变换可以无限进行；
故必存在单一循环。

若n是素数，则变换过程中的任一对数字是互质的，所以不存在第二个循环；
若n=p*k*...是合数，n必是奇数，存在另外的循环，
即若某一对数字不互质时，会发生短循环。
但这些循环不会交叉。.

引用:

原帖由 echooooo 于 2008-3-13 09:43 发表
俺觉得可能有如下命题：
按上述变换规则，
两个相邻自然数m、m+1，
若有2m+1=n是素数，则1~2m都出现；
若有2m+1=n=p*k*...是合数，则除合数n的约数p、k、...及其整数倍外，1~2m都出现。

理由：
m、m+1必能按 ...

上面猜测没有触及问题本质，所以不会成立，看7楼的解答以后，再考虑推广比较好。.

呵呵，看了，
看不懂。
俺是在用初等的办法理理思路，
不知能否用高等的办法证明或否定。.

引用:

原帖由 echooooo 于 2008-3-13 12:40 发表
呵呵，看了，
看不懂。
俺是在用初等的办法理理思路，
不知能否用高等的办法证明或否定。

这个也是初等的办法。.

O，俺说的初等是初等的初等。
比较直观易记易懂的那些东东。.

呵呵，家长能这样已经很节棍了。
但是小孩可不能永远停留在此。。。.