05.04.2017

Теория шести рукопожатий

Вы наверное слышали об идее что цепочки из шести человек, в среднем, достаточно чтобы связать вас с любым человеком на земле. Интересно также, возможно ли любого человека на земле связать с любым разумным существом во вселенной и какова длина этой цепочки. Но этот вопрос мы оставим на потом, и вернемся к границам земного шара.

Итак, в 1967 году американский ученый Стэнли Милгрэм провел эксперимент, который, вкратце, выглядел следующим образом: были выбраны пары городов, начальный и целевой, которые находились далеко друг от друга не только географически, но и социально. В начальный город, случайным людям, разослали письма с информацией об эксперименте и контакте персоны из целевого города. Если человек получивший письмо знал эту персону лично, то он должен был переслать письмо напрямую. В противном случае письмо необходимо было переслать тому, кто по мнению текущего держателя письма мог с большей вероятностью знать целевой контакт. Также присутствовал механизм для отслеживания длины цепочки людей, через которых проходило письмо прежде чем попасть к персоне в целевом городе. Средняя длина цепочки была равна шести.

В 2001 году Дункан Уоттс повторил вышеупомянутый эксперимент на современный манер. В качестве пакета для информации использовались электронные письма. Он получил такой же результат в виде средней длины цепочки равной шести.

Поразительно то, что шесть человек это не так уж и много. Это 0.00000008% от населения земли, которое примерно равно 7,3 миллиарда человек. Шесть человек можно посадить в ладу шестерку и устроить круиз по подмосковью. Но, как ни феноменально, этого может быть достаточно чтобы связать вас с любой, на первый взгляд самой недоступной, персоной.

Графы

Перед тем как мы приступим к рассмотрению возможного объяснения этого феномена нам необходимо познакомится с математическими объектами — графами, и с некоторыми из их свойств.

Граф это множество вершин и множество ребер, которые соединяют эти вершины. В графическом виде граф можно представить следующим образом:

У нас есть три вершины: A, B, C, и два ребра соединяющие их: AB, BC.

Может кто помнит такой вид развлечения из детства: дают набор точек и путем их правильного соединения получалась картинка какого нибудь котика. Набор точек это множество вершин, и по задаче мы рисовали к ним ребра. Граф в действии. Довольно продвинуто для детей, не находите? Так же я уже описывал такой объект как деревья, которые являются частным случаем графов.

Путь

Как видно из нашего рисунка некоторые ребра непосредственно связаны друг с другом. В нашем предыдущем примере из узла A есть ребро в узел B. Представим все ребра графа как дороги для автомобилей. Ну а там где есть дороги возможно и путешествие! Из A мы можем попасть в B, а из B мы можем попасть в C. Следовательно из A мы можем попасть в C, с промежуточной остановке в B.

Такое путешествие, а формально последовательность ребер через которые мы проходим, мы назовем путем. Длину последовательности ребер в пути будем считать длинной пути.

Итак, если мы из A хотим попасть в C, то нам необходимо преодолеть путь (AB, BC). Мы проходим два ребра, следовательно длина пути равна двум.

K-соседи

Для анализа путей вида A → C с промежуточной остановкой в B введем понятие k-соседей.

Вершина B является k-соседом вершине A если:

  1. Из вершины А есть путь в вершину B
  2. Его длина равна k
  3. Это кратчайший путь для двух данных вершин

Рассмотрим пример:

Из узла A в узел C мы можем попасть двумя путями: напрямую через ребро AC, или с промежуточной остановкой в B. Данные пути, соответственно, мы можем записать следующим образом (AC), (AB, BC). Каким же соседом C является для A? У нас есть два пути, длины этих путей равны 1 и 2 соответственно. Но для того чтобы полностью соответствовать нашему определению нам необходимо выбрать наименее короткий путь, следовательно C является 1-соседом вершине A.

Клика

Если из каждой вершины графа есть путь к любую другую вершину, то такой граф мы называем связанным.

В случае если не все вершины связаны между собой, но какое то подмножество вершин все же полностью связано, то это подмножество называется кликой графа.

Возьмем, к примеру, следующий граф:

В этом графе вершины A, B, C образуют клику, потому что у нас есть ребра из каждой вершины в каждую, а именно AB, AC, BC.

