等高线模式:解决极大极小问题的另类策略

    最近在看Pólya的《数学与猜想》,读到了一些很有意思的东西,在这里和大家分享。
    我们首先来看一道很火星的题目:A、B两点在已知直线的同侧,请在直线上找出一点C使得∠ACB最大。可能大家都知道这个该怎么做,但这个解法到底是怎么想到的呢?《数学与猜想》提到了这样一种看法:
      
    首先,我们需要确定,这条直线上的确存在一点,使得这个角度达到最大。我们很容易观察到,这个动点往左移(可以一直移动到BA的延长线与直线的交点),这个角度会慢慢变小;同时,动点不断往右移时角度也会慢慢变小(在无穷远处角度为0)。可以想到,角度大小的变化可以用一个凸函数来表示,这段函数上一定存在一个最大点。现在任意在直线上取一点C,你怎么才能说明∠ACB是最大或者不是最大?一个比较直观的方法是,如果你取的C点不能使角度达到最大,那么这条直线上一定存在另一个点C',使得∠ACB=∠AC'B。分析到这一步,问题终于有了眉目,因为有一个大家都很熟悉的东西恰好与角度相等有关——同一段弧所对的圆周角总是相等。过点AB作一系列的圆,那么同一个圆周上的所有点对AB的张角都是一样大的。我们看到,这些蓝色的线条与直线的交点都是成对出现,换句话说ABC三点确定的圆与直线的另一个交点就是那个C'。但有那么一个点非常例外:在这无穷多个圆中,有一个圆恰好与直线相切。这个切点只出现了一次,它就是角度大小的极大值。

    真正的数学家会从这个简单的题目里看到一些更深的思想。我们可以把这个图任意的扭曲,从而得到这样一个有趣的结论。假设我和MM在野外探险,地形是任意给定的,我们的行动路线也是任意给定的。现在我有一张非常精确的等高线地图,我把我们的路线画在地图上,那么整个旅途中所到达的最高点和最低点在地图上的什么位置?仔细思考等高线的定义,我们立即想到:路径穿过等高线的地方肯定不会是最高点或最低点,因为穿过一条等高线即表明你正在爬上爬下。因此,达到最高点或最低点的地方只能是等高线与我的路线相切的地方。这给我们一个启发:我们可以用这种模式来解决很多极大极小问题。我们把所有可能的结果的分布情况用等高线表示,而实际允许的初始条件则被限制在了一条路径上,那么最优解必然是这条路径与某条等高线的切点。用等高线模式来解释刚才的问题将变得非常简单:图中的蓝色线条就是角度大小的“等高线”,在直线上取得极值的时候,等高线恰与直线相切,其它情况下角度大小都在“变化进行时”。
    我们再来看三个有趣的例子。在第一个例子中我们将解释为什么点到直线的距离以垂线段最短,第二个例子则将探究为什么所有的圆内接n边形以正n边形最大。在第三个例子里我们将提到一个与椭圆有关的神奇性质。

      

    上面这个图就是到定点距离大小的等高线图。我们可以立即看到,等高线就是一个个的同心圆。与已知直线相切的那个同心圆确定了直线到给定点距离最短的位置,而圆的半径与对应位置上的切线垂直,这就说明了点到直线的距离以垂线段最短。

      
    下面我们考虑圆内接多边形的某个顶点X。这个顶点两旁的点分别是A和B。那么整个多边形被分成了两部分:三角形AXB,和剩下的那一大块多边形。如果我们只移动点X,这只会影响三角形AXB的面积,对剩下的部分没有影响。X在不同位置所得到的三角形面积不同,在图中我们用蓝色的等高线来表示这个面积值的分布情况。由于等底等高的三角形面积相同,因此我们的等高线是一系列互相平行的直线。点X只能在一段圆弧上取,当△AXB达到最大时X必然落在圆弧与某条直线相切的地方,显然此时AX=BX。换句话说,只要圆内接多边形里有长度不等的邻边,那么这个多边形的面积一定可以变得更大。再换句话说,只有所有边都相等了,面积才可能达到最大。这就说明了,所有的圆内接n边形以正n边形最大。

    我相信你已经对这个方法非常熟悉了,因此最后这个例子我就不画图了。在第三个例子中,我们将考虑一个和光学有关的性质。给定一条直线和直线同侧的两点A、B,那么直线上一定有一点C使得AC+BC达到最小。这个点C是一个以A、B为焦点的椭圆形等高线与直线的切点。固定点A和点B,适当调整直线的位置,结论始终成立。还记得Fermat原理吗,光从一点到另一点总是沿着光程最短的路径来传播。仅考虑反射定律,这个结论很显然。也就是说,A->C->B这样的光线传播路径完全遵循光的反射规律。嘿!我证明了这样一个富有传奇色彩的结论:椭圆形从一个焦点发射出来的光线总会反射到另一个焦点。

