转跳到内容

[数学算法挑战]发一个原创的数学(?大概?)问题


只显示该作者

只有该作者的内容显示中。 返回到主题

推荐贴

小ma每天放学骑车回家的时候回经过一条U型环道,如图:

image.png.74cae90f76985e2e347623ea43605f63.png

小ma现在所在的位置是从学校方向回到家的必经之路,那么此时小ma有两条路可以选择,第一条是直走到东侧路口左转直接回家,另一种是在当前路口左转通过弯道回家,(该车道只有非机动车,不用担心交通安全隐患,小ma可以在被黑线围起来的区域外的与自己同侧的任意区域上移动)问:

(1).小ma应该走那条路更近呢?(答案:先左拐)

以下为本问答案解析

剧透

在图中的情况下,先左转会比直走到U型道另一入口左转更近,理由如下:

image.png.7512332c927295349a4ca0ede9314088.png

如图,如果走左侧,小ma完全可以按照图中红线轨迹相似的轨迹到达自己的家。容易证明:红线轨迹的路径长度小于虚线矩形框的长宽之和(这里可以先证一个引理:我们可以把由一个点到另一个点的路径根据这两点的连线方向最为横轴正交分解,分解后横轴代表这段路对到达目的地的贡献,而已知最终能到达目标点的情况下任意分路段的纵轴分量只和为0,可以不做考虑。而单位长度路径对到达目的地的贡献越大,到达目的地的路径总长度就越短。我们可以把一整条路径给分成无数段可以看做是直线的极小段路径,易证这段路径方向与起始地——目标点方向夹角越小,单位长度的此段路径的贡献越大。当我们看向这个矩形中的红线的时候,我们就会发现红线中任意一段极小路径和小ma——家方向的夹角都小于长方形的长或宽和此方向的夹角,也就说红色线路对到达目标的贡献始终更大。通过这一引理也可以证明一个定理:若矩形框内存在一条由左下角至右上角的路径,路径任一位置的方向都指向第一象限。则这条路径的长度小于矩形的长宽之和。)而蓝色路线首先至少要到达水平箭头的目标点。此时,就算小ma的目标点是可以通过直线连接到达且距离比家位置更近的家'(绿星)的位置,小ma需要走的路径长度也大于左边虚线框的长宽之和了,所以可以判断红线路径长度一定小于蓝线路径长度。

小ma想明白该走那条路线之后,天天上下学都走这条路。久而久之,小ma心中有浮现了另一个问题:

(2).这条路这么宽,我应该朝着什么方向什么路径走能在更短的距离内回到家呢(求从小ma位置到家的最短路径)?

image.png.9093d582656b059caf843921447be910.png

剧透

大家都知道的一条公里是,平面上两点之间直线最短。所以对任意一条路径上的任意两个点,如果这两点之间存在直线但他们之间的路径并非直线,那么直接用直线将二点链接来替换原本的轨迹将能让总路径达到最小。所以如图:

image.png.3637e2c0e6da215cca7102348daba69f.png

如果红蓝射线所围的区域内存在路径中一点,那么如果此路径为最短且它在蓝色区域内,那么它与小ma之间的连线必为直线,同理,它在红色区域内则其从此点回家的最短路线必为直线。

而当小ma的路径经过红或蓝区域的区域内一点(黑点)时,如图:

image.png.678d9ae6bf9a35557bf546e24824f31e.png

则必然存在蓝色区域内的路径上一点与蓝色区域边界交点(绿点)和红色区域内路径上一点与红色区域边界交点(黄点)。

∵路径长度:蓝——黑——绿>蓝——绿(——代表连接两点的直线路径)

∴路径长度:蓝——黑——绿——红>蓝——绿——红

即存在更短路径“蓝——绿——红”小于当前路径长度

同理也存在路径“蓝——黄——红”小于当前路径长度

所以最短路径必不经过红蓝区域内任意一点(边界除外)

那么此时的最短路径可能的范围已经极大地缩小了,它必须沿着蓝色区域或红色区域靠东南方的边界或此边界以东南的方向行走。而如图:

image.png.d87e9f9a6b177b6d8792f1acb4e19412.png(图6)