Сила

Крутость графов в том, что мы можем представлять объекты реального мира в их виде и, через такого посредника, производить вычисления над ними.

Приведем пример. В качестве вершин представим города, а в качестве ребер дороги между ними. Это называется дорожной сетью. Почему слово сеть заменило слово граф? Я, поверхностно просмотрев сеть интернет, так и не нашел ответа. Есть некая тенденция сетями называть объекты которые относятся к реальному миру, а графами объекты относящиеся к математическому. А может кому то не нравится благородство происхождения?

Так, не отвлекаемся. Представим себе гипотетическую дорожную сеть между четырьмя городами России:

Изображение схематично, не имеет общего с реальным положением дел

Используя то, что мы уже знаем о графах, проведем вычисления над этим графом. Если мы возьмем Москву как отправную точку нашего путешествия, то Санкт-Петербург, Воронеж, и Ярославль являются 1-соседями Москвы. Архангельск и Волгоград 2-соседями. Также города Москва, Ярославль, Санкт-Петербург образуют клику.

На этом мы не остановимся. Мы, также, можем вычислять кратчайшие пути между городами. Скажем, перед нами стоит задача попасть из Архангельска в Ярославль. Кратчайшим путем будет Архангельск — Санкт-Петербург — Ярославль, а не Архангельск — Санкт-Петербург — Москва — Ярославль.

Еще такой пример. Представим что мы проектируем дорожную сеть. Если на дороге из Москвы в Санкт-Петербург произойдет затор, то мы все же сможем попасть из Москвы в Архангельск через путь Москва — Ярославль — Санкт-Петербург — Архангельск. Но если произойдет затор Москва — Воронеж, то мы не сможем попасть из Воронежа и Волгограда в Санкт-Петербург. Москва является узким местом в нашей дорожной сети. Мы можем это исправить проведя дорогу между Воронежем и Ярославлем.

Звучит довольно тривиально, но переведем наши задачи в масштаб городских улиц. Скажем у нас 3 500 улиц с множеством перекрестков, на каждой из улиц разный параметр загруженности и следовательно время прохождения. Ответ на вопрос «Как быстрее попасть из пункта А в пункт Б» уже не столь тривиален. Сложность выявление узких мест в дорожной сети может стать настоящим кошмаром. Но если мы перекладываем нашу проблему на графы, то мы можем использовать алгоритмы для решения этих задач, а следовательно и компьютеры. Вот это уже звучит более интересно, не так ли?

Решение

Теперь мы полностью готовы рассмотреть наш изначальный вопрос. Для этого мы сконструируем модель социальной сети человечества.

Первое предположение: каждый человек обладает определенным кругом знакомств. У нас есть друзья, и, обычно, каждый наш друг знает другого нашего друга. Таким образом мы формируем некую клику в социальной сети, обозначим ее буквой C.

Второе предположение: у человека есть случайные знакомые не входящие в его круг знакомств. Скажем, с кем то мы учились в школе в параллельных классах или познакомились в детском лагере летом. Обозначим их буквой R. У каждого из таких случайных знакомых есть своя клика друзей, у людей из этой клики есть свои случайные знакомые и так далее. Скажем у нас есть 12 человек, в каждой клике по 3 человека, у половины по одному случайному знакомому. Социальная сеть будет выглядеть следующим образом:

Давайте посмотрим на k-соседей для A1 в нашей социальной сети. 1-соседи состоят из людей в клике С (вершины B1, C1), и произвольного друга R (вершина A2). 2-соседи состоят из произвольных знакомых людей из нашей клики (CR), и друзей из клики нашего произвольного знакомого (RC). Мы не включаем друзей клики из нашей клики (CC) потому что это теже люди что и сама клика C. В общем случае мы не включаем цепочки в которых C идет два раза подряд. Ну а с 3-соседей довольно затруднительно описать словами, поэтому просто перечислю в виде обозначений: CRR, CRC, RRR, RCR, RRC.

Я знаю вам не терпится это посчитать:

1-соседи: C + R = 2 + 1 = 3
2-соседи: CR + RC + RR = 2×1 + 1×2 + 1×0 = 4
3-соседи: CRR + CRC + RCR + RRC + RRR = 2×1×0 + 2×1×2 + 1×2×0 + 1×0×0 + 1×0×0 = 4

Куча нулей берется потому что наша сеть довольно ограничена, если бы человек было больше размер 3-соседей был бы в разы больше.

Получается что 3 рукопожатия это максимум что нам понадобится для того чтобы войти в контакт с любым человеком из этой сети.

Расширим масштаб нашей сети до 140 человек в клике и 10 случайных знакомых. Посчитаем сколько человек мы можем достать используя 6 рукопожатий:

1-соседи: C + R = 140 + 10 = 150
2-соседи: CR + RC + RR = 140×10 + 10×140 + 10×10 = 2 900
3-соседи: CRR + CRC + RCR + RRC + RRR = 140×10×10 + 140×10×140 + 10×140×10 + 10×10×140 + 10×10×10 = 239 000
4-соседи: CRRC + CRRR + CRCR + RCRC + RCRR + RRCR + RRRC + RRRR = 6 450 000
5-соседи: CRRCR + CRRRC + CRRRR + CRCRC + CRCRR + RCRCR + RCRRC + RCRRR + RRCRC + RRCRR + RRRCR + RRRRC + RRRRR = 399 100 000
6-соседи: CRRCRC + CRRCRR + CRRRCR + CRRRRC + CRRRRR + CRCRCR + CRCRRC + CRCRRR + RCRCRC + RCRCRR + RCRRCR + RCRRRC + RCRRRR + RRCRCR + RRCRRC + RRCRRR = 13 021 000 000

Тринадцать миллиардов. Впечатляет! Это почти в два раза больше чем население земли.

Так откуда возникает столь интересный феномен? Он возникает из структуры нашей сети, а именно из того что у нас есть клики друзей и случайные знакомые. Структура же возникает из того, как каждый элемент сети создает связи с другими элементами. Для объяснения теории шести рукопожатий мы предполагали что у людей есть клика близких знакомых и у каждой такой клики есть связь, некий мост, в другую клику. Вообще, такие графы называются забавным названием «Мир тесен», и что самое удивительное не только социальные сети проявляют свойства подобных графов.

Интересно наблюдать за тем как растет число контактов с ростом числа рукопожатий. Если 1-соседей у нас 150, то 2-соседей уже 2900, а 3-соседей уже 239 000. Это население довольно крупного города. Это может натолкнуть на мысль, что более слабые связи могут дать нам больше, потому что в них участвует большее количество людей. Именно эту идею представляет американский социолог Марк Грановеттер в статье «Сила слабых связей».

Конечно, это не полностью описывает то, как обстоят дела настоящем мире. Это всего лишь игрушечная модель. Но в отличии от анализа реального положения дел, со всеми его деталями, наша модель позволяет нам получить понимание того, почему теория шести рукопожатий имеет место быть.

общество  /  математика  /  социология  /  теория графов
лайк
10.03.2017

Курс «Модельное мышление»

Для того чтобы понять что такое модельное мышление для начала разберемся с моделями. Возьмем определение из Википедии:

Модель (фр. modèle, от лат. modulus — «мера, аналог, образец») — это система, исследование которой служит средством для получения информации о другой системе; представление некоторого реального процесса, устройства или концепции.

Найдем что то более интуитивное для этого определения. Предположим перед нами есть некая сложная и серьезная проблема из реального мира со множеством «двигающихся частей»: переменных, сущностей, связей. Наша задача ее лучше понять или решить. Возьмем, к примеру, распространение слухов в социальной среде. Скажем, если вы проговоритесь одному вашему другу что вы любите соленые торты, то как быстро об этой весточке будет знать каждый ваш друг и еще полгорода в придачу? Неделя, день, пару часов, или может вообще ничего дальше него так и не уйдет? Можно попытаться решить эту проблему со всеми свистелками: спросить у друга расскажет ли он кому нибудь, спросить у тех кому он расскажет кому они расскажут и так далее. Бум, и голова по всей комнате.

