建设
数学中许多著名的问题都被表述为寻找一个特定的问题建设这符合某些标准。这通常需要一些创造力和对问题背后理论的理解。
一些众所周知的施工问题有:
- 费马大定理:是否存在非平凡解 为 ?
- Borsuk猜想:每个有界子集 空间的 被划分为 集合,每个集合的直径都小于 ?
- 古代几何问题:我们能否仅用圆规和直尺对任何角度进行三等分?
施工方法
在构造问题中,我们寻求一个明确的描述或识别,这使我们能够验证陈述是真还是假。
这有3个方面:
- 建设-是否有一种算法或方法可以让我们构造一个满足约束条件的构型?
- 存在-是否有满足条件的配置?我们能证明构型不存在吗?
- 枚举—满足条件的配置有多少种?
我们将介绍以下方法,以帮助您思考构建问题。
向前感应
我们从选择一个构型开始 ,并进一步选择以获取的配置 .这种映射可以是一对多的,不需要是满射或“内射”。重复计算可能是个问题。
有多少子集 有吗?
让它存在吧 的子集的数目 .
我们将继续证明<一个href="//www.parkandroid.com/wiki/induction/" class="wiki_link" title="感应" target="_blank">感应那 .
基本情况:我们知道 ,即空集 .
归纳步骤:
给定一个子集 ,我们如何创建的子集 ?有两种可能:
1.我们可以加上元素 到它。
2.我们对它无能为力。
因此,每个子集 对应于的2个子集 .相反地,我们可以找到这两个子集 对应于一个子集 .这设置了“双射”,它向我们展示了这一点 .
逆向归纳
我们从一个构型开始 ,并进一步选择以获取的配置 .这个映射可以是一对多的,也不需要这样<一个href="//www.parkandroid.com/wiki/bijection-injection-and-surjection/" class="wiki_link" title="满射或内射" target="_blank">满射或内射.重复计算可能是个问题。相对来说,它更难实现。
有多少子集 有没有两个元素是连续的?
给定这样一个子集,让我们考虑它是否包含元素 .
- 如果它包含元素 ,则它不能包含元素 .没有进一步的限制,因此我们得到的子集 它满足条件,我们将它与 .
- 如果它不包含元素 ,那么我们就得到了 满足条件。
让 表示满足这个条件的子集的数目。然后,上面的论证告诉我们 .我们可以计算的初值 (空集)和 (空集和 ).还有递归关系 这些初始值,我们可以得到<一个href="//www.parkandroid.com/wiki/fibonacci-series/" class="wiki_link" title="斐波纳契数" target="_blank">斐波纳契数.
这两种归纳法的区别是什么?虽然这些是相似的,但向前/向后方面是我们思考解决这些问题的方式。通常,这两种方法都可以使用,只是解决方案略有不同。
在第一个问题中,两种方法同样有效。反向归纳方法是从这样一个子集开始,然后考虑它是否包含元素
.
在第二个问题中,因为映射是从
两个
而且
逆向归纳法是更自然的思考方式。
贪婪算法-涵盖一切
使用局部启发式来确保我们的选择是好的,但仍然足够简单。理想情况下,“当且仅当存在使用局部启发式的配置时,就存在配置”,但这并不总是正确的。
考虑一个 董事会。骑士可以通过访问每个方格一次来游览整个棋盘吗?
我不知道这个问题的完整解决办法。你可以填写细节。
其基本原则被称为Warnsdorff规则:寻找邻居数量最少的邻居。为什么这样做有效(或者至少,为什么这样做可能有效)?
- 它优先考虑最有可能被切断的方块。
- 特别是对于只有两个空闲邻居的方块,当你落在其中一个邻居上时,你必须移动到该方块,然后从另一个邻居退出。
- 然而,这并不能保证你会探索整个棋盘。你可能会被困在一个地方。这是贪婪算法的缺点。
结构逃避器和查找器
如果问题的目的是构造一个构型避免了某种结构(如单色三角形的存在、元素等) ),考虑以下两个角色会有所帮助:
- 结构回避者:目标是构造一个避免结构的配置。
- 结构查找器:目标是在配置中查找结构(如果它存在的话)。
(印度TST)考虑数字的任何分区 分为三组 每个尺寸 .证明存在 , 而且 使得其中一个是另外两个的和。
我们要避免的结构是形式 .我们的主要障碍是什么? 这是个大问题,但很容易控制。 这也带来了一个问题,但更难控制。因此我们与 .
WLOG, .下一个问题是什么?显然是这样的 .我们知道它通向哪里吗?不完全是,它可以进入任何集合 .如果它进入 ,然后我们可以继续询问 .因此,适当的制定 如下:
让 而且 .
我们认为可能的问题是什么?相等大小的条件还没有被使用,所以为了使它发挥作用,我们必须相信其中一个集合是大的。我们还没有任何消息,但我敢打赌 被大。现在,结构查找器告诉我们没有元素对 而且 可以由 .结构回避者告诉我们没有连续的(或在 )元素可以在 而且 .因此,如果 有两个连续的元素 而且 ,然后 不在 或 ,所以它是在 .同时, 不在 或在 ,所以它是在 .因此, 而且 都在 .然后我们可以反复移除 从这两个元素到其中一个元素 ,这就产生了矛盾。所以,如果 ,然后 .
此外,由于 ,如果 ,然后 .
从前面的2个陈述,我们可以得出结论,如果 ,然后 .这给了我们一个内射映射 来 .它不是满射,因为 ,因此 ,这与大小相等的假设相矛盾。 .
构造-反例
这里的想法是通过构造一个特定的反例来证明一个陈述是不正确的。
典型的例子是古代的三个几何问题:圆的平方,立方体的两倍,以及仅通过圆规和直尺对角进行三等分。为了解决这些问题,我们提出了一个概念可构成的数量在复平面上。一个复数是可构的,如果它在欧几里得平面上的对应点可以用无规直尺、圆规和单位长度的线段来构。利用场论的语言,证明了可构造数是有理数的二次闭包。虽然这个完整的描述现在有点超出了我们的范围,但我们可以证明一个可构造数必须是一个代数数(这意味着它是一个整数系数多项式的根)。接下来要考虑各种罗盘和直尺结构实际上允许什么。因此,由于 是先验的,它表明我们无法把圆的平方。
欧拉猜想(1769年提出)指出
如果有非零整数 与 而且 ,然后 .
这似乎推广了费马最后定理,也就是 .这个猜想很容易被证明是正确的 的非平凡解 ,即费马大定理的具体例子。
终于在1966年,通过计算机直接搜索,得到了一个反例 被发现:
1986年,诺姆·埃尔基斯发现了一组解 :
在哪里 .因为这是<一个href="//www.parkandroid.com/wiki/elliptic-curves/" class="wiki_link" title="椭圆曲线" target="_blank">椭圆曲线理性点在 ,有无穷多个其他有理点。然后我们可以把它代入上面的方程并明确分母。
1999年和2000年的病例 分别用具体例子予以反驳。
到目前为止,还不知道是否 或 是假的。想试试吗?
Borsuk猜想问道
每个有界子集 空间的 被划分为 集合,每个集合的直径都小于 ?
这是一个著名的问题,对于 (1932年证明)和 (1947、1955年证明)。这被认为是对更大的 ,但没有进一步的结果,直到杰夫·卡恩和吉尔·卡莱通过构造一组特定的点来证明这是不正确的 .安德里·邦达连科(Andrij Bondarenko)证明了这个猜想对所有人来说都是错误的 .目前,尚不清楚是否 是一个真实的陈述。
施工-解决问题
长寿链是一个连续整数序列,其数字和永远不是9的倍数。长寿链的最长长度是多少?
我们知道,任何倍数为9的数,其数字和都是9的倍数。因此,长寿链最多可以有8个元素。
作为一个显式的例子,序列 是由8个连续整数组成的序列,其数字和永远不是9的倍数。
因此,答案是8。
在上面的问题中,我们需要理解的是数字和与9的倍数之间的关系。有了这些理解,解决方案的构造就很简单了。
是否存在一组同心圆使得每个圆恰好包含一个格点,并且每个格点都在一个圆上?
考虑这些同心圆的中心。由于每个格点都在一个唯一的同心圆上,这意味着每个格点到中心的距离必须是不同的。
结论:重点 作为同心圆的中心。
假设不是,那么我们必须有2个晶格点 它们的距离是相等的。这意味着
展开项,我们得到这个
如果 ,则LHS是理性的,RHS是非理性的,这是一个矛盾。因此 .因此, ,这意味着 ,或者 .因为第二项不为0(因为 都是整数),我们必须有 这与两点不同的假设相矛盾。
在上面的问题中,我们改变了条件,并将其重新表述为一个数论命题,这使得它更容易接近。
注意:有一个存在性解法,它证明平面不能被数条线所覆盖。
有没有可能在平面上找到7个点使得在3个点的每个子集中,有2个点是间隔单位距离的?
让 是4点这样 .让我们稍微旋转一下 ,以得到 这样 .
声明:这组7个点满足条件。
证明:如果3点在于 或 ,那么我们就完成了。否则,我们必须在每个集合中有2个点。如果这些点不是 或 ,那么它们之间就是一个单位距离。因此,3点必须如此 ,但这给了我们 ,我们做完了。
额外的问题
1)子集
是sum-free如果没有解决方案
为
.(注:我们考虑到
.)
证明对任何
,有一个无和的子集
的大小
.
2)格方形是平面上的正方形,其4个顶点为格点。描述一个格子正方形可能边长的集合。
3)对于哪个整数 ,是否存在 平面上的点,不都是共线的,使得任意两点之间的距离都是整数?