考虑到红蓝区域边界均是直线可达(实际上就是不被半圆弧遮挡)的最大范围,故其绝对与U型弯道的半圆相切。所以图(6)中的红蓝区域内如果存在路径上的点,则路径必通过红蓝区域边界,故而与上述理由相同,存在可直达的更短路径。所以实际上最短路径已经大致确定了,最终抱有不确定选择的便是黄色区域内的路径。我们对黄色区域内任意路径,如果它并非贴着圆弧则在离开圆弧的路径内必然存在两点之间可以用直线相连,不断地用两点直接相连取代原有路径,最终路径便会收缩为贴着圆弧的路径。

 

然而这道题有一个更为巧妙的解法,这也是我出这道题的意义所在:

假象有一条足够长的绳子,一端绑在小ma的初始位置,而让人在家的位置拉紧绳子。只要人有拉动绳子,那么被拉出的绳子就越长,留在U型区域内的绳子总长度就越短。最终当人无法拉动的时候这个绳子的形状就是最短路径。通过受力分析可知绳子拉到最终状态便是从蓝点到小圆弧切线的切点与蓝点相连的直线——贴着小圆弧绕行——从红点到小圆弧切线切点开始到红点的直线。这一段路。这一方法不仅可以运用于这一题设情景。对任意的复杂迷宫(充满任意曲线而非横平竖直、具有多种达到目的地的路径)。我们可以将连通部分看做是1块,对某一块应在绳子上方还是下方做排列组合,然后拉动绳子,测得的迷宫内绳子长度最短的情况便是最优选择下的最短路径。

注释
骚男 骚男 60.00节操 糖w
链接到点评
1 小时前,kq586说道:

考虑过于复杂了:kl:

首先两点之间直线最短排除走圆弧的路线

第一问:2.png.604f066c0c5db9de33408f162a9ba680.png

两条直道都是一样的距离,存在差距的只有1号线走的红色和2号线走的蓝色+黄色,组成三角形就看得很明白了

 

第二问:3.png.bbeab0d2e29421d319da5c83ffa4cd86.png

做两条切线找到出发点和终点到圆弧的最短距离,其他的直线路径都只会和这条路拼成三角形

走圆弧短还是走直线短就得去比较tan(圆心角/2)和(圆心角/2)/180° * π  了

关于第一问主要是考虑到还有红线可能会被靠内侧的半圆弧遮挡的情况所以必须考虑曲线路径。

而第二问我们的结论差不多,我主要的篇幅是在证明为什么所有路线要么和蓝色且线段相交要么和红色切线段相交,也就是你说的“其他的直线路径都只会和这条路拼成三角形”然后我觉得走圆弧短还是折线段短这应该是一个可以无穷迭代的微分的问题,你说的比较tan和弧长只是两切线交点和切点的折线段和圆弧长度的关系,并不能排除在这区域内的任意一种路径。我觉得这里要排除所有路径还是任意两点间是否存在可达直线相连较好

链接到点评
于 2022/9/14 于 PM6点42分,kq586说道:

红线被挡但是2号的黄线不会,2号能走的所有路线最后都能从1号里头找到一条直线组成三角形。只是比较两条路线长短这样就够了。

 

 

第二问设起点为A,两条切线交点为B,区域内任取一点为X

4.png.996c6d516d7b35c32c713ddda99c2b98.png

两条切线可以把X能选择的位置分为四个区域

①③④区域都会让路径与内圈的圆相交

②区域无论哪一点都会有AX+XB>AB

 

信我,真没那么复杂要无穷迭代:mx007:

红线被遮挡而黄线不会那么红黄蓝三线就不能组成像上面一样的三角形了。不理解你说的“2号能走的所有路线最后都能从1号里头找到一条直线组成三角形”的证明过程。

第二问的关键并不在于图中的1234个区域,而重点在于

image.png.edc6d26d3acfa3b158b6776eb46acf21.png

这张图画的切线交点和切线与圆的切点围城的黄色区域,在这区域内要证明任意一条从蓝线切点到红线切点的路径长度都大于这段圆弧的长度。而无穷迭代指得就是当路径上的点并不贴合弧线的时候在偏离弧线的部分找弧上一点做切线一定会交路径于2点,而这段新切线加上那两点沿原路径到起点/终点的距离一定小于原路径的总长度。而因为切线也同样无法贴合圆弧,所以还需要反复在圆弧上找切点作切线,就是我说的无穷迭代。直到最后逼近圆弧。

