July 30th, 2021

moose, transparent

панегирик америке

Мне кажется, очень интересная запись от блоггера и генетика Разиба Хана: "Get lucky".

Хан уже много лет пишет известный блог о генетике под названием "Gene Expression" (но эта запись написана в личном блоге на новой модной платформе Substack). В 2015-м году газета Нью-Йорк Таймс предложила ему престижный контракт колумниста, но тут появились гневные статьи о том, что Хан в прошлом публиковался в том числе в журнале Taki's Magazine, известном своей бескомпромиссной политикой печатать сколь угодно одиозных авторов: там публиковались расисты (настоящие), отрицатели Холокоста, итд. итп. Нью-Йорк Таймс отозвала свой контракт, эта история наделала много шума и иногда ее называют одним из предвестников "культуры отмены" последних лет.

В заметке Хана есть немало интересного об его жизни, детстве в Америке (он прибыл в страну в пятилетнем возрасте с родителями, иммигрантами из Бангладеш), его увлечением генетикой, ДНК, секвенированием - в 2014-м году Хан секвенировал геном эмбриона своего нерожденного ребенка, вроде бы впервые в истории. Но кроме того он пишет о том, что невзирая на те трудности, с которыми он лично столкнулся, он убежден, что Америка остается самой свободной страной в мире, если ты хочешь свободно говорить все, что тебе хочется сказать, не оглядываясь на то, что это кому-то не нравится. Да, в современной Америке можно за это потерять место работы (или контракт в газете), и это плохо. Но Хан сравнивает это с тем, как в его родной Бангладеш в прошлом десятилетии религиозные активисты, вооруженные мачете, зарубили до смерти 11 блоггеров-атеистов - не всех сразу, а по одному, в их домах, в кафе или университетах - просто за то, что они писали блоги о том, что они атеисты.

Да, не везде в мире Бангладеш. Но почти во всех странах мира можно сесть в тюрьму за то, что высказываешь мысли, которые никому не угрожают, никаких гос. секретов не раскрывают, но не нравятся властям. Где-то вас посадят в тюрьму за оскорбление ислама или других религий. Где-то - за "призыв к нарушению территориальной целостности". Где-то за отрицание Холокоста. Где-то за оскорбительные слова о какой-то расе или этнической группе. Во многих местах сразу за несколько из этих вещей. Очень мало есть мест на земном шаре, где у людей есть свобода высказывать сколь угодно крамольные мысли. В Америке это право продолжает защищать Первая поправка к конституции, и она реально работает. Да, там (и в других западных странах) есть очень печальная тенденция последних лет к растущей нетерпимости к неортодоксальным мнениям. Но не забывайте о людях, которые сидят в тюрьмах по всему земному шару за то, что публично высказывали свои убеждения. И не забывайте о блоггерах-атеистах в Бангладеш.

Хан заканчивает свою заметку так:

"Три вещи я скажу вам с полной уверенностью:

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

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

Я не знаю, как это все закончится, но меня устраивает то, как я использовал свой чудесный дар свободы. А вас?"


Разиб Хан в Америке 80-х
moose, transparent

community

catpad хорошо написал о сериале "Сообщество" (Community):

Тут дело такое. Дэн Хармон, прежде чем сделать «Rick & Morty», создал «Community». Дальше начинается загадочное: в то время как «Rick & Morty» почему-то стал супер популярным и культовым, «Community» до сих пор мало кому известно. И это не только несправедливо, это по меньшей мере глупо, потому что (по моему скромному мнению) R&M в подмётки не годится «Community». Это поистине потрясающий сериал. Нет — потрясающий сериал. В общем, зачем мне писать много слов, если вам тут всё отлично расскажут:





Я не согласен с тем, что "Рик и Морти" в подметки не годится "Сообществу", но согласен с тем, что это отличный и незаслуженно малоизвестный сериал. Первые несколько серий немного обманчивы, они не более чем хороши; потом поток мета-наблюдений и отменных шуток и мета-шуток начинает нарастать, и это становится просто отлично.
moose, transparent

пятая задача олимпиады

Пятая задача Международной математической олимпиады в этом году была средней по сложности; ее целиком решили 175 участников.



Она имеет отчетливый алгоритмический оттенок. Не очень легкое для понимания условие. В 2021 ямок положены в произвольном порядке 2021 пронумерованных ореха. На шагу номер k у ореха под номером k его соседи меняются местами. Иногда оба его соседа будут больше, чем он, по номерам, иногда оба меньше. Надо доказать, что хотя бы один раз случится, что один сосед будет больше, а другой - меньше. Просто-таки просится идея найти какой-нибудь удобный инвариант всего порядка орехов, но я такого найти не смог, хотя пытался. В итоге мое решение немного по-другому работает.

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

Дальше идет мое решение, если хотите решать сами, не смотрите.
[Spoiler (click to open)]

Введем немного терминологии. Когда на k-m шагу у ореха номер k меняются местами соседи, назовем это "орех номер k стреляет". Если в какой-то момент времени шаг номер k уже случился, то орех номер k называется "выстрелившим", а если еще не случился - "невыстрелившим". Далее, если в момент выстрела оба соседа больше по номерам, чем стреляющий орех, назовем это "выстрел вверх". Если оба меньше, назовем это "выстрел вниз". Если один меньше, один больше - "выстрел наискосок". Наша задача - доказать, что есть хотя бы один выстрел наискосок. Для этого мы прямо сейчас предположим, что их нет ни одного, и в конце придем к противоречию.

Итак, выстрелы могут быть только вверх (меняются местами два соседа номерами больше нашего) или вниз (номерами меньше нашего). Отсюда мы делаем следующее важное НАБЛЮДЕНИЕ: при любом обмене мест на место невыстрелившего ореха приходит другой невыстреливший, а на место выстрелившего - другой выстреливший. Это соответствует выстрелу вниз и выстрелу вверх соответственно.

