转跳到内容

一个正方形内如何让某种折射方式的斜线段平均最长


推荐贴

如题:假设从正方形ABCD的对角线AC上的任意一点O出发,朝DB方向发出一条射线,这条射线碰到AB边后会朝BC方向移动,碰到BC边后会朝BA方向移动,碰到AC边后会超DB方向移动。问AO/AC=多少时这些图上的斜线段(红线)的平均长度最长?(AO/AC∉{Σ(0or1)×1/2^i(并非是二进制有限小数)},即射线不会碰到ABC三点中的一点)

v2-b69a56bd87ae762921f8748dbd69c254_r.png.bcf19422131ed9379a07c4c79ea75ce4.png

以下为一个思路,但是希望能有人给出更为巧妙的解法。

剧透

目前来说找到的最优的解是AO/AC=1/3或者2/3时,斜线段的平均长度是1/3AC。但是不知道这个解是否是全局最优。实际上目前也稍微有点思路,如果能证明斜线段连续两次落在同一条直角边上不如改变初始位置让它在最后一次“反射”时直接一步到位落在原来连续两次落在同一直角边上时后一次的位置更好。这个以前k次连续反射必不在同一直角边上为假设列出数列求出通项公式后求个导应该就能证明。然后就能推出最优时这无穷次反射应该轮流落在两条直角边上,然后AO/AC(以下简称为p)=1/3就是两次反射后落回原点的一个解。而如果1/4<p<1/3则两次反射后会落回原来的左边(越来越接近1/4,当小于1/4的时候就会连续反射到AB上),1/3<p<1/2时一次反射之后p就会>2/3,由对称性这和p<1/3的情况是一样的。但是感觉这么解实在不太优雅,希望能有什么让人眼前一亮的比较巧妙的解法。

 

,由makuwa修改
注释
骚男 骚男 50.00节操 糖w
链接到点评

我们如果建一个系,然后把这题看成是由x轴,y=1-x,y=1+x约束的情况下,按初始点在每个(n/2^m , (n+1)/2^m)区间上讨论。

我们容易发现在点(2^(-i+1), 0)左右分别会使下一次折射点在x轴左或右,此时若该次出射点横坐标为m(m>0),则竖线长度(对应图中红线)分别为2-2m和2m,可以记作过程f和过程g

这玩意就变成动态规划问题了,通项我不会写,有个特例就是初始横坐标在(1-2^(-i), 1)上时,平均长度是(2^(i+1)-1)(1-x)/(i+1), i >= 0

当然状态和转移方程都搞定了,就请下面的算法大佬来做这dp题喽

————————————

在非1/6和1/2^n处都会有∞个红线;感知一下的话会有一种Σl=1的感觉

,由Haj修改
链接到点评
6 小时前,Haj说道:

在点(2^(-i+1), 0)左右分别会使下一次折射点在x轴左或右

没太看懂这一句

前面那个约束也没看懂,y=1+x的约束是怎么来的用来干什么的?把正方形翻转对称一下吗?但是这里对称后用射线的结论应该不等效于原问题,对称之后要等效于原问题还得是横平竖直的。要想当成射线看得在射到直角边的时候将交点当做另一相同正方形斜边的交点才行,不过这么做我也没看出啥巧妙的规律来。

而dp这个就更奇怪了,这道题里对于某一出发点只有一个结果而没有可以交给我们的选择,这里没有2-2m和2m给你选,只有不同的初始m会对应不同的选择方向。如果从结果逆推首先得定义最终结果,其次从结果逆推的时候dp出来的应该不是最优解。

——————————————————

关于无穷次反射时的期望。假设证明直角边上每一个点的机会是均等的,而这个可以看做是马尔可夫过程,用状态转移方程可以看出每一个点的下一个状态的映射和原先的概率密度函数一样,而假设自洽的条件是假设这个马尔科夫过程能形成一定周期,并且周期中的不同相位某一点机会的平均值与假设相符。同过这一点我们可以看出这个假设起码自洽,至于是否存在其它自洽的假设我不确定,暂时没有想到。如果这个假设是对的的话那期望的斜边平均长度就应该是1/4AC,如果把正方形边长看做是1那就应该是根号2/4,不清楚你说的Σl=1是什么意思。

