Курс состоит из нескольких жизненных сюжетов, каждый из которых разбирается "по косточкам" и, как выясняется, содержит внутри себя нетривиальное математическое ядро. Это ядро далее также бьётся на "элементарные частицы" - так, что у слушателей возникает понимание всех глубинных механизмов рассматриваемой ситуации. Сюжеты сгруппированы по смыслу: каждая группа сюжетов вращается вокруг одной и той же основополагающей математической идеи. Таких идей всего пять: инвариант, шаг через бесконечность, непрерывность физических процессов, самоподобие природы и нашего её восприятия, и, наконец, алгебраическая природа различных чисел. Курс предназначен для всех, кто хочет лучше представлять себе тот мир, в котором мы живём. Не имея никаких предварительных знаний, слушатели будут введены в курс дела: какая техника используется в математике ("абсолютное доказательство" как главное отличие математического знания от любого иного) и как строить рассуждения. Вскоре выйдет вторая часть, "Математика для энтузиастов", которую нужно будет уже изучать "с листочком бумаги и ручкой в руках". В ней встретится более нетривиальный материал, в том числе "приводные ремни" современной математики - "группы" и "поля". Кроме того, будут вскрыты весьма нетривиальные подоплёки многих школьных задач. Курс состоит из 6 недель и 6 контрольных работ по окончании каждой недели. Для успешного прохождения курса необходимо успешно преодолеть все 6 испытаний.
Задача Пола Эрдеша
Loading...
Do curso por Moscow Institute of Physics and Technology
Математика для всех
325 classificações
Na lição
Элементы комбинаторики
На пятой неделе вы познакомитесь с несколькими сюжетами из мира теории вероятности, комбинаторики и графов.
Conheça os instrutores
Савватеев Алексей ВладимировичДоктор физико-математических наук
Кафедра дискретной математики МФТИ
Бычков Борис СергеевичКандидат физико-математический наук, младший научный сотрудник международной лаборитории теории представлений и математической физики НИУ ВШЭ
Кафедра дискретной математики
Мы обсуждали несколько сюжетов из дискретной математики
и комбинаторики.
И совершенно несправедливо было бы не упомянуть человека,
который может считаться королем комбинаторики.
Это человек, которого зовут Пал Эрдеш.
он никогда не был женат,
он прожил 83 года, и фактически он нигде не жил,
то есть он ездил между конференциями и домами своих друзей
и всю жизнь занимался только математикой,
никогда не занимался ничем больше.
Так вот, Пал Эрдеш очень любил все эти задачи,
о которых я рассказал, может быть, кроме Лиги чемпионов,
которая тогда, наверное, еще была не столь популярна,
и я бы хотел завершить неделю комбинаторики
одной из самых любимых его задач,
которая до сих пор является открытой математической проблемой.
Начну издалека.
Пусть вам дано десять фишек маленьких, на магнитиках,
например, они приклеены к плоскости
раз, два, три, четыре, пять, шесть, семь, восемь, девять, десять.
Требуется расставить их на плоскости так,
чтобы равных расстояний было как можно больше,
то есть чтобы было много таких треугольников равносторонних,
и они как-то между собой были тоже связаны в какую-то конструкцию,
где бы было как можно больше
равных друг другу вот таких вот отрезочков.
Итак, десять точек,
и нужно попробовать найти конструкцию на плоскости этих точек,
чтобы было как можно больше равных расстояний между ними.
сколько вообще существует отрезков между десятью точками,
если я нарисую все отрезки?
Вот возьму и нарисую все-все-все отрезки.
Будет тут много разных отрезков.
Вот хотелось бы понять, а сколько именно.
Ответ такой.
Давайте решим эту задачу.
Из первой точки сколько отрезков исходит?
Понятно, что девять, потому что во все остальные девять точек.
Хорошо, берем какую-нибудь вторую точку
один отрезок в первую точку мы уже провели.
Поэтому нужно провести остальные восемь отрезков
во все остальные точки.
Берем третью точку
из нее мы провели уже отрезки в первый и второй,
но в остальные, с четвертого по десятый, не провели,
значит, еще семь надо провести.
Берем четвертую — от нее осталось провести шесть и так далее.
Соответственно, будет такая сумма:
6 + 5 + 4 + 3 + 2 и 1.
Вот.
И соответственно, нужно посчитать такую сумму,
и для этого существуют разные приемы,
например, как вслед за Гауссом написать ее в обратном порядке.
Говорят, что это придумал Гаусс, хотя я не верю, я думаю,
что это знали и до него.
Если теперь мы просуммируем обе эти суммы вместе,
то получится соответственно удвоенное количество,
чем то, которое мы ищем.
И вот это удвоенное количество очень легко посчитать,
сгруппировав вот такими парами.
9 + 1 — это 10, 8 + 2 — это 10, 7 + 3 — это 10.
У нас получается, что идет сумма девяти слагаемых,
каждое из которых равно 10,
то есть это 9 умножить на 10, то есть 90.
Но это 90 — это сумма вот эта плюс такая же сумма еще раз,
поэтому это удвоенная рассматриваемая нами сумма,
ее нужно поделить на 2 и будет 45.
Итак, сколько отрезков могут иметь равную длину из этих 45,
сколько максимально?
Я умею строить так, чтобы получилось 19,
больше я не умею.
Может быть, кто-то сможет придумать какой-то пример, в котором
больше 19 из этих 45 отрезков, равных друг другу,
но интерес не в этом.
Интерес в том, что будет, сли я вам дам теперь сто точек.
А потом тысячу точек.
сли у меня есть
очень-очень много точек, например, миллион или миллиард,
то какой процент расстояний, сколько примерно по порядку вещей,
по порядку числа, сколько расстояний можно сделать равными?
Здесь есть замечательные достижения,
связанные с арифметикой целых чисел, очень красивой, но довольно сложной.
И на основе этой арифметики строится конфигурация на плоскости,
в которой количество расстояний равных
будет некоторому коэффициенту равно, умноженному на количество точек,
то есть для каждой точки будет несколько вот это вот C,
скажем, пять.
Пять отрезков будет равно друг другу и всем остальным отрезкам
из остальных точек, вот этим пяти.
У каждой точки есть пять отрезков, которые друг другу равны,
у разных точек тоже вот эти отрезки, выходящие пять отрезков, равны.
То есть получается примерно какая-то константа,
умноженная на количество точек.
И вот если мы будем увеличивать число точек,
у нас будет расти вот так с константой здесь.
Но Пал Эрдеш сумел доказать, что эту константу можно тоже,
неограниченно увеличивать, устремлять к бесконечности.
То есть с ростом количества точек
можно медленно-медленно выращивать эту константу.
Если у меня есть миллион точек, я могу добиться,
чтобы было пять миллионов равных друг другу расстояний,
то есть равных друг другу отрезков.
А если у меня миллиард,
я могу добиться уже восемь миллиардов таких равных расстояний.
А если триллион, то, скажем, 12 триллионов.
Если триллион триллионов триллионов,
то 28 триллионов триллионов триллионов.
То есть вот эта константа начинает неограниченно расти,
и вот этого сумел добиться Эрдеш.
Но он более точных оценок не дал.
В частности, он совершенно не знает,
насколько сильно можно заставить расти вот эту константу,
и это один из совершенно знаменитых
открытых вопросов в дискретной математике
такая золотая гипотеза Пала Эрдеша.
Кто может придумать, например,
какой-нибудь рост типа n в степени α, где α > 1?
Я уж извиняюсь перед теми, кто позабыл, что такое степень,
но вот этот вопрос,
можно ли придумать такую конфигурацию n точек,
чтобы равных расстояний было n в степени α, а α > 1,
никто пока не придумал, никто, ни один человек,
и неизвестно, возможно ли это.
Может быть, можно, наоборот, доказать, что ни каком α > 1
нельзя добиться при растущем числе точек
вот такой оценки количества равных расстояний.
Это типичная такая задача в духе Пола Эрдеша,
экстремальная комбинаторика называется.
И что интересно, что в этой области в данный момент,
когда мы с вами говорим, происходит довольно много прорывов,
просто научных прорывов.
Это совершенно живая математическая область.
И никто не поручится, что вот завтра ответ на этот вопрос
будет уже положительным,
когда вы увидите эту лекцию, ответ уже будет известен.
Может быть, потому что над этой задачей активно работают,
и там происходят то и дело какие-то дополнительные достижения.
И Пол Эрдеш оставил в районе тысячи таких задач.
Я думаю, что слушатели увидели, что последняя задача уже привела
чему-то, похожему на непрерывную, чем на дискретную математику.
И вот в этом состоит некоторое волшебство.
Математика дискретная, как только начинает выходить
за пределы каких-то очень простых постановок,
разу начинают пользоваться математикой непрерывной,
с результатами из математического анализа,
из линейной алгебры и так далее.
И соответственно, математика она совершенно взаимосвязана:
искретные задачи возникают из непрерывных,
а непрерывные возникают из дискретных.
И фактически разрубить ее топором на две отдельные области
область, где используются предельные переходы,
непрерывность и бесконечность, и где не используются
это сделать нельзя.
Математика живет как единое дерево.
И, в принципе, единственное, что действительно есть общее
у всех разделов в математике,
что требует формализации, осмысления, это понятие числа.
И вот как раз к этому понятию мы и перейдем теперь,
обобщая все, что мы узнали в течение этих пяти недель.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