Мы можем пойти более простым путем, но нам придется добавить немного размышлений. Можно представить наших друзей, их друзей, и друзей их друзей в виде социальной сети. Каждый узел будет человеком, а связь между узлами означает связь между людьми. Также мы можем добавить меру болтливости: предположить, что каждый из людей распространяет слухи с некоторой вероятностью.

Moreno Sociogram 2nd Grade.png

Кружки представляют людей, а линии связывают их знакомством. Буквы в кружках можно расценивать как инициалы имен. Автор Martin Grandjean, собственная работа, CC BY-SA 4.0, ссылка

Все просто. Наша модель готова. С ее помощью мы можем изучать нашу проблему более точно, нежели на основе предположений. Мы можем менять параметры и смотреть как будет меняться ситуация в зависимости от того сколько людей знакомы с друг другом, или насколько они болтливы. И вне зависимости от того что вам больше по душе: мой неловкий пример, или определение из вики, этот стиль мышления таит в себе огромный потенциал.

Так что же такое модельное мышление? Собственно это и есть использование моделей для изучения и решения реальных проблем. Причем не обязательно одну модель для одной проблемы. Мы можем использовать множество моделей для рассмотрения одной проблемы, или же одну модель для изучения множества вопросов. Это следствие того, что наши модели это абстракции реальных проблем. В нашем примере человек перестает быть индивидуумом, со своими желаниями и эмоциями, а становится лишь точкой в социальной сети, и этой точке без разницы чем она является. Используя ту же модель мы можем анализировать проблему распространения сигнала в компьютерной сети, в которой есть точки отказа. Модели плодовиты, и это мощь!

В чем магия? В Одиссеи Гомера был такой сюжет (из Википедии):

Прожив у Цирцеи год, Одиссей отправляется дальше, мимо острова сирен, влекущих своим чарующим пением моряков на гибель. Своим гребцам он затыкает уши воском, сам, полный любопытства, приказывает привязать себя к мачте и слушает. Так они минуют угрозу.

Вот хитрец! И волки сыты и овцы целы (в быту я более интересную версию использую). Так, а какое отношение это имеет к нашим моделям? Наши модели привязывают нас к мачте логики, которая в свою очередь помогает нам более эффективно исследовать проблему. Логика направляет нас в наших исследованиях и открывает для нас те свойства проблемы, которые не может открыть мышление «здравым смыслом». Все это помогает нам более точно мыслить, а как результат мы можем принимать более рациональные решения и улучшить нашу жизнь до невиданных высот.

Собственно, курс

Со всем этим великолепием нам поможет ознакомиться замечательный курс «Модельное мышление». Он состоит из десяти недель. После каждой пятой недели вас ждет небольшой экзамен в виде теста. Каждая неделя разбита на 2 модуля и содержит проверочный тест в конце. Широта охватываемых тем и количество моделей которую покрывает курс просто нереальная. Среди них такие вопросы:

  • Почему в американских городах большая сегрегация?
  • Как принять грамотное решение в ситуациях неопределенности?
  • Как предсказать победителя на выборах президента?
  • Как и почему расчет экономика?
  • Что такое процессы Маркова и функция Ляпунова?
  • Как можно представить культуру в виде модели?
  • Почему работает теория семи рукопожатий?
  • Что такое мудрость толпы?

И это очень как далеко не все, подчеркну еще раз: далеко не все темы. Огромное число моделей, и как мы говорили выше их можно использовать и в других проблемах, вплоть до бытовых. А если и этого мало к каждой неделе еще прилагаются материалы для чтения: научные статьи или отдельные главы книг. На закуску у нас программа НэтЛого в которой можно запустить компьютерную симуляцию модели и воочию наблюдать ее работу и менять ее параметры. Безграничные возможности!

Каждый модуль курса самодостаточен и ну очень интересный. Обычно в процессе столь долгого курса под конец интерес очень сильно падает, и это превращается в какую то каторгу. Но не в этом случае.

Обилие матана пугаться не стоит, достаточно простой школьной алгебры. В процессе вы ознакомитесь с теорией игр, автоматов, вероятности, плюс немного статистики. Но это все великолепно и интересно объясняется.

Как мы говорили выше курс на широкую ногу, затрагиваемых тем очень много. В связи с этим он не раскрывает все во всех деталях, но каждый модуль служит хорошим приглашением и мотивацией для дальнейшего самостоятельного исследования.

