极值原理是一种通过研究具有极端性质的例子来解决某些数学问题的有效方法。这为我们理解简化后的问题提供了一个有用的起点。
在某种意义上,我们看到的物体或例子通常有最小或最大的值。认识到什么时候使用极端的原则通常是很有挑战性的。一些线索表明使用极端原则是有帮助的:
它是问题解决者最有用的工具之一,可以用来解决各种各样的问题。它基本上取决于一个看似明显但有用的事实,即每个非空有限有序集都有一个最小和一个最大的元素。
极值原理的应用最好是通过例子来理解,这就是我们现在要做的!
让我们从一个简单的例子开始,在这个例子中,这个命题是通过陈述显而易见的事实来证明的:
学生们站在一个场地上,这样每一对之间的距离是明显的。每个学生拿着一个球,当老师吹哨子时,每个学生把球扔给最近的学生。证明有一对学生互相扔球。
考虑任意一对学生之间的最小距离。因为这是最小的距离,离这两个都最近的学生就是另一个,所以这些学生互相扔球。
请注意其他成对的学生互相扔球当然是可能的。通过关注一个极端对象,我们可以很容易地确定一个必须始终工作的场景。
下面这个有趣的问题有效地展示了极值原理的威力:
假设在一个平面上有有限的红点和蓝点,它们具有以下有趣的性质:连接两个相同颜色的点的每一条线段都包含另一个颜色的点。证明所有的点都在一条直线上。
如果你拿出纸和笔,开始用这个属性画点,你可能会开始觉得,如果这些点不在一条线上,那么它们的数量就不可能是有限的。你是对的。但是我们如何严格地证明它呢?
当然是用极值原理!
如果这些点不是一条直线,你可以用这些点作为顶点画出不同的三角形。取最小的三角形,即面积最小的三角形。
这个三角形中至少有两个顶点的颜色是相同的。它们之间有一个不同颜色的点。将这个点与第三个顶点连接起来,你会得到两个三角形,每个三角形的面积都小于“面积最小的三角形”。
一个矛盾!所有的点必须躺在一条线上。
看这多容易!这就是观察极端情况的效果。
我们怎么知道总会有一个面积最小的三角形呢?并不是所有的有序集都有最小元素。例如,考虑间隔 .
之所以存在面积最小的三角形是因为三角形的数量是有限的,这是因为一开始点的数量是有限的。
所以这是另一件要注意的事当你想要使用极值原理时确保极端情况确实存在,在你声称它们存在之前。
在平面上选择点,这样就没有 共线。 都是蓝色的 的是红色。证明有办法加入 红色指的是 蓝色的点, 线段,使两条线段不相交。
假设我们连接这些红点 到蓝色点 以任意的方式。如果这个不具有我们想要的性质,那么我们必须有一个线段 加入 来 和一段 加入 来 使这些部分相交。如果我们让 连接 来 和 连接 来 那么这些线段就不再相交了。然而,有可能新的 和 再与其他线段相交。
我们注意到我们的交换移动减少了线段的总长度(画一个图并说服自己这是事实)。那么,让我们考虑线段的构型 它的总长度最小。注意,这样的最小值必须存在,因为对分段进行配对的方法是有限的。如果在这个构型中有一对交叉的线段,那么我们可以把它们分开,得到一个更小的长度和,与我们的选择相矛盾。因此,这种结构没有一对交叉段。
为 从1到 被放置在一个 棋盘。表示有一对水平、垂直或对角相邻的单元格,其值至少相差
考虑标记的细胞 和 存在一个至多的序列 细胞, 和细胞 和 是相邻的 如果相邻的每对细胞的值相差最多 那么 和 最多是 然而,它们之间的实际区别是 当 因此,这条链上的某些对至少有差异
考虑一个无限大的棋盘,棋盘上的平方都是正整数。这些整数中的每一个都是它四个相邻整数(上、下、左、右)的算术平均值。证明所有的整数都是相等的。
考虑这块板上最小的整数。我们叫它 .如果 是相邻的算术平均值吗 和 然后我们有
现在自 黑板上最小的整数,是吗 可以大于或不到 .所以它们必须等于 .换句话说,
由此可知,所有整数都是相等的。
在这个例子中,我们怎么知道存在一个最小的整数呢?不像第一个,我们没有有限的整数要处理。
这实际上遵循了有序原则,即非负整数的每个非空子集总是有最小的元素。
另一个例子:
在坐标平面上,证明正五边形的顶点不都是格点。
在我们开始之前,记住晶格点是一个整数坐标的点。
现在你们中的一些人可能在想一些三角函数的东西。在我们开始一些(非常混乱的)计算之前,让我们停下来想一想。
如果我们有这样一个五边形呢?将会发生什么?
你可能会说,如果我们有一个这样的五边形,我们就可以造出无限多个这样的五边形(怎么做?)但这对我们没有帮助。
在所有这些五边形中,选面积最小的那个。考虑这五个向量 从一个顶点到另一个顶点。
请注意, 在哪里 为正多边形的边长。
自 ,我们必须 和 .
求最后两个方程的平方 .
我们可以看到 必须是偶数。
等于 .这意味着 需要是偶数,这意味着 和 具有相同的奇偶性。
如果 和 都是奇数吗 不是a的倍数吗 .这意味着所有 和 是奇数。但如果真的发生了, 不能等于零,因为你不能通过相加得到偶数 奇数。
如果 和 那么,两个人都是偶数吗 分 .这意味着 和 甚至。现在我们可以缩放多边形 得到另一个以晶格点为顶点但面积较小的正五边形。这是一个矛盾。
所以不可能有这样的五边形。
注意,这个参数适用于任何规则 百分度, 是奇数。
1)证明一个立方体不能被分割成有限数量的小立方体,每个小立方体的大小都不同。另外,证明一个超立方体不能是超立方体。
平面上有限的点集具有这样的性质:由任意点组成的三角形 它们的面积都小于 .证明有一个三角形的面积 它包含所有的点。
图的每一个顶点 有学位 .证明我们可以划分的顶点 成 集 和 使每个顶点都在 至少有两个邻居 每个顶点 至少有 邻居