做人要厚道
转贴请注明出处

函数上某一点导数为正,该点邻域不一定形成单增区间

    给出一个连续函数,某一点上的导数为正说明函数在这一点是上升的,换句话说函数从左边充分靠近该点时函数值总小于这个点,从右边靠近该点时函数值总大于这个点。但这并不等于说这一点左右是一个单增区间,也就是说该点左右任意小的邻域内函数都不是单调递增的。你能找出这样的函数来吗?

    昨天数学课上,我学到了一个比较牛B的东西:函数上某一点导数为正,该点邻域不一定形成单增区间。虽然左边的点都比该点低,右边的点都比该点高,但这并不能说明左边和右边各自都是单增的。这样的函数确实存在,而且并不是那种很怪的函数,仅仅是一个简单的初等函数:f(x) = x + 2x^2*sin(1/x)。由于x=0时函数没有定义,我们规定f(0)=0。按照导数的定义,函数在x=0时的导数值为
   Limit[ (f(0+Δx)-f(0))/(Δx-0), Δx->0 ]
= Limit[ f(Δx)/Δx, Δx->0 ]
= Limit[ 1 + 2Δx*sin(1/Δx) , Δx->0 ]
= 1

    这说明函数在x=0处的导数确实是正的。当x≠0时,按照求导法则可以求出f'(x) = 1 – 2*cos(1/x) + 4x*sin(1/x)。当|x|充分小时,最后一项可以忽略不计;此时只要1/x恰好等于2πn (n为整数),那么f'(x)保证是负的。这就告诉我们,x=0左右任意近的位置都存在导数为负的情况,这样不管邻域范围多小总能找到一个函数值在减小的地方。
    其实,看一下f(x)的函数图象,你会立即明白这是怎么回事。这个函数越接近原点抖动频率越快(到原点时“周期”无限小),同时振幅也越小(到原点时振幅为0,这样可以保证导数存在);但这个函数总的来说呈上升趋势。因此,这个函数才有我们前面提到的奇怪性质。

07年NOIp模拟赛by Matrix67 解题报告