В заключении скажу что пройти этот курс очень рекомендую я. 10/10. Это один из тех редких курсов который сможет поменять то как вы видите и думаете о мире.

курсера  /  моок  /  математика
лайк
27.02.2017

Представление проблем

На протяжении возможности долгой и беззаботной жизни, которую нам предоставляет современный мир, мы сталкиваемся с множеством проблем. Некоторые из них довольно простые, симметрично, некоторые довольно сложные. Это свойство можно измерить, скажем, по количеству минимального времени которое необходимо потратить для решения проблемы. Под минимальным временем я имею ввиду такое количество времени, которое бы затратил лучший из лучших для решения данной проблемы. Это вполне объективно. Но есть и еще одна сторона монеты: как каждый из нас «видит» данную проблему. Назовем это представлением. Грубо говоря кто то ищет правосудия в суде сквозь логические аргументы, а кто то сквозь огнестрельные:

Игра

Обернем это в математическую обертку для того чтобы посмотреть на это в действии. Рассмотрим игру «В сумме 15» со следующими правилами:

Есть два игрока и карты с номерами с 1 по 9. Игроки берут карты по очереди, начиная с первого игрока. Побеждает тот игрок у которого на руках 3 карты, которые в сумме дают 15.

Предположим что у игрока на руках карты 9 3 5 4 2. Он побеждает потому что 9 + 4 + 2 = 15.

Что мы можем сказать о данной игре? Она может оказаться простой или сложной (наподобие тех в которых тебя облапошивают уличные мошенники). Для того чтобы это понять проведем тестовый матч. В левом углу воображаемого ринга Алиса в роли игрока № 1, в правом Боб в роли игрока № 2.

Стол
Алиса
Боб

Нажмите чтобы проиграть демо

Как мы условились первое право выбора карты за Алисой. Она берет четверку. Боб думает что это странный выбор и берет пятерку. Ход переходит Алисе. Она делает еще более странный ход и берет шестерку. Боб впадает в сомнения. Тут две возможности: либо Алиса хитрая, либо она не понимает сути игры. Боб берет восьмерку. Алиса с победоносным видом берет двойку. Боб включает арифметику и производит расчеты. Если он не возьмет девятку то Алиса победит (4 + 2 + 9 = 15). Но если он не возьмет семерку то Алиса так же победит (6 + 2 + 7 = 15). Взять он может только одну карту. Боб оказался в ловушке и с грохотом продул.

Игра не такая простая как хотелось. Если ее решать в лоб то можно взять все тройки карт которые в сумме дают 15 и следить какие карты взял противник. Вот все возможные комбинации:

  • 2 + 7 + 6
  • 2 + 5 + 8
  • 9 + 5 + 1
  • 4 + 3 + 8
  • 4 + 5 + 6

Конечно, никто не хочет казаться безмозглым придурком который играет в такую простую игру с бумажкой и ручкой и каждый его ход занимает по минуте. По крайней мере я бы предпочел выглядеть умно и решать все в голове.

Магия

Вернемся к нашим комбинациям. Я их перетасовал немножко чтобы запутать ваc, но теперь приведем все в порядок:

15 15 15
2 7 6 15
9 5 1 15
4 3 8 15
15 15

Как видно из таблицы выше эти числа можно организовать в очень интересную структуру, которая имеет замечательное название «Магический квадрат». Каждая строка, столбец и диагональ в сумме дают 15. Это число называется «Магическим числом». Итого у нас есть по три числа в группе (строка, столбец, диагональ), каждая тройка этих чисел в сумме дает 15. Ах, да это же наша изначальная проблема. Но та часть, которая мне нравится больше всего, все еще впереди. Представим игру Алисы и Боба используя магический квадрат:

15 15 15
2 7 6 15
9 5 1 15
4 3 8 15
15 15

Не выглядит ли это как что то до боли знакомое? Мы поочередно ходим, выбирая по одной клетке, для того чтобы собрать строку, столбец или диагональ. Cтарые знакомые крестики-нолики подойдут под это описание. То что мы сейчас сделали это сконструировали представление для нашей начальной игры, которое, возможно, поможет нам играть более эффективно. Мы можем играть в крестики-нолики используя представление которое описанно в наших начальных правилах, можем играть в нашу начальную игру используя представление крестиков-ноликов, но являются ли эти две проблемы идентичными вопрос оставлю открытым.

