Продолжаем уроки математики от профессора Нелли Литвак.
Напомним, в группе «Математика — великая и ужасная!» Нелли вместе с журналистом Аллой Кечеджан помогают взрослым гуманитариям освоить великую и ужасную науку «с нуля». Они постоянно доказывают, что: а) математику может постигнуть каждый; б) социальные сети — отличное пространство для образования.
Вопрос важнее ответа. Когда студенты говорят, что ничего не понимают, я их прошу сформулировать вопрос, что именно непонятно. И когда они это делают, они часто сами видят ответ, и объяснять больше ничего не надо!
Занятие 9. «Прочувствовать» логарифм
Теперь мы подошли к новому великому и ужасному математическому инструменту — логарифму.
Один из участников нашей группы задал такой вопрос: «В чём прелесть логарифмов, какие задачи они помогают решать? Что могут дать логарифмы для гуманитариев? Знаете ли вы какие-нибудь интересные применения логарифмов? Всегда хотелось «прочувствовать» это понятие, так сказать, «сроднить» со своими мыслительными механизмами. Но везде, где я искал, сухой математический язык, нигде не раскрывается философия этого инструмента...»
Сначала — что такое логарифм. Смотрите.
2^1=2 (2 в степени 1 равно 2);
2^2=4;
2^3=8;
2^4=16 и так далее.
Применений полно повсюду. Вот пример из кодирования. Компьютер всё записывает с помощью нулей и единиц. Для каждой позиции есть два варианта — 0 и 1. Если у нас пять позиций, и на каждую по два варианта, то можно закодировать 2*2*2*2*2=2^5=32 разных символа. На русский алфавит не хватит.
Более естественно спросить наоборот: нам нужно закодировать, скажем, 128 символов (русский и латинский алфавит плюс цифры и кое-какие знаки препинания). Сколько позиций кода нам понадобится?
Это очень важно, потому что каждая позиция занимает память в компьютере. Каждая позиция — это бит, 8 позиций — это байт, и 1024 байта — этот тот самый килобайт, который вам компьютер показывает, когда вы смотрите, насколько документ «тяжёлый». Так вот: сколько нужно позиций, чтобы закодировать 128 разных символов? 2^7=128, то есть нужно 7 позиций, это логарифм по основанию 2 от 128.
Длина кода — это логарифм от количества информации, которую он может закодировать.
Вот здесь в обсуждениях можно посмотреть другие примеры использования логарифмов. И очень здорово, что участники группы замечают закономерности в существующем математическом инструментарии: если есть действие «возведение в степень», значит, должно быть и противоположное — извлечение корня и взятие логарифма.
Задание №1. Турнир Большого Шлема
По телевизору показывали теннис, турнир Большого Шлема — American Open. Я подумала, что для нас это повод лучше разобраться в связи между степенями и логарифмами.
ЗАДАНИЕ. 128 игроков начинают турнир на вылет. Правила знакомы всем. Двое теннисистов играют матч, проигравший вылетает, а победитель выходит в следующий раунд, где встречается с другим победителем предыдущего раунда. И так до четвертьфинала, полуфинала и, наконец, два последних игрока играют финал за звание чемпиона. Вопрос: сколько матчей будет сыграно в таком турнире?
КСТАТИ: Хотя задача напрямую связана со степенями и логарифмами (мы ещё обсудим, как именно), самое простое решение, как часто бывает, основано на простом здравом смысле. В данном случае даже никакой математики для этого знать не нужно!
Итак, я надеюсь, что вы попробовали свои силы в здравом смысле и математике и готовы проверить своё решение.
Решения было два.
Первое решение. В первом раунде 64 матча (128 делить на 2), во втором 32 и так далее до финала. Ответ: 64+32+16+8+4+2+1=127
Второе решение ещё проще. В каждом матче вылетает ровно один игрок. В результате вылетают все, кроме чемпиона. Всего игроков вылетает 128-1=127, это и есть количество матчей.
Заметьте, что 128 — это 2 в степени 7: 128=2^7, 64=2^6, 32=2^5, и так далее, то есть мы складываем степени двойки. И получаем, что 2^6+2^5+2^4+2^3+2^2+2^1+1=2^7-1
Но вдруг эта закономерность только для степеней двойки, или с 3 или 71 тоже работает?
Работает, но с поправкой! Допустим, начинают 3^7 игроков, играют по три, два вылетают и один проходит. Рассуждение то же самое, вылетают 3^7-1 игроков. Но нам нужно число матчей, а в каждом матче вылетает двое. Поэтому надо число проигравших поделить на два — по два за матч. Это в точности равно (3^7-1)/2.
Естественно, можно решить и со степенями. В первом раунде 3^6 матчей, во втором 3^5, и так далее. Получаем: 3^6+3^5+...+3+1 = (3^7 -1)/(3-1).
Такая сумма степеней называется великими и ужасными словами «геометрическая прогрессия».
Число 7, конечно, можно заменить любым целым числом. Тогда мы получаем более общую формулу для суммы геометрической прогрессии: (3^n-1)/(3-1), где n — это количество слагаемых (в задачке про теннис — количество раундов). Тройку тоже можно заменить любым числом, даже нецелым или отрицательным. Формула остаётся верна.
Задание №2. Про чемпиона
Теперь давайте поговорим про связь между задачкой про теннис, степенями и логарифмами.
ЗАДАНИЕ: Снова 128 спортсменов начинают турнир на вылет. Спрашивается, сколько раундов нам понадобится, включая финал? Это очень важный вопрос для организации, расписания, телетрансляций и так далее. Другая формулировка: сколько раундов сыграет чемпион?
Ответ можно посмотреть здесь. Но ответ-число — это не главное. Главное — объясните, при чём здесь логарифмы!
Задание №3. Абстрактная математическая бактерия
Представьте себе бактерию, которая живёт один день, за день она производит 5 таких же бактерий и после этого умирает.
Да простят меня биологи... Скорее всего, таких бактерий не существует. С другой стороны, я была в музее «Микробия» в Амстердаме и узнала, что разных сортов бактерий в великие разы больше, чем разных сортов «видимого глазом» животного мира. Так что будем надеяться, что найдётся что-то подобное этой задаче. А если не найдётся, то в том и сила математики, что решение можно распространить и на другие случаи.
ЗАДАНИЕ: Перед нами бактерия, которая за день производит 5 потомков и умирает. У нас в пробирке ровно одна бактерия. Через сколько дней бактерий станет миллиард?
Напомню, что поисковую строчку Google можно использовать как калькулятор. Если вы наберёте 6*3, то получите 6, умноженное на три, а если наберёте 6^3, то получите 6 в третьей степени, то есть 6*6*6.
А теперь давайте разберёмся, что же общего между теннисом и бактериями. Допустим, за один день бактерия делится пополам и производит две новые бактерии. На рисунке 1 я нарисовала, как растёт население бактерий.
0 дней с начала эксперимента, у нас одна бактерия. Прошёл один день, бактерий стало 2^1=2. Прошло два дня, и бактерий стало 2^2=4. И так далее: 8, 16, 32…
А теперь перевернём картинку, см. рисунок 2. Это же теннисный турнир на вылет! На рисунке начинают 32 игрока, потом их 16, потом 8, потом 4. В финале 2 игрока, и в конце концов остаётся один чемпион.
Что же общего между теннисом и бактериями? С точки зрения математики, между ними нет никакой разницы! И то, и другое описывается с помощью степеней.
Номер «поколения» растёт: 0, 1, 2, 3, … Но население растёт гораздо быстрее: 1, 2, 4, 8, и т. д.. Чтобы перевалить за миллиард, нужно всего 30 поколений. Представляете?
Такая зависимость называется «степенной» или «экспоненциальной», потому что номер поколения — это степень двойки. И, конечно, двойку можно заменить любым другим числом.
Мы выяснили, что число раундов и число поколений — это и есть великий и ужасный логарифм. Логарифм — это всего лишь в какую степень нужно возвести число.
3^1=3;
3^2=9;
3^3=27.
Логарифм 3 по основанию 3 = 1;
Логарифм 9 по основанию 3 = 2;
Логарифм 27 по основанию 3 = 3.
И так далее.
Возьмем, например, степени десятки: 10^6 это миллион (1 000 000); 10^9 это миллиард (1 000 000 000).
Логарифм миллиона по основанию 10 равен 6. Логарифм миллиарда по основанию 10 равен 9. Мы перешли от миллиона к миллиарду, аж три нуля приписали, а логарифм вяло и лениво увеличился всего лишь на три!
Лирическое отступление. Маленький мир социальных сетей
В социальных сетях есть понятие «маленького мира». Любых двух людей соединяет очень короткая цепочка знакомых.
На языке математики мы говорим, что сеть обладает свойством «маленького мира», если цепочка, которая связывает двух произвольных людей, по порядку величины сравнима с логарифмом от числа участников.
В Фейсбуке расстояние в среднем 3,75, то есть примерно 0,4 от десятичного логарифма числа участников. По порядку величины, если подумать, какая гигантская эта сеть — логарифм даёт довольно правильное представление о расстоянии.
ЗАДАНИЕ: Объясните, почему понятие «маленького мира» связано именно с логарифмом? Откуда берётся логарифм, почему это логично?
Структура социальных сетей гораздо сложнее, чем структура теннисного турнира. И главная причина в том, что в социальных сетях у нас много «циклов»: Если А дружит с Б и с В, то очень часто Б тоже дружит с В. Получается треугольник. И такую сеть, с треугольниками и другими короткими циклами, анализировать гораздо труднее, чем «дерево», как в теннисном турнире, где циклов нет.
Если смотреть на чисто математические результаты, то циклы — это самая большая проблема при анализе.
Пока мы можем получить логарифмические расстояния только для сетей, которые мы называем «локально похожие на дерево». По сути это означает, что в наших моделях короткие циклы (короче, чем логарифм от числа участников) очень маловероятны. Это сильное упрощение реальности, но многие вещи удаётся выяснить на таких простых моделях. Например, как распространяются эпидемии и распадется сеть или нет.
В реальных сетях, конечно, таких коротких циклов очень много. Анализ для них ещё не придумали, но эта область математики (случайные графы) развивается так быстро в этом направлении, что хотя бы по каким-то моделям результаты скоро будут, я уверена.
Конечно, мы не хотим получить бессмысленные результаты типа «средней температуры по больнице». Мы рассматриваем расстояние между двумя произвольными участниками сети как случайную величину. Эта величина с какой-то вероятностью может быть 1, 2, 3, и так далее. При доказательстве теорем мы часто устанавливаем верхнюю границу. Результат тогда звучит примерно так: «С большой вероятностью, расстояние не превышает константу, умноженную на логарифм от числа участников».
Мои коллеги из Милана, информатики, подсчитали расстояния в Фейсбуке. Это очень сложная задача ещё и с алгоритмической точки зрения. Потому что участников на тот момент было 700 миллионов, а пар и того больше, и нужно было подсчитать расстояние между всеми парами! Но не только в количестве дело. Опять же, именно из-за циклов задача сложна алгоритмически.
У них получился как раз тот самый результат, о котором я писала:
Но на самом деле в статье они всё распределение подсчитали: какой процент пар на расстоянии 1, 2, 3,... Про этот результат писали BBC и New York Times. Так что интерес к этой теме явно есть.
Надеюсь, сейчас вам удалось «сроднить» логарифмы со своими мыслительными механизмами. На следующем уроке мы поговорим о прививках. С точки зрения математики, конечно.