makuwa收和谐资源时被小萝莉围观良心发现失去-2节操

链接到点评
5 小时前,kq586说道:

唔,那我说详细严谨一些

 

过终点家做到圆内弧的两条切线,做平行与底边路的直线蓝线,过黄线切点做垂直于底边路的直线绿线

5.png.0f280252d1f844ba3430f20e90f331c5.png

2号线距离一定大于+绿+绿线是有可能在圆弧内部的

三角形两边和大于第三边 有 <+

+绿 < ++绿

这样就清楚了吧

 

第二问是我的问题,没看完你的证明,我以为你只是证切线外路径来着:mx028:

你得出圆弧最短的结论是错的

你证明默认了一个前提条件,圆外一点到圆两切线的长度大于圆弧的长度

两切线长之和是 2*r*tan(圆心角/2)

圆弧长度是(圆心角/180°)*r*π    

切出来的圆心角足够小走切线会比圆弧短

对于这个问题要么量角器直接得出结果

要么就两个区间解

 

image.thumb.png.6e0fb63468b3e6bf5704f250e321d7ad.png

我指得是像这样,当家到半圆切线与半圆的底所在的直线(蓝线)在U型弯内无交点的时候1号线中就不存在你所说的代替黄线+蓝线的红线,一号线一样必须要走折线。

 

而第二问可以肯定两切线长之和大于圆弧长度,证明如下(采用弧度制):

对tanθ求导即tanθ'=sec²θ>1

又θ=0时r*tanθ=r*θ=0

θ∈(0,π/2)时(r*tanθ)'=r*sec²θ > r,(r*θ)' = r

即在(0,π/2)r*tanθ的增量始终大于r*θ

∴θ∈(0,π/2)时r*tanθ>r*θ

这就是完全不用量的,或者直接从几何上看:

image.png.52b20d570de0ee36a38c17b50ac8a1e5.png

如图在一个单位圆上做一条与x轴夹角为θ的射线(绿虚线),此时扇形面积(蓝色区域)=r²*θ/2(θ/2π个圆形的面积)

x轴、射线y=x*tanθ、直线x=1围成的三角形区域的面积(蓝色区域+黄色区域) = 1(三角形在x轴上的直角边的长度)*tanθ(三角形的另一条直角边长度)*1/2

显然只要θ∈(0,π/2)三角形面积就大于扇形面积。

对你所说的

两切线长之和是 2*r*tan(圆心角/2)

圆弧长度是(圆心角/180°)*r*π    

换成弧度制其实就是比较2*r*tanθ和(2θ)*r的问题,就是上面说的比较tanθ和θ的问题。

注释
骚男 骚男 30.00节操 糖w
链接到点评
11 小时前,kq586说道:

第一问补个补充情况吧,这样更容易看

1.3.png.762ab5582d52818c84a7775733233283.png

可能我上面话的不够标准,如果是这样呢?

image.png.a6c74fc00a7e6648a12ebab168734d54.png

makuwa在动漫资源区买下了无路的本子,结果在回家路上被警察叔叔查获,失去了-3节操

链接到点评
15 小时前,kq586说道:

 

1.4.png.806c7c88bbcf6b488f0e2a78e8c1808d.png

 

这特殊情况红蓝平行了做不出三角形,可是X方向上的和Y方向上的直接对过去不是更一目了然了……

顺便一提终点的位置再模糊下去你自己的推论也要站不住脚了,那时这个问题得重头讨论:mx043:

是啊,终点位置再往下实际上都不是推论的问题了,这个问题的答案都有可能改变了。所以我的推论就是为了包含你说的这种特殊情况和能直接通过走直线构建三角形的情况才假设的。而你说的“对任何家的位置1号路线都能找到三角形”是比“1号线路中必然存在一个比2号线路中所有线路都要短的线路”更弱的一个条件。而在只知道大致位置而不知道具体相对位置的数值的时候我的推论是“1号线路中必然存在一个比2号线路中所有线路都要短的线路”的充要条件。可能是我一开始画的图不够标准,而让你忽视了这个特殊情况。因为现实中我思考这个问题的时候实际情况是像我最后画的这个图这样差不多的,家门口一出来是看不到那条直道的入口的,所以我当初构想的是这种证明方法。

链接到点评
  • 骚男锁定了本主题
游客
此主题已关闭。
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款