Итог

Что же у нас получилось? Для начала посмотрим на ингредиенты. У нас есть проблема в виде игры решение которой в том виде в котором она нам представлена, через правила, может быть весьма запутанным или даже невозможным. В таких случаях мы можем попробовать сконструировать представление которое описывает нашу проблему по другому, оголяет ее структуру, делая решение простым и очевидным. Все это конечно ведет к прибыли и успеху.

Развивая эту идею можно прийти к интересному размышлению: разные представления ведут к разным решениям. Скажем вы хотите пообщаться с людьми, что переведем как выпить. Рассмотрим два решения: позвать много людей, чем больше тем лучше, или же посидеть тихонько с друзьями, чем ближе тем лучше. Можно это изобразить как количество и качество. Сначала пойдем количественным путем. Мы позвали кучу людей, но все знают чем это обычно оборачивается: вы оказываетесь в кругу в котором большинство берут идиоты. Ваша оценка 4/10. Если мы пойдем другим путем то мы душевно посидим на 10/10. Итак у нас есть 4/10 и 10/10. Первый случай нам принес меньше прибыли, это субоптимальное решение. Второй путь нас приводит к оптимальному решению. Первое представление полностью блокирует оптимальное решение потому что мы мыслим в категории количества. Проблема может быть в том что разные представления включают в себя разное количество частей объективной проблемы. Ну в общем я тут не могу представить ответа, так что оставляю это так.

математика
лайк
04.03.2015

Парадоксы Зенона

Бесконечность интересная и таинственная вещь. Но совершенно не понятно может ли наш мозг понять и принять ее? Я уже рассказывал вам о бесконечном отеле Гильберта и мне все это кажется чем-то ненатуральным, чьей то безумной фантазией. Но бесконечность может быть гораздо ближе к реальности, чем закрома нашего разума. Предлагаю вашему внимаю два парадокса о движении, которые сформулировал Зенон Элейский где то в 5 веке до нашей эры.

Чтобы по-настоящему насладится этими парадоксами, надо знать, что рациональные числа обладают свойством плотности. Оно говорит нам следующее: между двумя неравными рациональными числами всегда можно найти рациональное число которое меньше большего числа и больше меньшего. То есть: ∀(a,b ∈ Q)∃(m ∈ Q): a<b ⇒ a<m<b. Это свойство позволяет нам говорить о том, что между вещественными числами 0 и 1 существует бесконечное число рациональных чисел (½, ⅓, ¼, ⅕, ..., ∞). Доказательство.

Гонка Ахиллеса и черепахи

Устроим небольшое воображаемое соревнование. На стартовой линии стоит греческий герой Ахиллес, воин и атлет, символ скорости и силы своего времени. И черепаха. Что? Черепаха? Бред, как черепаха может соревноваться с Ахиллесом? Я думаю, вы бы не стали возражать, если бы мы дали черепахе фору в 100 метров для того, чтобы Ахиллесу пришлось хотя бы немного размять свои мышцы перед триумфальной победой. Предположим, что в целом нашим спортсменам надо преодолеть дистанцию в 1000 метров.

Кстати, на кого вы бы поставили ¤ в этой математической гонке?

Судья взводит стартовый пистолет. На старт, внимание, бдыщь!

Для того, чтобы Ахиллесу обогнать черепаху, ему необходимо сначала ее догнать. Пока Ахиллес бежит 100 метров форы черепаха пробегает еще 10. Черепаха вновь впереди Ахиллеса, он вновь бросается ее догонять и пробегает еще 10 метров. В это время черепаха проползает еще 1 метр. Этот процесс может продолжаться до бесконечности, в которой Ахиллес так и не догонит черепаху.

Проиграли ставку? Но это ничего, ведь деньги у нас не настоящие (в отличии от банков ☺).

Википедия дает данную формулировку этого парадокса:

Допустим, Ахиллес бежит в десять раз быстрее, чем черепаха, и находится позади неё на расстоянии в тысячу шагов. За то время, за которое Ахиллес пробежит это расстояние, черепаха в ту же сторону проползёт сто шагов. Когда Ахиллес пробежит сто шагов, черепаха проползёт ещё десять шагов, и так далее. Процесс будет продолжаться до бесконечности, Ахиллес так никогда и не догонит черепаху.

Представить такую гонку на компьютере нет возможности. Как думаете, почему? Потому что компьютер не может делить бесконечно, так как у нас нет бесконечной памяти, чтобы хранить числа произвольной длинны. Благодаря этим свойствам Ахиллес и черепаха в компьютерной гонке все же окажутся в одной точке. Но, несмотря на это, ее смысл мы можем представить так:

1000 метров
И так до бесконечности.

Давайте сделаем еще одну визуализацию. Для этого мне понадобятся ваши руки. Расставьте их на расстоянии одного метра. Правая рука стоит не подвижно, а левая начинает движение к ней. Но не плавное, сначала левая рука приближается к правой на половину начального расстояния, то есть на 50 сантиметров. Потом на половину полученного расстояния, то есть на 25 сантиметров, потом на половину этого и так далее. До бесконечности. Забавно, да? Вы только что завершили бесконечный процесс своим хлопком.

Еще одна хорошая визуализация, которую опять же нельзя по настоящему представить на компьютере, это построение квадрата из бесконечного числа прямоугольников. Берем квадрат, скажем, 100 на 100 единиц измерения, делим его пополам, одну половину делим еще раз на две равные части, еще одну полученную половину делим пополам. И так далее, до бесконечности. Да, наш конечный квадрат состоит из бесконечного числа меньших прямоугольников:

Так о чем это? О бесконечном процессе и его конечном завершении. Как же Ахиллесу удается настичь и обогнать черепаху в этой нелегкой гонке? Почему наши руки сходятся в хлопке, завершая процесс у которого нет финального шага? И еще: как конечный кусок материи может состоять из бесконечного числа частиц, как в случае с нашим квадратом?

Дихотомия

Дихотомия в переводе с греческого значит «Деление пополам», именно так Аристотель назвал этот парадокс Зенона.

Давайте представим что мы решили прогуляться в парк. Парк находится от нас в 100 метрах. Для того, чтобы пройти 100 метров, надо сначала пройти 50 метров. А для того, чтобы пройти 50 метров, нам надо пройти 25 метров. Вы уже поняли к чему я клоню? Да, к бесконечности процесса деления этого расстояния. Движение невозможно!

Есть забавная выдержка в которой противник Зенона, чтобы доказать обратное, начал просто ходить перед ним:

Еще как-то, защищая того же учителя, утверждавшего, что сущее неподвижно, он выдвинул пять эпихейрем в пользу того, что сущее неподвижно. Антисфен-киник, который не смог на них возразить, встал и стал ходить, полагая, что доказательство делом сильнее всякого возражения словом.

Википедия дает нам такую формулировку этого парадокса:

Чтобы преодолеть путь, нужно сначала преодолеть половину пути, а чтобы преодолеть половину пути, нужно сначала преодолеть половину половины, и так до бесконечности.

Представим это визуально:

100 метров
или подождем еще минутку?

Как мы видим, этот парадокс похож на парадокс Ахиллеса и черепахи, только в отличии от последнего, у него отсутствует точка старта — что и делает невозможность совершить шаг.

Заключение

Данные парадоксы обсуждаются уже более 2000 лет, и, как говорит нам Википедия, научное сообщество до сих по не пришло к общему мнению о сущности парадоксов. Мне нравятся эти парадоксы тем, что они, при достаточном погружении в их суть, задают интересные вопросы, которые, как мне кажется, уходят корнями во что-то очень базовое:

  • Как бесконечное действие может завершиться?
  • Есть ли конечная мера у времени и пространства, или его можно делить до бесконечности?
  • Если время можно делить бесконечное число раз, тогда как быть с такими вот парадоксами?
  • Если пространство бесконечно, то как конечные предметы могут состоять из бесконечного числа частиц?
  • Как физический процесс за конечное время принимает бесконечное множество значений?