Problem 1: Matrix67的情书(二)
    大家都知道,看一个数是否能被2整除只需要看它的个位能否被2整除即可。可是你想过为什么吗?这是因为10能被2整除,因此一个数10a+b能被2整除当且仅当b能被2整除。大家也知道,看一个数能否被3整除只需要看各位数之和是否能被3整除。这又是为什么呢?答案或多或少有些类似:因为10^n-1总能被3整除。2345可以写成2*(999+1) + 3*(99+1) + 4*(9+1) + 5,展开就是2*999+3*99+4*9 + 2+3+4+5。前面带了数字9的项肯定都能被3整除了,于是要看2345能否被3整除就只需要看2+3+4+5能否被3整除了。当然,这种技巧只能在10进制下使用,不过类似的结论可以推广到任意进制。
    注意到36是4的整数倍,而ZZZ…ZZ除以7总是得555…55。也就是说,判断一个36进制数能否被4整除只需要看它的个位,而一个36进制数能被7整除当且仅当各位数之和能被7整除。如果一个数同时能被4和7整除,那么这个数就一定能被28整除。于是问题转化为,有多少个连续句子满足各位数字和是7的倍数,同时最后一个数是4的倍数。这样,我们得到了一个O(n)的算法:用P[i]表示前若干个句子除以7的余数为i有多少种情况,扫描整篇文章并不断更新P数组。当某句话的最后一个字能被4整除时,假设以这句话结尾的前缀和除以7余x,则将此时P[x]的值累加到最后的输出结果中(两个前缀的数字和除以7余数相同,则较长的前缀多出来的部分一定整除7)。
    上述算法是我出这道题的本意,但比赛后我见到了其它各种各样新奇的算法。比如有人注意到36^n mod 28总是等于8,利用这个性质也可以构造出类似的线性算法来。还有人用动态规划(或者说递推)完美地解决了这个问题。我们用f[i,j]表示以句子i结束,除以28余数为j的文本片段有多少个;处理下一句话时我们需要对每一个不同的j进行一次扫描,把f[i-1,j]加进对应的f[i,j']中。最后输出所有的f[i,0]的总和即可。这个动态规划可以用滚动数组,因此它的空间同前面的算法一样也是常数的。
    如果你完全不知道我在说什么,你可以看看和进位制同余相关的文章。另外,我之前还曾出过一道很类似的题(VOJ1090),你可以对比着看一看。
    另外,非常抱歉地告诉大家,这道题的最后一个数据是错的。这个数据的第一个句子是一个空句子(感谢Ai.Freedom的提醒)。很多第一题只得了90分的好同志估计都是由于我的失误造成的,这里再次表示歉意。如果去掉最前面的那个问号,输出应该是19511110。

Problem 2: 送给MM的生日礼物
        
    我们用f[i,j,k]表示以第i行第j列的格子为右下角,边长为k的正方形是否符合要求。要想f[i,j,k]=True,首先必须满足f[i-1,j-1,k-2]为True(灰色部分满足要求)。另外,我们还需要保证图中两块蓝色区域相等,两块绿色区域相等,并且这四个区域自身还必须是对称的。由于动态规划的状态已经是三方的了,因此判断后面的这些条件必须在常数时间里完成。为此,我们可以在动态规划前进行以下6个预处理:

以同列不同行的两个格子(i,j)和(i',j)为右端点,同时向左扩展可以得到多长的相等区域
以同行不同列的两个格子(i,j)和(i,j')为最底端,同时向上扩展可以得到多长的相等区域
以格子(i,j)为中心,向左右扩展可以得到多长的对称区域
以格子(i,j)为中心,向上下扩展可以得到多长的对称区域
以两个横向相邻的格子(i,j-1)和(i,j)为中心,向左右扩展可以得到多长的对称区域
以两个纵向相邻的格子(i-1,j)和(i,j)为中心,向上下扩展可以得到多长的对称区域

    上面的每个预处理都可以在三方的时间里完成,动态规划的决策降到常数级别,因此总的复杂度还是三方。

    同样地,这也只是我出这道题的本意。我事先已经想到,这道题应该还有很多其它的算法,只是没想到会有那么多。一个比较容易想到的算法是,执行与上面相同的预处理后,枚举某个格子(或某个交叉点)为中心,向外一层一层地进行扩展。虽然这样的复杂度仍然是三方的,并且与前面的算法实质相同,但它的效率显然更高,因为你可以在无法再向外扩展时停止最里面的那个循环,继续枚举下一个中心点。
    同样是枚举正方形的中心点,只使用上面的后4个预处理也可以解决这个问题。我们可以在线性的时间内找出,以某个格子(或交叉点)为中心的最大的合法正方形。假如这个最大的正方形边长为k,这相当于我们同时找到了(k+1) div 2个正方形来。至于如何找到这个最大的正方形,还是留给大家思考吧。
    Cockhorse想到了一个非常巧妙的算法,预处理结束后它可以在常数时间内判断任一个给定的小正方形是否满足题目要求。用f[i,j,k]表示,以第i行中(i,j)及其右边相邻的k-1个格子(共k个格子)来作为底边,所能得到的左右对称的矩形其最大高度是多少。则当f[i,j+1,k-2]为True且(i,j)格与(i,j+k-1)格花色相等时f[i,j,k]=f[i-1,j,k]+1(否则f[i,j,k]=0)。同样地,再用g[i,j,k]表示以(j,i)..(j+k-1,i)作为右边界,使矩形上下对称的最大宽度。这样,判断任意一个正方形是否满足题目要求,只需要检查它的底边和右边能够产生的最大对称区域是否可以覆盖该正方形即可。
    当然,这道题目还有很多其它的算法,这里就不一一列举了。

Problem 3: 流言的传播
    给定一个图,把图中所有点构成的点集叫做U,另指定一个不等于全集的子集S,那么所有一个顶点在S里另一个顶点在U-S里的边就叫做S点集的“割边”,因为去掉所有这样的边后S集将孤立出来。这道题就是需要你找出一个边集E,使得不管S集是什么,对应的割边中权值最小的那一条一定在边集E中。这样的边集肯定是存在的,比如所有边构成的集合就是一个满足条件的边集。这道题希望你找到的边集E里所含的边尽可能的少。
    一个错误的贪心法是,去掉每个点的邻接边中权值最小的那一条。这种算法显然不对,比如下面就是一个鲜活的反例:

o—–o—–o—–o
   2     3     1

    在上图中,每个点的邻接边中权值最小的不是1就是2,这样的话中间那条边就被保留了下来,于是令S集为左边两个点(或右边两个点),割边仍然一条不少。很容易想到,要想让任意S集的割边中权值最小的被去掉,首先得保证边集E连通了所有的点,否则令S等于任一连通分量,边集E里都不会包含任何一条割边。这样,边集E至少要有n-1条边。
&n
bsp;   考虑到最优解至少是n-1条边,这n-1条边必须连通所有的点,而所选边的权值都应该很小,于是想到最后的答案很可能就是最小生成树。现在假设我们已经选择了某些边,这些边形成了若干个连通分量。考虑所有连接两个不同的连通分量的边(两顶点不在同一连通分量的边)中权值最小的一条,那这条边必须要选,否则令S集为其中一个连通分量,题目条件就不能达到了。这不就是Kruskal算法吗?
    且慢,我们还没有证明,对任意一个S集,最小生成树都符合条件。证明其实很简单,假设权值最小的割边e不在最小生成树E中,添加割边e将形成一个回路。这条回路将从S集的某个点出发,经过e跑到U-S里,最后必须还要回到S集。回到S集必然要经过另一条割边e',而显然e'>e(因为e是权值最小的割边,且题目说了没有权值相同的边),于是边集E+{e}-{e'}就成了更小的生成树。

Problem 4: 表白机器人
    第四题是整个模拟赛中最简单的题,它不需要你构造任何算法,你只需要按照题目意思进行模拟即可。和去年的NOIp一样,纯粹考编程能力的题目并没有放在第一道题的位置上。这提示大家拿到题目后要先看完所有的题,特别是看到最后一道题时千万别慌,很可能把它的衣服扒光了一看,发现它居然是一道赤裸裸的送分题。
    为了加快速度,先预处理出一个数组wall[i][j][k],表示第i行第j列往k(1<=k<=4)方向上走是否走得通。然后枚举所有可能的命令序列,模拟机器人的行走过程,看它是否能到达终点。在模拟过程中,你需要用一个数组hash[i][j][k]表示机器人曾在序列的第k个命令后到达第i行第j列的位置,并在模拟过程中不断更新hash数组;当某一次命令后机器人还没走到右上角,而对应的hash值已经为True了,则机器人的行动将从这里开始循环,永远也到不了右上角了。
    虽然这道题不需要任何剪枝,但我还想再说一句。这道题有一个非常有趣的剪枝:命令序列的第一个指令只能是U或R,最后一个指令也只能是U或R。大家想想这是为什么。

趣题:等腰直角三角形与勾股定理形式的条件

    
    等腰直角三角形ABC,斜边BC上有两点M、N 满足BM^2 + NC^2 = MN^2。求证:∠MAN为45度。这个图形最早出现在2001年罗马尼亚数学奥赛的一道题目中。
    看答案前我先说点别的事……有多少网友住在北京?这次清北还在那个地方么?假期我没事干,想和大家一起聚一聚,吃个饭,喝个夜啤酒什么的……不知道为什么,最近酒瘾特别大。
    答案在下面。

    
    证明:将整个图形绕A点逆时针旋转90度。显然∠MAM'为90度,BCC'也为90度。连接M'N,则BM^2 + NC^2 = M'C^2 + NC^2 = M'N^2,于是MN = M'N。又AM = AM', AN = AN,由SSS可知△AMN≌△AM'N,这样∠MAN和∠M'AN都是45度。

来源:cut-the-knot新文
Matrix67原创翻译

趣题:内切圆与最大内接矩形

      
    看图,DEFG为直角三角形ABC的内接矩形,三个内切圆的半径从小到大依次为r1, r2和r3。证明:当内接矩形的面积达到最大时,r1^2 + r2^2 = r3^2。

      
    四个直角三角形ABC, EDC, AEF, DBG显然相似,内切圆半径与边长一样对应成比例。因此,我们可以把研究对象转换到任意一个对应边上。这里,我们重点观察四个三角形斜边长的关系。
    如果△ABC的三边BC, AC, AB长度分别为a, b, c,那么对于某个相似比k,其余三个三角形的对应边长度如下:

△ABC     a      b      c
△EDC    ka     kb     kc
△AEF    …    …  (1-k)b
△DBG    …    …  (1-k)a

    现在,我们要证明的是,当矩形DEFG面积达到最大时,有:
  [(1-k)a]^2 + [(1-k)b]^2 = (kc)^2

    也即
  (1-k)^2 * a^2 + (1-k)^2 * b^2 = k^2 * c^2

    同时,我们还知道a^2 + b^2 = c^2。等式两边同时乘以k^2后与上式相减,我们就得到:
  (1 – 2k) * (a^2 + b^2) = 0

    显然,只有k=1/2时上式才有可能成立。
    接着看,由△DBG ∽ △ABC,可知 DG/AC = BD/AB,因此DG = (1-k)ab/c。另外,我们还知道DE=kc,那么矩形DEFG的面积就可以这样表示:
  S = DG x DE = (1-k)k * ab

    S取最大等价于函数f(k)=(1-k)k达到最大值。这个函数是一个以0和1为根的上下颠倒的抛物线,显然在k=1/2时达到最大值。

来源:cut-the-knot新文
Matrix67原创翻译