数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 426|回复: 6

[讨论] 一个数论问题

[复制链接]
发表于 2017-9-9 21:26:20 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
萨沙沿着圆周以任意顺序写了不多于100个互不相同的正整数,而季玛试图猜出它们的个数,为此,季玛以某种顺序告知萨沙一些号码,萨沙则从某一固定位置开始依顺时针方向,把季玛所说的号码所对应的位置上所写的数告诉季玛,季玛为了保证猜出圆周上数的个数,最少要告之多少个号码。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-9-10 20:25:21 | 显示全部楼层
设M=[1,2,3,...,100]也就是前100个数的最小公倍数。
那么对于任意一个素数p,如果两个位置相差$M/p$而值相同,那么就说明圆周长度不是p的倍数;否则必然是p的倍数。
而对于大于11的所有21个素因子,必然不会同时出现,我们可以同时判断多个大于11的素因子来使用二分法判断出各个素因子是否为圆周长度的因子。
对于小于11的4个因子,可以在大素数因子确定的情况下,在设计方案缩小范围
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-9-11 09:03:42 | 显示全部楼层
谢谢mathe老师,这个题目是第76届莫斯科数学竞赛的一道题,原题目的问题有2个,(1)季玛为了保证猜出圆周上数的个数,告之17个号码可以吗。(2)告之的号码少于16个可以吗。 第二个问题的答案也是这个思路,给出了15个号码可以保证猜出。
答案最后又说了一句最少的号码要比15小很多,这个就不太明白了。我感觉最少的号码应该比15小不了多少啊。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-9-11 19:01:39 来自手机 | 显示全部楼层
我也觉得应该可以远远小于15个号码。但是找最优解很难。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-9-11 19:06:23 来自手机 | 显示全部楼层
首先一次操作可以判断是否存在不小于11的素因子,如果存在,由于只有21种可能,5次二分法可以完全确定大于10的素因子。而对于小于10的素因子,2最多6次,3次二分法可以确定其次数。3最多4次 ,也最多判断3此次,5和7都最多判断两次。
这种简单方案累积已经最多需要1+5+3+3+2+2=16次了。如果我们考虑第一次判断后,不存在大于10的因子只需要再判断3+3+2+2,而存在大于10的因子,那么2最多3次,3最多两次,5,7最多一次,需要最多判断5+2+2+1+1,再加上第一次区分两种情况需要的方案,12次即可。
但是这方案显然远远不是最优的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-9-11 19:20:38 来自手机 | 显示全部楼层
上面提到次数应该全部加一,也就是我们实际上只使用了第一次和后面各次的差值。如果设计良好,继续使用了后面各次之间的差值,会有更好的改善
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-9-13 22:51:44 | 显示全部楼层
又算了一下,11个号码是可以的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

GMT+8, 2017-11-24 08:03 , Processed in 0.242871 second(s), 21 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表