第 6 集 · B1 · 7 分钟
数学思维 · 第6集 · 证明（续）
萨瓦捷耶夫用慢而清楚的俄语讲逻辑、函数、证明和集合，适合跟听长句。 开头：也就是说，我们现在还要诉诸于
中俄字幕
то есть мы теперь еще апеллируем к
也就是说，我们现在还要诉诸于
индукции, да, как тут много всего сразу:
数学归纳法，是的，这里一下子出现了很多方法：
от противного, по индукции и бесконечный
反证法、数学归纳法以及无穷递降法。
спуск. Вот уже три метода доказательства в
这已经是同一道题中使用的三种证明方法了。
одной задаче.
一道题目中。
Хорошо, предположим, что
好的，假设
мы доказали, что ему необходимо
我们已证明，他除了使用这些纸币外，还必须
пользоваться кроме вот этих всех купюр еще
使用其中某些其他面额的纸币。
и какими- нибудь из этих.
以及其中的某些面额。
и докажем, что тогда на самом деле ему
并证明此时实际上他
необходимо пользоваться и какими- то из
必须使用其中一些
этих. Ну, смотрите, если мы
这些。嗯，你看，如果我们
знаем, что за бесконечное количество
知道经过无限多步后无法
шагов нельзя с
与魔鬼交流
чёртом общаться, используя
仅使用这张纸币列表
только вот этот список купюр, тогда это
那么这就意味着
означает, что в какой- то момент придётся
在某个时刻，我们不得不
обратиться к этой или более высоким.
求助于这张或更高面额的纸币。
Ну, давайте, пока мы хотим доказать, что
好吧，让我们暂时先证明
нельзя пользоваться тысячной и всеми
不能仅使用千元及所有更小面额
нишами, значит, бесконечное количество
壁龛，也就是说，无限多步
шагов. Итак, так как этими нельзя
这些步骤，因此由于这些步骤
бесконечное количество шагов, то в какой-
无限多步，那么在某个
то момент вы выдадите тысячу ему.
时刻，您会给他一千张。
Так, в этот момент у вас увеличатся вот
这样，在这一刻，您的这些
эти вот, любым образом увеличатся вот эти
这些钞票会以某种方式增加，
купюры, но тысячных станет на одну меньше.
但千元钞票会减少一张。
за конечное время эти все исчезнут по
在有限时间内，所有这些都将按已证明的那样消失。
доказанному.
已证明。
Значит вам придется еще одну тыквенную
因此您将不得不再拿一个南瓜。
использовать.
使用。
за конечное время опять эти все исчезнут
在有限时间内，所有这些又会消失。
значит придётся ещё одну тысячную ну и
所以还得再加一个千分之一，嗯……
видно что тысячные тоже кончатся за
可见，千分之一也会在有限时间内耗尽。
конечное время и вот индукционный шаг да
于是就完成了归纳步骤，对吧？
то есть мы говорим что если мы доказали
也就是说，我们说如果已经证明了，
что вот этими нельзя торговать бесконечное
用这些单位无法进行无限长时间的交易，
количество времени то и этими нельзя ну и
那么用这些单位也无法做到，对吧？
так вот мы как бы дойдём по индукции
这样，我们便可通过归纳法逐步推进，
дойдём до самого верха и выясним что и эти
最终到达最顶层，并发现这些也同样不行。
тоже в конце концов кончатся ну тогда
最终也会耗尽，那么
это означает, что он
这意味着他
может быть очень нескоро, но всё равно
可能要等很久，但终究
разорится. Ну тут, конечно,
会破产。当然，这里
предполагается, что он может жить вечно,
假设他能永生，
да, и чёрт тоже.
是的，魔鬼也能。
Но, видимо, когда он разорится, он тогда и
但显然，当他破产时，他也就
умрёт. сложная красивая задача, в которой
死去。这是一道复杂而优美的题目，其中
три метода доказательства сразу
同时运用了三种证明方法。
используются.
同时运用了三种证明方法。
так еще еще есть методы доказательства
还有其他证明方法
которые ну как бы они
嗯，就是那些方法
связаны просто с логикой рассуждений вот
仅与推理逻辑相关
смотрите задача такая
请看这道题
девять монет одна фальшивая тяжелее других
有九枚硬币，其中一枚是假币，比其他硬币重
задача из форта боярд
这道题出自《博雅尔堡》节目
там правда восемь было.
不过原题中是八枚。
одна тяжелее других, остальные настоящие.
其中一枚比其他硬币重，其余都是真币。
за сколько взвешиваний можно их
最少需要称量几次才能找出它？
обнаружить? здесь доказательство состоит в
这里的证明在于
переборе всех вариантов после того как вы
在穷举所有可能性之后，当你
догадаетесь до того за сколько взвешиваний
推断出需要多少次称重才能解决
вы должны будете аккуратно перебрать все
必须严谨地穷举所有可能性
варианты и этот метод доказательства
这种证明方法
естественно носит название доказательство
自然被称为
переборным способом
穷举法证明
но как говорится перебор тоже должен быть
但俗话说得好，穷举本身也需
умный ну во первых видно что за одно
讲究策略：首先，显然一次称重
взвешивание вы ничего не определите
你无法确定任何结果
понятно что при одном взвешивании ну как
一次称重，显而易见，无论如何
бы если даже на одной чаше весов одна
但如果天平的一边只有一枚硬币
монетка то есть либо часть монет останутся
也就是说，要么部分硬币会剩下
либо на какой то чаше весов слишком много
要么某一边的硬币太多
монет и ничего между ними уже понять будет
而它们之间已无法分辨
нельзя поэтому ясно что одним взвешиванием
因此，显然单靠一次称重
здесь не обойдешься и вот сюрприз в том
是解决不了问题的；而惊喜在于
что двумя можно уже вполне
仅用两次称重就已完全足够
довольствоваться смотрите фокус- покус
请看这个神奇操作：
кладем так и так
这样放，那样放
теперь варианты вот теперь начинаем
现在来看各种可能情况；现在开始
перебирать варианты
逐一尝试各种选项
левая тяжелее
左边更重
Тогда что? Тогда среди вот этих очевидно
那么呢？那么在这几个中显然
это тяжелая, да?
这个是重的，对吧？
Она же только одна тяжелая, остальные все
只有一个重的，其余全部
одинаковые. Хорошо, если среди этих одна
重量相同。好的，如果这几个中有一个
тяжёлая, то мы кладём
是重的，那么我们放两个到这里。
две из них сюда.
其中两个放在这里。
а третью просто оставляем в сторонке.
第三个则直接放在一边。
Итак, на первом взвешивании мы взяли две
因此，在第一次称重中，我们取了两个
из этих кучек и положили на весы.
从这些堆中取出并放在天平上。
Дальше идёт перебор.
接下来是逐一排查。
Если левая чаша весов перевесила, то мы
如果天平左边下沉，那么我们
берём два из них, сравниваем, и опять
从中任取两个进行比较，再次
перебор трёх вариантов.
逐一排查三种可能。
Если одинаковая,
如果重量相等，
то ровно последняя и есть та, которая нам
那么最后一个就是我们需要的那个。
нужна. Если здесь больше, то вот эта была
如果这里更重，那么这个就是较重的；
тяжёлой, если меньше, то этой.
如果更轻，那么就是这个。
То есть в этом случае мы всё нашли.
也就是说，在这种情况下，我们已经全部找到了。
Совершенно аналогично будет если вот это
完全类似地，如果这个
тяжелее правое,
右边更重，
то же самое.
情况也一样。
А если они равны, то что?
如果它们相等，那会怎样？
Правильно, тогда мы эти три оставшиеся,
没错，那么剩下的这三枚硬币中，
среди которых, естественно, и должна быть
自然就包含那枚较重的硬币，因为
тяжелая монета, потому что она только
它只有一枚，所以如果它们相等，
одна, и значит, если они равны, они все
那它们就都是正常的。
нормальные. Вот с этими проделываем ту же
接着对这三枚硬币执行同样的操作，
последнюю операцию, тоже откладываем одну
同样先搁置一枚。
монету в сторону.
硬币朝一边抛。
Вот мы взяли и методом перебора
我们就这样通过穷举法
решили эту задачу.
解决了这个问题。
Вот, ну и сейчас еще
好了，接下来我还要
расскажу про пару методов, которые тоже я
介绍几种我也非常喜欢的证明方法，
очень люблю, которые тоже в
这些方法在证明中也经常被使用。
доказательствах часто используются.
这些方法在证明中也经常被使用。
Итак, следующий метод доказательства,
接下来我要介绍并演示的证明方法是
который я вам расскажу и проиллюстрирую,
接下来我要介绍并演示的证明方法是
называется метод построения инварианта.
称为构造不变量法。
И он на самом деле он
而他实际上
выводит на совершенно передовые разделы
引向数学的最前沿领域
математики, то есть современной высокой
即现代高等数学。
математики. Он как бы используется сплошь
它被广泛地、持续地应用着，
и рядом. Ну все используются там в разных
且随处可见。嗯，所有人都在不同场合
моментах разные фрагменты рассуждений
使用各种不同的推理片段，
пользуются всеми упомянутыми методами, но
并运用所有前述的方法，但
это такой продвинутый метод, реально
这是一种非常先进的方法，真正地
продвинутый.
非常先进。
Я его иллюстрирую на двух примерах.
我将通过两个例子来说明它。
Первый пример простой, второй посложнее,
第一个例子很简单，第二个稍难一些，
но тоже не очень сложный.
但也不是特别难。
Шахматная доска,
国际象棋棋盘，
вырезаны два противоположных,
切掉了两个对角的，
значит, этих самых две противоположных
也就是说，去掉的是两个对角的方格。
клеточки. Итого получается у нас тут 62
总共剩下62个方格。
доминошки. можно ли ой вся две клетки
有62张多米诺骨牌。能不能——哎呀，每张覆盖两格，
можно ли их эти клетки замостить
能不能用这些方格铺满？
доминошками два на один
用2×1的多米诺骨牌，
то есть как то вот так
也就是像这样铺。
Ну понятно, вот,
好吧，明白了，就是这个，
ну мастить, мастить, мастить и все
就是涂，涂，涂完就完了。
вымастить. С первого взгляда кажется, что
涂满整个棋盘。乍一看，似乎
почему бы нет.
好像没什么问题。
62 делится на 2, 31 доминошка и все такое.
62能被2整除，所以是31张多米诺骨牌之类的东西。
но если вы начнете пытаться это замочать
但如果你试着铺满它，
да у вас все время будет оставаться две
总会剩下两个格子，
клетки и все время в разных местах вот
而且总是在不同的位置。
просто можете взять и потренироваться с
你完全可以自己多练习几次。
этим несколько раз.
用这个多练习几次。
будет вечно облом такой как бы и каждый
永远都会碰壁，仿佛每一次都是如此
раз будет облом то
一旦碰壁，就……
есть вы как бы надеваете на себя кафтан
你们就好像给自己披上了长袍
физика и говорите это задача
物理学，并宣称：这是一道题
экспериментальная
实验性的
поэкспериментировав сто раз мы вполне
经过一百次实验，我们完全
уверены что это невозможно это установлено
确信这是不可能的，这一点已得到证实
невозможность экспериментальным путем
这种不可能性是通过实验方式确定的
программист скажет запустим программу на
程序员会说：我们在超级计算机上运行这个程序
суперкомпьютере она переберет все варианты
它将穷举所有可能的情况
замещений пройдет пятьсот миллиардов
替换操作将进行五千亿次
факториал лет и
阶乘年，以及
компьютерная программа остановится и
计算机程序将停止运行，并
скажет что все варианты перебраны нет
宣布所有方案均已穷举完毕，但
возможности замостить и он скажет ура вот
无法实现密铺。它会欢呼道：“太好了！我证明了！”
я доказал а
而
来源：Alexey Savvateev · CC BY 3.0