Ахен и Кёльн

Ехали с sasmok и Натанкиным в машине. Сына, спрашиваем, как ты думаешь, какой город самый первый в алфавитном порядке? Он предсказуемо начинает генерировать что-то, начинающееся с Abc... Потом постепенно доходит до варианта Aba... Но победитель всё равно Aachen, он же Ахен, он же Aix-la-Chapelle. Мы хотели туда заехать, потому что это — столица Карла Великого, а без него не обходится ни один французский учебник истории.

От дворца Карла Великого осталась одна часовня, но какая же она красивая!


( Read more... )

Pour la science № 493 — мелочи

Статья о том, почему даже те люди, которые верят в глобальное потепление, не принимают практически никаких мер по борьбе с ним. Лично мне ответ на этот вопрос очевиден: во-первых, сложно начать терять что-то гарантированно и сейчас ради выигрыша возможно и потом; а во-вторых, особенно сложно это делать без гарантии, что тебя поддержат другие (потеряешь только ты, а выгоду получат все).
Но в статье рассказывают о другом факторе. О перенасыщении мозга — якобы, нам каждый день рассказывают о стольких опасностях, что мы теряемся в выборе: с чем именно бороться, с чего начать? И в этом контексте приводят прекрасный эксперимент, когда в супермаркетах ставят выносную витрину с «экзотическим вареньем». В половине супермаркетов на этой витрине находится всего 6 видов варенья, а в другой — вдвое-втрое больше. Более богатые витрины привлекают больше внимания — возле них люди останавливаются чаще, и времени они там проводят больше. А вот покупок совершают меньше. По мнению авторов эксперимента, он говорит о том, что слишком большой выбор не даёт нам возможность принять решение.

---

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



Синее колесо может катиться по наклонной плоскости, на красных спицах у него расположены грузы. Как нужно расположить грузы, чтобы колесо скатилось как можно скорее? (правильный ответ: максимально отодвинуть от центра груз на верхней спице, максимально приблизить к центру на всех остальных)
У вас есть 4 попытки, после чего вы передаёте ход следующему человеку из вашей команды. Этот следующий не знает, что именно вы уже пробовали, вы ему оставляете только самый лучший из испробованных вами вариантов.

Я не вдавался в подробности, но организаторы эксперимента говорят, что они наблюдают постепенное улучшение модели (рано или поздно команды находят оптимальную конфигурацию), при этом каждый отдельно взятый участник эксперимента как не понимал, почему этот вариант — самый лучший, так и не понимает этого. И именно в этом авторы видят одно из ключевых отличий человека от других животных: мы умеем не только качественно имитировать поведение других собратьев, но и фиксировать достигнутое. Не вдаваясь в подробности :-)

---

Статья о роли геологов в Первой мировой войне. Пишут о поиске воды — я как-то не задумывался, но действительно: людей нужно поить, лошадей нужно поить. И в траншейной войне становится крайне важно иметь колодец на своей стороне относительно линии фронта.
Но самое впечатляющее — это затопление линии фронта в Бельгии. Для того, чтобы осенью 1914 году остановить наступление немцев, командование приняло решение открыть морские дамбы и затопить полосу в несколько километров шириной. Эта полоса оставалась неприступной до конца войны — и нападать по колено в воде нереально, и траншеи все затопило.

---

Статья о том, почему слоны не болеют раком? Логика вопроса в том, что, если рассматривать запуск рака как случайный процесс (мутация, после которой здоровая клетка становится раковой), то чем больше клеток в организме, и чем дольше он живёт, тем больше шансов умереть от рака. Слоны в этом смысле — идеальные клиенты: клеток много, живут долго.
Дальше авторы рассматривают возможные варианты противораковых защитных механизмов, я же зацепился за инфографику: «у слона 37 миллионов клеток, у человека в 1000 раз меньше, у мыши — ещё в 1000 раз меньше». Выходит, у мыши всего порядка 37 клеток? Скорее всё же в журнале потеряли несколько порядков.
Смешное начинается, когда ты пытаешься найти «количество клеток у мыши», а первые 10 результатов рассказывают тебе про Excel (мышка, клеточки, всё сходится). На каком бы языке ты это ни искал :-)