Теперь о главной идее доказательства. Я хочу доказать, что на протяжении всех 2021 шагов выстрелов вверх встречается меньше, чем выстрелов вниз. Обратите внимание, что первый выстрел (орех номер 1) всегда вверх, последний (орех номер 2021) всегда вниз. На первых номерах преобладают выстрелы вверх, на последних вниз, посредине может быть по-разному, но я хочу доказать, что всего выстрелов вверх меньше, чем вниз.

Предположим, что я это доказал. Теперь представим себе, что мы взяли конечное состояние, после 2021-го выстрела, и разматываем его в обратном направлении: сначала опять меняем соседей 2021-го, потом соседей 2020-го и так далее. В конце мы придем к исходному состоянию. Используя ровно то же доказательство, что я сейчас приведу ниже (про то, что выстрелов вверх меньше), но с заменой везде "вверх" и "вниз" симметрично, можно видеть, что "обратное направление" доказывает, что наоборот, выстрелов вниз меньше, чем выстрелов вверх. Это и есть противоречие, которое нам нужно, и после этого доказательство завершено. Это может показаться немного сложным для понимания или "читерством", но продумайте эту идею симметрии и "размотки обратно" как следует, она работает.

Теперь мне осталось доказать, что выстрелов вверх (когда меняются соседями с большими номерами) меньше, чем выстрелов вниз (меняются соседями с меньшими номерами). Рассмотрим четыре ямки, идущие подряд, назовем их A B C D в этом порядке. Предположим, что только что произошел выстрел вверх в орехе, который лежит в ямке C, и вот теперь в ямках лежат какие-то орехи примерно так:

A=? B=300 C=100 D=?

Я взял тут B=300 и C=100 для наглядности, на самом деле там могут быть любые номера, кроме того, что номер в B > номера в C, потому что это был выстрел ВВЕРХ. Я теперь хочу доказать следующие два утверждения:

Во-первых, больше уже никогда не выстрелит орех в ямке C. Это следует из НАБЛЮДЕНИЯ выше: в C сейчас лежит выстреливший орех, и туда может в будущем придти только выстреливший орех.
Во-вторых, когда орех в ямке B выстрелит, какой бы номер это ни был, это будет выстрел ВНИЗ. Почему это верно? Рассмотрим следующее свойство: "в B лежит невыстреливший орех, а в C лежит выстреливший орех". Это свойство верно прямо сейчас, но когда-нибудь оно станет неверным, потому что все орехи рано или поздно выстрелят. Однако орех в C уже никогда не выстрелит (только что доказано), а выстрелы в ямках A и D, хотя и могут заменить орехи в B и C на другие, сохраняют тот факт, что в B невыстреливший, а в C выстреливший (согласно НАБЛЮДЕНИЮ). Значит, это изменится только когда выстрелит орех в B, и в этот момент в C будет лежать уже выстреливший орех, т.е. меньший по номеру, чем в B. Значит, это будет выстрел ВНИЗ.

Для чего мне нужно было это техническое рассуждение? Я теперь могу сказать, что каждый выстрел вверх из какой-то ямки порождает две ямки - слева и справа от стреляющей - которые точно рано или поздно выстрелят вниз (в абзаце выше мы рассмотрели это для ямки слева, но для ямки справа работает точно такой же аргумент). Более того, выстрелившая вверх ямка уже никогда не выстрелит снова. Это не значит, однако, что выстрелов вниз в два раза больше, чем вверх - потому что каждая из этих "порожденных ямок справа и слева" может также быть "порождена" выстрелом вверх с другой стороны. Поэтому некоторые выстрелы вверх "порождают" два новых кандидата на выстрел вниз, некоторые только один, некоторые даже ноль, потому что их ямки слева и справа уже "порождены" предыдущими выстрелами вверх.

Мы можем, однако, оценить число выстрелов вниз с помощью графа. Каждый раз, когда стреляет ВВЕРХ орех из какой-то ямки, представьте себе, что мы проводим ребро, соединяющее ямки слева и справа от стреляющей. Обе вершины этого ребра когда-нибудь выстрелят ВНИЗ. Из-за того, что выстрелившая вверх ямка больше не стреляет, ребро создается только один раз. Иногда эти ребра присоединяются концами друг к другу. Если ребро появилось с двумя новыми кандидатами, то это тривиальный пример ДЕРЕВА (графа без циклов). Когда ребро присоединяется к существующей вершине (один новый кандидат), это расширяет дерево. Когда ребро соединяет два существующих кандидата, это соединяются вместе два дерева в одно. В общем случае по мере того, как происходят выстрелы вверх и создают новые ребра, мы получаем лес (набор деревьев из одного или больше). В любом дереве число вершин на 1 больше числа ребер, а если в лесу больше одного дерева, так тем более больше. Единственный способ для нашего леса перестать быть лесом - это если замкнется цикл из этих ребер. Каждое ребро соединяет ямки на расстоянии 2 друг от друга. Казалось бы, если обойти все ямки по кругу, есть надежда замкнуть цикл - но нам помогает то, что 2021 нечетное число, и после обхода по кругу мы попадем "между" начальных ребер, а не присоединяемся к ним. Полный цикл из таких ребер может быть только длиной 2021, но ясно, что не может быть, чтобы все 2021 шага были выстрелами вверх, так что это невозможно. Значит, мы всегда будем иметь в лучшем случае одно дерево, а то и несколько, и число вершин > числа ребер. Но число вершин это число гарантированных выстрелов вниз, а число ребер это число происшедших выстрелов вверх. Что и требовалось доказать.