Я говорю с позиции профана и в этих вещах не разбираюсь, если у вас есть ответы на эти вопросы, я бы очень хотел прочитать о них в комментариях к посту. Или, возможно, у вас возник тоже какой-то интересный вопрос?

В качестве бонуса интересное видео по теме:

математика
лайк
25.10.2013

Гостиница Гильберта. Ответ

Эту задачу предложил немецкий математик Давид Гильберт где то в третьем десятилетии 20 века. Давид был одним из величайших умов своего времени. Среди большого числа его учеников, которые в последствии стали видными учеными, был Джон Фон Нейман. Он так же консультировал Эйнштейна при разработке тензорного анализа — фундамента теории относительности.

Один гость

Напомню вам условие задачи для одного гостя из предыдущей статьи:

Представьте себе гостиницу с бесконечным числом комнат. Комнаты пронумерованы натуральными числами, от 1 до ∞. В один прекрасный день в нашу гостиницу вошел человек и попросил снять комнату. К сожалению, для нашего гостя не нашлось комнаты, так как именно в этот день отель был полностью заполнен бесконечным числом гостей. Выгнать гостя? Или все же есть возможность предоставить ему свободную комнату не выселяя никого из постояльцев?

Несмотря на то, что задача явно говорит что все номера заняты, мы все же можем выделить сколько угодно свободных комнат. Давайте просто переселим человека из первой комнату во вторую, человека из второй комнаты в третью и так далее. То есть, каждого гостя из комнаты с номером n переселим в комнату с номером n+1, n→n+1. В результате этого у нас освобождается комната с номером один, и мы с радостью можем поселить нашего нового гостя.

Бесконечное число гостей

Напомню условие:

Если вы смогли найти комнату для одного гостя значит вы замечательный администратор. Но всегда есть простор для улучшения ваших навыков. Представьте что в полностью заполненный бесконечный отель приехало бесконечное число гостей. Как бы вы поселили бесконечное число гостей, при этом не выселяя никого из бесконечного числа постояльцев?

Задача стала интереснее. Может ли бесконечность вместить еще одну бесконечность? Для решения предыдущей задачи мы переселили каждого гостя на один номер вперед. Этот подход можно применить для любого конечного числа постояльцев. Если n номер комнаты постояльца, а m число прибывших гостей, тогда каждого постояльца надо переселить в номер n+m, чтобы освободить m номеров для m гостей. Но что если число гостей бесконечно, то есть m=∞?. Чему равно n+∞? Давайте попросим «Вольфрам Альфа» дать нам ответ: n+∞=∞. То есть, надо переселить каждого постояльца на номеров. Нет, это нам не подходит. Но задача имеет решение, давайте взглянем на определение четного числа:

Четное число — целое число, которое делится без остатка на 2.

Что если мы возьмем номер постояльца и умножим его на два? В результате мы получим четное число, так как оно будет делится на два. Следовательно если мы переселим каждого гостя из номера n в номер 2×n, n→2×n, мы получим бесконечное число нечетных свободных комнат, и мы сможем поселить бесконечное число гостей. Только не спрашивайте сколько времени займет переселения гостя из комнаты номер 8140406085191601 в комнату номер 16280812170383202.

***

Этот парадокс хорош тем, что он отлично показывает странные, но вполне логичные свойства бесконечности в простых и понятных сущностях. Посмотрите так же этот интересный ролик:

загадка  /  математика
лайк
22.10.2013

Гостиница Гильберта

Представьте себе гостиницу с бесконечным числом комнат. Комнаты пронумерованы натуральными числами, от 1 до ∞. В один прекрасный день в нашу гостиницу вошел человек и попросил снять комнату. К сожалению, для нашего гостя не нашлось комнаты, так как именно в этот день отель был полностью заполнен бесконечным числом гостей. Выгнать гостя? Или все же есть возможность предоставить ему свободную комнату не выселяя никого из постояльцев?

Если вы смогли найти комнату для одного гостя значит вы замечательный администратор. Но всегда есть простор для улучшения ваших навыков. Представьте что в полностью заполненный бесконечный отель приехало бесконечное число гостей. Как бы вы поселили бесконечное число гостей, при этом не выселяя никого из бесконечного числа постояльцев?

Ответ.

загадка  /  математика
лайк