makuwa在偷偷前往歌姬住处要签名的时候偶然碰到了管家123,被罚款-1节操

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

感觉有个位置能达成路径无限循环……

我题目排除的点除外的位置都能无限迭代,至于要陷入某种无限循环,也有好多的位置,只要它们最后能到达斜边上的三等分点就可以陷入周期为2的循环之中。进入3等分点的方法是从另一个三等分点或者六等分点,而进入六等分点的方法是5/12点或1/12点。。。。。总计有无穷多的点可以最终达成无限循环

makuwa在华山论剑时惨中面目全非脚.-2节操

链接到点评
8 小时前,makuwa说道:

没太看懂这一句

前面那个约束也没看懂,y=1+x的约束是怎么来的用来干什么的?把正方形翻转对称一下吗?但是这里对称后用射线的结论应该不等效于原问题,对称之后要等效于原问题还得是横平竖直的。要想当成射线看得在射到直角边的时候将交点当做另一相同正方形斜边的交点才行,不过这么做我也没看出啥巧妙的规律来。

而dp这个就更奇怪了,这道题里对于某一出发点只有一个结果而没有可以交给我们的选择,这里没有2-2m和2m给你选,只有不同的初始m会对应不同的选择方向。如果从结果逆推首先得定义最终结果,其次从结果逆推的时候dp出来的应该不是最优解。

——————————————————

关于无穷次反射时的期望。假设证明直角边上每一个点的机会是均等的,而这个可以看做是马尔可夫过程,用状态转移方程可以看出每一个点的下一个状态的映射和原先的概率密度函数一样,而假设自洽的条件是假设这个马尔科夫过程能形成一定周期,并且周期中的不同相位某一点机会的平均值与假设相符。同过这一点我们可以看出这个假设起码自洽,至于是否存在其它自洽的假设我不确定,暂时没有想到。如果这个假设是对的的话那期望的斜边平均长度就应该是1/4AC,如果把正方形边长看做是1那就应该是根号2/4,不清楚你说的Σl=1是什么意思。

我其实是偷懒把正方形旋转45度以正方形中心建系然后设对角线长度为2罢了,然后一个个算线长,这里的dp正好是发现两次连续落到同一象限的分类标准,就可以按初始值分类讨论计算下一条直线的长度,不过这个蠢办法大概只能求个近似解吧64018c409cdd0.jpeg

右边像茎叶图一样的是按区间分类的总长,不过通项是真写不出来啊

时间序列什么的不会,我学的数学太朴素啦ww

—————————

6401d46d8ed87.jpeg

南开数学系的同学讲,可以用二进制小数来寻找红线交点在AC上稠密的条件;二进制小数本身也蕴涵了图的生成过程

 

,由Haj修改
注释
骚男 骚男 20.00节操 回复糖w
链接到点评
6 小时前,Haj说道:

这里的dp正好是发现两次连续落到同一象限的分类标准

但还是没看出你这里是打算如何dp的,x并非一个具体的值,比如你图里image.png.fcba3fbe0c227cefb9dc3ca524ea7aa4.pngx∈(1/4,1/2)的时候8x-2与4x-8并没有绝对的大小关系,这里一样还是要分类讨论,然后像你图里把所有情况都算出来也完全不是dp,感觉你这就是横向全部算出来然后比较一遍然后选最好的算下去。这只是没有证明最优性的贪心而已。毕竟首先你就不能保证i=9时的最优解前面的折返过程与i=10时的前九步是一致的。

——————————

至于用有限二进制小数可以表达的初始我一开始在给出题目的时候就排除了:

19 小时前,makuwa说道:

(AO/AC∉{Σ(0or1)×1/2^i(并非是二进制有限小数)}

我一开始就去掉了最终会直接射到B点上最终终止迭代的初始点,顺道一提你这份南开数学系的同学的解答漏洞有一堆。

首先稠密不代表均匀,sinx的值域在0~π上也是稠密的但是它在0~π上的期望并不为1/2。然后At的非稠密条件也并非是靠二进制有限小数即可完全寻找的比方说t=1/3和t=2/3的时候,At就只是两条直线。以及从t=1/3、2/3的上级迭代点(t=1/6、5/6)以及上上级迭代点(t={1/12,7/12}、{5/12,11/12})以及再往前迭代的那些点(不好直接表示,自己推即可)作为t时都是非稠密的。

如果你的那位同学有兴趣的话可以把完整题目和题目下的思路截图或者复制一下发给他,顺道这篇回答也发给他。问问他有没有什么别的想法。

makuwa遇见阿里尼,决定跟着他学打游戏,买游戏被G胖骗走了 -1节操

链接到点评
1 分钟前,makuwa说道:

但还是没看出你这里是打算如何dp的,x并非一个具体的值,比如你图里image.png.fcba3fbe0c227cefb9dc3ca524ea7aa4.pngx∈(1/4,1/2)的时候8x-2与4x-8并没有绝对的大小关系,

首先,那是是4-8x,,其次,二进制小数小数点后第i位能决定图在生成第i+1条红线时是否落到对侧,而给定起始点的二进制值是确定的(无限但是可表示),不过这样迭代还是蠢办法罢了;

然后咱也没打算用二进制有限小数,因为有限小数那玩意就是会糊到B点的;

至于证明稠密性以后拿面积除底边我也觉得不行啊,因为稠密它不等于连续9F69CE84-6075-4199-9354-9C5787FF958F.png.ec9dca7d987164074961b3d8ffdf6e1a.png咱不学数分的也知道,我同学确实也在准备开学考,大概有点糊涂(我明天早八也考试hh)

不过俺寻思有理数能表示成无限循环或有限的二进制小数,这样每个循环后交点坐标应该趋近某个特定模式的;但无理数取值怎么办?

Haj路过听到路过酱的歌声,不小心被路过的鸡仔绊倒,受到了路过酱的赔偿金5节操

链接到点评
1 小时前,Haj说道:

首先,那是是4-8x,,其次,二进制小数小数点后第i位能决定图在生成第i+1条红线时是否落到对侧,而给定起始点的二进制值是确定的(无限但是可表示),不过这样迭代还是蠢办法罢了;

然后咱也没打算用二进制有限小数,因为有限小数那玩意就是会糊到B点的;

至于证明稠密性以后拿面积除底边我也觉得不行啊,因为稠密它不等于连续9F69CE84-6075-4199-9354-9C5787FF958F.png.ec9dca7d987164074961b3d8ffdf6e1a.png咱不学数分的也知道,我同学确实也在准备开学考,大概有点糊涂(我明天早八也考试hh)

不过俺寻思有理数能表示成无限循环或有限的二进制小数,这样每个循环后交点坐标应该趋近某个特定模式的;但无理数取值怎么办?

嗯,打错了,我指得也是4-8x,8x-2与4-8x在这个区间上没有绝对的大小关系,这里就不能贪心。

对啊,就是有限二进制小数会糊到B点,但是无限二进制小数绝对不会糊到B点,所以题目中就是说了排除有限二进制小数。

连续也不能拿面积除,就是个落点概率不一样的问题,一块区域的权重不一样。我举的那个sinx的例子就是,不能因为它的值域是0~1上的连续区间就认为它在x在(0,π)区间上随机取值时平均值为1/2。

只要不是有限二进制小数和我上面说的1/3相关的那几个点,最后坐标都不会趋近于某个特定值,最多在多个特定值之间往复波动。无理数就是完全没有波动周期(因为n个周期之后肯定是一个有理数+有理系n数不同的这个无理数的n倍)。但是讨论这些都不影响题目讨论的内容。我问的是期望最高的取法,是否能取到平均>1/3AC的初始点,以及是否有方法证明这种取法是最优的。

链接到点评
7 分钟前,makuwa说道:

连续也不能拿面积除,就是个落点概率不一样的问题,一块区域的权重不一样。我举的那个sinx的例子就是,不能因为它的值域是0~1上的连续区间就认为它在x在(0,π)区间上随机取值时平均值为1/2。

哦,咱理解不一样,您想着的是离散数学,我想着是积分后除π得到平均值2/π这个连续问题;不过这题显然无法不是连续数学研究的范围

16 分钟前,makuwa说道:

只要不是有限二进制小数和我上面说的1/3相关的那几个点,最后坐标都不会趋近于某个特定值,最多在多个特定值之间往复波动。

我也是觉得有可能在特定值附近振荡才提了一嘴

26 分钟前,makuwa说道:

我问的是期望最高的取法,是否能取到平均>1/3AC的初始点,以及是否有方法证明这种取法是最优的。

现在的问题是,每个给定的初始值都有明确的对应值,只是找不到这个单值函数的解析式,所以我还是希望复变函数能解决这个问题… …

Haj不吃不喝三天三夜只为“汉化”某悬赏游戏,搞定后发现居然是要翻译成俄语.-3节操

链接到点评
3 小时前,Haj说道:

您想着的是离散数学,我想着是积分后除π得到平均值2/π这个连续问题

:1348558391_SSB(2):不知道你是怎么得出这个结论的。我只是指正你那同学“证明稠密并不代表可以直接看面积”的错误后,你说“你知道稠密不行要连续才能直接看面积”,我再指正“连续也不能直接看面积,要考虑概率密度函数”而已。这一思路本身不就是在将无穷多的稠密的离散变量给看做是连续变量的思路吗?单看有限的过程它是离散的,考虑无穷的过程可以将其当做是连续的,这两个本身并不矛盾。给你举的sinx的例子不也是连续的吗?这就像是你说火箭应该靠风吹着上天然后我说风力不足以支撑起火箭的重量然后你告诉我我考虑的是质量问题你考虑的是力的问题一样,用莫名其妙的分类方式避开问题的重点。这里问题的重点在于你没法保证t是均匀分布的,所以不能直接看图像的面积,要看t对应的函数值和t的概率密度函数的积分。就像是刚刚那个例子,如果我通过投骰子来决定x的取值,如果投到1就在(0,π/4)的区间上随机取一个点,投到2及以上就在(π/4,π/2)的区间上随机取一个点。这时候我用于取点的区间任然是连续的,但你还认为我一直这么取下去得到的sinx的平均值还是2/π吗?这里的图像面积本身并未包含概率密度信息,你没法保证t落在AC上某一区间的概率和这个区间的长度的比值是一个定值,所以不管连不连续都不是看这里的面积,明白了吗?

4 小时前,Haj说道:

不过这题显然无法不是连续数学研究的范围

至于你的这一句我更倾向于你是把“显然不是连续”错打成了“显然无法不是连续”。不然你给我的感觉就像是在说“火箭显然无法不靠风力做出麻婆豆腐”一样。我在思考的是“最优策略”(上天)的问题,你在回答的是“求随机一点的期望”(做麻婆豆腐)的问题。你要是支持风力的思路,那虽然抽象但不是不可能,你要是能把火箭的整体重量降到风也吹得起来(求出概率密度函数算出任一初始点出射以后的期望)。但是你要是说“显然无法不用风力”——直接将核动力(几何方法)和化学燃料动力(列数列求通项)排除在外,除此以外什么结果都没有的话是不是有点。。。

4 小时前,Haj说道:

所以我还是希望复变函数能解决这个问题

其实本身这一题的普通解法我上面已经写出来了,不过还不够让人眼前一亮,所以想来看看有没有谁能给出巧妙的思路。不过我现在倒是有了一个比较巧妙且严谨的证明思路,直接从平均1/3AC的特定解入手通过假设和反证在不用太多计算的前提下完成证明。等我把图片文字啥的编辑完了以后再发出来吧

链接到点评
55 分钟前,makuwa说道:

:1348558391_SSB(2):不知道你是怎么得出这个结论的。我只是指正你那同学“证明稠密并不代表可以直接看面积”的错误后,你说“你知道稠密不行要连续才能直接看面积”,我再指正“连续也不能直接看面积,要考虑概率密度函数”而已。这一思路本身不就是在将无穷多的稠密的离散变量给看做是连续变量的思路吗?单看有限的过程它是离散的,考虑无穷的过程可以将其当做是连续的,这两个本身并不矛盾。给你举的sinx的例子不也是连续的吗?这就像是你说火箭应该靠风吹着上天然后我说风力不足以支撑起火箭的重量然后你告诉我我考虑的是质量问题你考虑的是力的问题一样,用莫名其妙的分类方式避开问题的重点。这里问题的重点在于你没法保证t是均匀分布的,所以不能直接看图像的面积,要看t对应的函数值和t的概率密度函数的积分。就像是刚刚那个例子,如果我通过投骰子来决定x的取值,如果投到1就在(0,π/4)的区间上随机取一个点,投到2及以上就在(π/4,π/2)的区间上随机取一个点。这时候我用于取点的区间任然是连续的,但你还认为我一直这么取下去得到的sinx的平均值还是2/π吗?这里的图像面积本身并未包含概率密度信息,你没法保证t落在AC上某一区间的概率和这个区间的长度的比值是一个定值,所以不管连不连续都不是看这里的面积,明白了吗?

至于你的这一句我更倾向于你是把“显然不是连续”错打成了“显然无法不是连续”。不然你给我的感觉就像是在说“火箭显然无法不靠风力做出麻婆豆腐”一样。我在思考的是“最优策略”(上天)的问题,你在回答的是“求随机一点的期望”(做麻婆豆腐)的问题。你要是支持风力的思路,那虽然抽象但不是不可能,你要是能把火箭的整体重量降到风也吹得起来(求出概率密度函数算出任一初始点出射以后的期望)。但是你要是说“显然无法不用风力”——直接将核动力(几何方法)和化学燃料动力(列数列求通项)排除在外,除此以外什么结果都没有的话是不是有点。。。

其实本身这一题的普通解法我上面已经写出来了,不过还不够让人眼前一亮,所以想来看看有没有谁能给出巧妙的思路。不过我现在倒是有了一个比较巧妙且严谨的证明思路,直接从平均1/3AC的特定解入手通过假设和反证在不用太多计算的前提下完成证明。等我把图片文字啥的编辑完了以后再发出来吧

image.png.ecf3f6af228d768373eb79e81f542a6b.png
易知,当初始点为对角线三等分点时红线平均长度为AC/3
image.png.e4fc42b9f838581a0a64eb7fb21f400a.png

情况一:对于线段AP和线段CQ上的任意一点T,显然它抛出的线段image.png.3e88ddb76c8c4077447853250777eb1b.png

image.png.dd1a5e1fe33e9eae5bdc4490408b2513.png

情况二:对于线段PQ内的任意一点T1,都有它在触壁“折射”之后落点必然落在AP或CQ上,这里取T1在PO上的版本,此时,延迟CB,平移线段image.png.b4fe467279c619e7096184c1a388a5f6.png 至图中对应颜色的虚线位置,显然,image.png.a88735fdc7e5c1f405852279ab258353.png 即线段image.png.e2233aad394af0b11602d99b7b99efeb.png的平均值<AC/3.

而在图中除了经由PQ两点抛出的线段外的所有初始点抛出的折线段中的斜线段都可以看做是数种情况一和数种情况二的组合,而情况一和情况二内部的斜线段平均值都<AC/3,它们在平均一下得到的总的斜线段的平均值肯定也<AC/3。故三等分点对应的平均长度为AC/3的斜线段是此规则下可无穷迭代的线段中斜线段平均长度的最大值。

 

这种方法怎么说呢,只是一个让人感觉之前怎么就没有想到的中规中矩的方法,还是用特殊值凑的,感觉不够优雅与让人眼前一亮。不过比起代数方法做还是优雅了许多,同时,依旧期待着更好更灵活的想法。

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

重要消息

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