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