有趣的数学问题2? 10

7.p和q是两个互质的正整数。有一只青蛙从数轴上的零点出发,每一步只能向右跳p步,或向左跳q步,最终跳回原点。请证明:无论青蛙如何跳动,对于每一个小于p+q的正整数d,都... 7. p和q是两个互质的正整数。有一只青蛙从数轴上的零点出发,每一步只能向右跳p步,或向左跳q步,最终跳回原点。请证明:无论青蛙如何跳动,对于每一个小于p+q的正整数d, 都存在两个青蛙跳到过的点,这两点之间的距离为d。 展开
 我来答
匿名用户
2021-05-24
展开全部

以向右跳为正,向左跳为负。

设最终回到终点时,累计向右跳了m次,累计向左跳了n次,则mp-nq=0。

由于p和q互质,则有m=kq,n=kq,k为正整数。

p、q等价,可假定p>q

先分析k=1的时候是什么情况:设从左到右,向右跳过的落脚点为Ai,i∈{1,2,……,q};从右到左,向左返回的落脚点分别为Bj,i∈{1,2,……,p}。

先预证1个命题:所有落脚点不重叠。假设有重叠的落脚点,两次落脚之间,分别向右跳了x次,向左跳了y次(显然x<q,y<p),那么xp=yq,也就是x=yq/p。因为p、q互质,那么y是p的整数倍,显然与y<p矛盾。因此假设不成立,命题为真。

  1. 如果先是全部朝一个方向跳,再反向跳着返回,比如先朝右跳q次,再向左跳p次返回原点。总共向右前进了pq,共有p+q-1个落脚点,这些落脚点都不重叠。

    Bj与左侧相邻Ai间的距离可以转化为q的倍数除以p的余数问题:除了原点,Bj的q-1个点离原点距离分别为q、2q、……、(p-1)q。上述预证已证明,这(p-1)个点与Ai的(q-1)个点都不重叠,意味着q、2q、……、(p-1)q都不能被p整除,且余数各不相同(如果余数相同,假设分别对应的Ai和Bj为Ax1、By1和Ax2、By2,那么(p-y1)q-x1p=(p-y2)q-x2p,则有(y1-y2)q=(x2-x1)p,与上述预证类似,不可能存在正整数x1、x2、y1、y2使等式成立)。而p的余数必然∈{1,2,……,p-1},那么这p-1个余数分别对应{1,2,……,p-1}中的一个。

    相应的,Bj与左侧第二近的Ai之间的P-1个不同距离(如果是左侧相邻Ai是A1,则对应原点)分别对应{q+1,q+2,……,p+q-1}中的一个。

    又相邻Ai点间的距离为P,相邻Bj点之间的距离为q。

    按前述假定p>q,那么p-1≥q,

    因此落脚点之间的距离包含了{1,2,……,p-1}∪{p}∪{p+1,p+2,……,p+q-1}={1,2,……,p+q-1}。

  2. 如果青蛙往复跳跃

    累计向右跳动的次数为q,累计向左跳动的次数为p,未回到原点前,累计跳动p+q-1次。按(1)中的证明,这p+q-1个落脚点必然不重叠。所以这p+q-1个落脚点之间的最大距离要≥p+q-1。

    在往复跳跃、使落脚点最紧密的极端的情况下,落脚点之间的最大距离仍然有p+q-1,题目所述命题仍然成立,这时两个相邻落脚点之间的距离只有1。

我只能推到k=1时,落脚点的最大距离取到最大值和最小值的情况,题目所述命题成立。更复杂的往复跳跃情况下如何证明,如何推广到k>1的条件下成立,暂时还想不到。

dickcseeee
2021-05-23 · 超过26用户采纳过TA的回答
知道答主
回答量:98
采纳率:66%
帮助的人:24.9万
展开全部
不知道你有没有学过 Extended Euclidean algorithm,扩展欧几里得算法。

直接上结论, 存在 整数 r, s使得 rp+sq=1, 这里你可以理解为r和s为向左和向右r次或s次,
从0 点出发, 任意小于p+q的数字d都可以写作 1* d, 即 d*r*p+d*s*q=d,
我们可以找到这两个点即0 和 d。
追问
您好,谢谢您的解答。根据我的理解,您的解答对应的是青蛙可以任意跳,但是如果对于特定的某一种跳法,比如0 5 10 15 20 25 30 35 28 21 14 7 0,怎么证明呢?谢谢
追答
多谢提醒,我想到了值得补充的地方。
我没有注意到最重要跳回原点,但这并不影响这道题可以通过扩展欧几里得算法来完成,
比如p=5 q=7
就拿你的例子中没有经过的点3
3*5-2*7=1 3*3*5-2*3*7=3 9*5-6*7=3
即先向右跳9 再向左跳7次到达3
至于回到原点 完全可以通过 补全p*q-q*p=0 来进行,
比如这里r=9 s=6, r>p, s<q, 则我们要将最小公倍数扩大两倍即 70,
先向右跳9再向左跳7次 再向右跳5次再向左跳3次回到原点。
中间必定经过3
用此算法可以经过任意小于p+q的数并且能回到原点
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式