Pour la science № 493 — граф Радо

Статья про совершенно сумасшедший объект в математике :-)

Начинается статья с «универсальных чисел» (я не знаю, как перевести nombre univers) — чисел, десятичная запись которых содержит любое конечное десятичное число. Для простоты цифры записываются после десятичной запятой. Например, постоянная Чемперноуна = 0,1234567891011121314... — это универсальное число.
С универсальными числами связано множество парадоксов: практически любой объект можно представить в виде конечного числа (текст => его побуквенная запись, картинка => попиксельная запись и т.д.), а поскольку универсальное число содержит в себе все конечные числа, то да, в них есть любая когда бы то ни было написанная книга. И ненаписанная тоже. Описание того, что вы будете делать завтра. Фотография вашего пра-пра-прадедушки, несмотря на то, что тогда ещё не было фотоаппаратов. И фотография, где вы рядом с ним. Ну и так далее.
Обычно все эти байки рассказывают про число Пи, но его универсальность пока ещё гипотетическая, она не доказана.

Так вот, универсальных чисел бесконечное количество. А если мы попытаемся перенести вот этот признак универсальности на графы, там будет ровно один универсальный граф — граф Радо.

Сначала, что такое «граф», что такое «равно», и что такое «содержится»?
Графы мы рассматриваем счётные и ненаправленные, то есть как счётный набор вершин (названных или перенумерованных) и счётный набор ненаправленных рёбер между вершинами (ребро [a, b] эквивалентно ребру [b, a]), причём между двумя вершинами не может быть более одного ребра, и ребро не может соединять вершину саму с собой.
Равенство мы будем понимать как изоморфность: то есть, два графа считаются одинаковыми, если можно переименовать / перенумеровать вершины этих графов таким образом, что список вершин и список рёбер у них будет записываться одинаково.
И мы будем считать, что граф A содержится в графе B, если в графе B можно выделить подграф C, включающий часть вершин графа B, а также все рёбра графа B, соединяющие вершины, отобранные для графа C, — и при этом C «равен» A.

Теперь определение графа Радо. Перенумеруем все вершины целыми неотрицательными числами, начиная от 0. Пусть a < b. Между вершинами a и b есть ребро тогда и только тогда, если в двоичной записи числа b a-я цифра не равна нулю (цифры считаются справа налево, начиная с нулевой). Например, 12 записывается как 1100, то есть 12-я вершина связано со 2-й и 3-й, а больше ни с какой вершиной, имеющей меньший номер, не связано.

Совершенно экзотическое определение, но через него крайне легко показать, что этот граф обладает прекрасным свойством расширяемости: для любых двух несвязанных друг с другом подмножеств A и B можно найти вершину X, которая будет связана со всеми вершинами множества A и ни с одной вершиной множества B.
Казалось бы, чем это нам поможет? Но именно через это свойство элементарно показывается, что а) все возможные конечные графы содержатся в графе Радо, назовём это свойство универсальностью; б) все возможные универсальные графы изоморфны графу Радо.

Когда я говорю «элементарно» — это означает, что автор статьи смог привести понятные мне доказательства длиной в несколько строчек. После чего написал параграф в духе «Элементарно, но настолько невероятно, что я несколько раз проверил. И всё равно не до конца верю написанному».

Дальше автор рассказывает о случайных графах: при добавлении каждой новой вершины случайным образом определяется, с кем она будет связана. Бесконечные случайные графы тоже расширяемы, а значит — равняются графу Радо. В этом месте автор цитирует Эрдёша, сожалевшего, что этим фактом закрывается тема бесконечных случайных графов. Это единственная известная ему область, в которой переход от конечного количества элементов к бесконечному радикально упрощает задачу.

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

Отличный объект!

---

Порадовала библиография статьи. Помимо исторически важных статей, автор цитирует Википедию. Само по себе это уже давно нормально, но до сих пор я видел цитирование как сайта, то есть, с указанием адреса страницы. Здесь же Википедия, наконец-то, цитируется как энциклопедия: «Википедия, „Граф Радо“, 2018».