发新话题
打印【有0个人次参与评价】

[数学] 俄罗斯数学竞赛题

俄罗斯数学竞赛题

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

TOP

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

TOP

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

TOP

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

TOP

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

TOP

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

TOP

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

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

附件

111.gif (5.76 KB)

2008-3-12 23:07

111.gif

222.gif (6.61 KB)

2008-3-12 23:07

222.gif

TOP

通过初等判断,除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)
是否是个普遍规律呢?.

TOP

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

TOP

探索者。.

TOP

有意思.

TOP

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

TOP

俺觉得可能有如下命题:
按上述变换规则,
两个相邻自然数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必是奇数,存在另外的循环,
即若某一对数字不互质时,会发生短循环。
但这些循环不会交叉。.

TOP

引用:
原帖由 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楼的解答以后,再考虑推广比较好。.

TOP

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

TOP

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

TOP

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

TOP

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

TOP

发新话题