Так математики видят зарождение вселенной ⬆️

Ну не все, а только те, кто имел дело с клеточными автоматами.

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

🔸Первым клеточными автоматами серьёзно озадачился Джон фон Нейман — мы писали о нём здесь и здесь. Его занимал вопрос самовоспроизводящихся машин. В 1940-х он предложил квадратную схему решётки из ячеек, где каждая имела целых 29 возможных состояний, и могла себя копировать.

🔸Спустя двадцать лет его коллега Станислав Улам предложил более простые варианты. Но настоящую славу клеточным автоматам принёс Джон Конвей — он придумал игру «Жизнь» (1970). Это, пожалуй, самая известная модель. Она отличается простотой и элегантностью правил, а ещё плодовитостью вытекающих из них результатов.

Зачем нужны клеточные автоматы 👀

Эти системы применяются в разработке игр, криптографии, биологии, моделировании физических процессов и даже поведения людей. И, конечно, они красивы с точки зрения математики.

Накидайте реакций, и мы расскажем, причём тут зарождение Вселенной. Спойлер: будем говорить об игре «Жизнь».

#как_устроено

Головоломка о волшебниках 🧩

Джон Конвей, о котором мы начали рассказывать на прошлой неделе, известен не только как создатель игры «Жизнь». Его вклад в математику намного разнообразнее. Например, в 1960-х годах он придумал вот такую задачу:

▶️В ночном автобусе ехали два волшебника и вели диалог:

Волшебник А: «У меня положительное целое число детей. Их возрасты — положительные целые числа. Сумма возрастов равна номеру автобуса, на котором мы едем, а произведение возрастов — это мой собственный возраст».

Волшебник B: «Как интересно! Может быть, если бы вы сказали мне ваш возраст и количество детей, я смог бы выяснить их индивидуальные возрасты?»

Волшебник А: «Нет».

Волшебник B: «Ага! Наконец-то я знаю, сколько вам лет!»

▶️Вопрос: что можно вывести из этой беседы?

Ответы под спойлером ждём в комментах. А пока думаете — перечитывать условие или нет — голосуйте, насколько вам нравятся такие головоломки:

❤️ — Конвей супер
👀 — хочу решать задачи про белок

#задача

Математики в этой задаче больше, чем может показаться на первый взгляд. И решение не из самых коротких. Разобьём его на шаги:

1️⃣ Обозначим сумму возрастов через S (номер автобуса), а возраст волшебника А через P (произведение возрастов):

Волшебник B изначально знает только, что сумма равна S. Когда он спрашивает про возраст волшебника А (P) и число его детей (k), он подразумевает, что пара (P, k) однозначно определяет разбиение суммы S на k положительных целых частей.

Волшебник А отвечает: «Нет». Значит, для реальной пары (P, k), соответствующей словам А, существует более одного набора k положительных целых чисел с суммой S и произведением P. Другими словами, даже зная P и k, возраста детей всё ещё неоднозначны.

2️⃣ Факт, что волшебник B, услышав «Нет», сразу же узнаёт возраст волшебника А, означает:

среди всех возможных разбиений суммы S на положительные целые с разными произведениями ровно одно произведение P даёт такую «внутреннюю» неоднозначность по числу детей.

То есть ровно один P для данного S имеет свойство: «существует хотя бы два разных разбиения с той же парой (P, k)». Тогда волшебник B, зная только S и услышав «Нет», может однозначно выбрать это единственное P.

3️⃣ Найдём номер автобуса (S) и возраст волшебника А (P):

Перебирая возможные суммы, видно, что единственная сумма S, для которой существует ровно одно произведение P, дающее описанную неоднозначность, — это 12. Для S = 12 есть ровно одно проблемное произведение P = 48 с k = 4, потому что:

Два разных набора из 4 положительных целых чисел, сумма которых 12, дают одинаковое произведение 48:

🔸1, 3, 4, 4 (сумма 1 + 3 + 4 + 4 = 12, произведение 1 ⋅ 3 ⋅ 4 ⋅ 4 = 48)
🔸2, 2, 2, 6 (сумма 2 + 2 + 2 + 6 = 12, произведение 2 ⋅ 2 ⋅ 2 ⋅ 6 = 48).

Таким образом, получаем ответ:

▶️Номер автобуса S = 12
▶️Возраст волшебника А = 48
▶️Число детей k = 4
▶️Но сами возраста детей остаются неоднозначными: это либо 1, 3, 4, 4, либо 2, 2, 2, 6

Ну как, что-нибудь понятно? Если нет, советуем прочитать подробное обсуждение задачи и другие её обобщения здесь.

#задача

Настоящие расследования в авторском канале «Детектив данных» 🔍

Уже три года Виталий рассказывает, как вкатывался в аналитику данных. Он прошёл путь от тысячи откликов неуверенного джуна до мидл-позиции и публикаций на «Хабре».

Теперь автор делится опытом и проводит настоящие аналитические расследования. Советуем начать с этих:

▶️ Рассказ про неправильную формулу прироста в интернете в трёх актах.
▶️ Анализ семейного бюджета, или Как с нуля
создать базу данных и дашборд в Excel
▶️ Визуализация «Какие зарплаты обещают нам курсы по аналитике данных»

Особенно советуем пост про формулу прироста — это гимн внимательности к математическим деталям. Подписывайтесь и читайте!

#рекомендуем

Вселенная: Смотри, я бесконечно огромна
Мандельброт: 🗿

Французский математик Бенуа Мандельброт считается одним из отцов фрактальной геометрии. Его множество стало, пожалуй, самым узнаваемым фракталом в математике. Оно рождается из бесконечного повторения простой формулы: Zₙ₊₁ = Zₙ² + c.

И, конечно, мы не можем оставить вас без визуализации этого множества. Её сделал индийский математик Чираг Дудхат. На его канале ещё много красивых экспериментов с математическими идеями — можно позалипать.

🔗 Понравилось? Тогда переходите к нашему сериалу про узоры Эшера. Там ещё больше бесконечностей и визуальных парадоксов — особенно советуем новым подписчикам!

#рекомендуем

Знаете что-нибудь об Аде Лавлейс ❓

В XIX веке, когда компьютеров ещё не существовало, леди Лавлейс придумала первый алгоритм для вычислительной машины. По сути, это была первая программа в истории — и её автору тогда было всего 27 лет.

Делимся тремя фактами из жизни известнейшей женщины-математика. Оценят все, кто дружит с числами и кодом:

1️⃣ Ада была дочерью поэта Джорджа Байрона.

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

2️⃣ Она написала первый в истории алгоритм.

Изучая проект разностной машины Чарльза Бэббиджа, Ада предложила, как та могла бы вычислять числа Бернулли. Она расписала шаги вычислений и результат — по сути, создала первую программу. Сегодня это заняло бы несколько строк кода, а тогда представляло собой сложную таблицу с десятками операций.

3️⃣ Её имя стало частью мировых технологий.

В честь леди Лавлейс назвали язык программирования ADA, созданный для военных систем, и архитектуру видеокарт NVIDIA. А ещё именно Ада ввела в обиход понятия «цикл» и «рабочая ячейка».

Каждый второй вторник октября весь мир отмечает её день — праздник достижений женщин в науке и технологиях.

Расскажите в комментариях, кто вдохновляет вас искать новые знания — и не забудьте поставить ❤️ Аде за её достижения!

#история

Сегодня у нас особенная задача — зашифрованная ✏️

Всего-то и нужно — понять, что написано здесь:

Я ючоьг гдь фйч гчйьгчйябч?

Тем, кто всё знал или сходу догадался, со всей ответственностью сообщаем:

Гэ птрфкюд!

Пишите расшифровки обеих фраз в комментах под спойлером.

Решить рандомную задачу из канала — тык

#задача

Легко ли быть… криптографом❓

Шифр, который мы использовали в первом сообщении, называется шифр Цезаря. Это один из старейших и простейших методов шифрования информации. Вот в чём его суть:

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

В нашем случае ключ равен -9, то есть Я переходит в И, и так далее.

Получим ответ:
Я ючоьг гдь фйч гчйьгчйябч? → И зачем мне эта математика?

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

Ещё один похожий шифр называется Атбаш. Он пришёл из древнего иврита: в нём первая буква алфавита заменялась на последнюю, вторая — на предпоследнюю, и так далее. То есть в русском алфавите А превращается в Я, Б — в Ю, В — в Э и так далее

Но ни шифр Цезаря, ни Атбаш не помогут вам расшифровать наше сообщение.

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

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

Шифр для нашего второго сообщения можно назвать позиционно-полиалфавитным — сдвиг зависит от позиции буквы в слове. А именно: первая сдвигается на 1, вторая — на 2, третья — на 3 и так далее.

Получаем:
Гэ птрфкюд! → Вы молодцы!

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

Накидайте огоньков — и мы расскажем!

#задача

Цезарь мёртв, да здравствует Цезарь

Вчера мы разобрали шифр Цезаря и затронули Атбаш. Главный недостаток таких шифров — сохранение частотной структуры языка.

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

Le chiffre indéchiffrable de Vigenère 🧩

Так по-французски называли «неподдающийся расшифровке» шифр Виженера. Его изобрели в XVI веке, и до XIX века к нему не могли подобрать метод решения. Всё дело в ключевом слове: его используют циклично, смещая для каждой позиции.

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

Возьмём английский алфавит A–Z (26 букв) и, например, слово LEMON в качестве ключа. Шифровать будем открытый текст ATTACKATDAWN.

Считаем, что A=0, B=1, …, Z=25. Для каждой буквы открытого текста берём соответствующую букву ключа (циклично) и сдвигаем:

A (0) + L (11) = L (11)
T (19) + E (4) = X (23)
T (19) + M (12) = F (5)
A (0) + O (14) = O (14)
C (2) + N (13) = P (15)
и т.д. по циклу.

Текст: A T T A C K A T D A W N
Ключ: L E M O N L E M O N L E
Шифр: L X F O P V E F R N H R

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

Как же взломать шифр Виженера❓

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

А вот короткий повторяющийся ключ, как LEMON в примере, уязвим. И есть разные способы его восстановить. Приведём несколько методов:

🔸Сначала необходимо определить длину исходного ключа. Это можно сделать, например, по методу Касиски — искать повторяющиеся фрагменты в шифротексте. Расстояния между ними часто делятся на длину ключа — это наша первая подсказка.

🔸Ещё есть статистический метод Фридмана, оценивающий вероятность совпадений букв при сдвиге — индекс совпадения. Если мы правильно угадали длину ключа k, то, разбив шифротекст на k потоков (буквы через каждые k позиций), внутри каждого получим обычный шифр Цезаря.

🔄Индекс совпадений измеряет, насколько часто в тексте встречаются одинаковые буквы. Для английского текста он равен примерно 0.065, для случайной абракадабры — около 0.038. Нужно найти то k, при котором индексы приближаются к 0.065 — это и будет искомая длина ключа🔄

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

🔸Если ключ короткий, можно использовать брутфорс — перебрать все возможные ключи: при алфавите из 26 букв и длине ключа k достаточно рассмотреть 26^k вариантов:

▶️для k = 3 это 17 576 — легко
▶️для k = 6 — около 309 млн — на грани, но достижимо
▶️для k = 10 — имеем 1,4·10^14 — почти невозможно для перебора на персональном компьютере

Однако современные методы (комбинация статистики, эвристик и вычислительной мощности) позволяют сократить пространство поиска.

Как вам тема? Интересно читать про настоящую криптографию или вы ждали разоблачение Дэна Брауна?

😐 — «Код да Винчи» не трогать
😍 — хочу узнать про математику «Энигмы»

#как_устроено