Комбинаторика
Бумага А5, маркер для каллиграфии
Бумага А5, маркер для каллиграфии
Неделю назад я создал ПО, которое массово генерирует btc кошельки и проверяет, использовались ли они до этого в блокчейне.
Вчера я его (ПО) опубликовал для того, чтобы каждый смог проверить, а сегодня публикую результаты своего исследования.
Btc кошелёк защищён последовательностью из 12 слов, которые находятся в особом списке bip39, состоящем из 2048 слов. Имеют смысл не только сами слова из списка, но и последовательность положения этих слов в фразе. Саму фразу называют мнемонической фразой.
Общее количество комбинаций слов составляет 2048 ^ 12, и равно приблизительно 5,44 × 10^39, то есть 5,44 дуодециллионов. Для понимая - 1 дуодецеллион - это приблизительно суммарная мощность излучения 250 000 звёзд как наше Солнце в одну секунду. Наше же число равно мощности 1 375 000 звезд. Много, правда? Но давайте продолжать исследование.
Давайте чуть чуть упростим наше понимание. Пусть btc кошелёк будет замком, а мнемоник фраза - ключом. Итак, вероятность того, что случайный ключ подойдёт к определённому замку равно единице, поделенной на эти самые дуодециллионы, или же как пишут математики - 1 / 5,44 × 10^39, или же примерно 1,84 × 10^-40, то есть 0 целых, далее идет 39 нулей и 184. То есть 184 дуодецелионных доли. А вот вероятность неудачи равна 1 - 1,84 x 10^-40, то есть 0,9999.....9999816, и по сути, стремится к единице, то есть 100%.
На текущий момент, согласно исследованием, имеется всего 19 миллионов созданных адресов. Это у нас 19 × 10^6 замков.
Далее воспользуемся формулой комбинирования вероятностей.
Исходя из неё, вероятность неудачи для любого из 19 млн замков равна (1 - 1,84 x 10^-40)^19 x 10^6, что приближается к значению в 1 000 000.
А вот уже шанс удачи равен 1 - (1 - 1,84 x 10^-40)^19 x 10^6, что чуть меньше чем -999 999.
То есть, теоретически, это невозможно.
Отправные точки - программа работала неделю на 10 пк приблизительно с одинаковой скоростью, и не смогла найти ни одного адреса.
Она делала 2 запроса к блокчейну в секунду. Умножаем на 30 потоков, на которых она стабильно работала, и получаем 60 запросов. То есть в сутки она проверяла 60 × 86 400 = 5 184 000 адресов. Умножаем на 10 ПК и получаем 51 840 000 адресов в сутки.
Если учесть, что всего в сети биткойн может быть создано приблизительно 2^160 адресов, то для того чтобы перебрать абсолютно все адреса мне понадобилось бы примерно 2,87 x 10^41 дней, или же 7.83×10^38 лет. Это в несколько раз превышает ожидаемую продолжительность жизни вселенной и на порядки больше, чем возраст вселенной.
Как говорилось в теоретической части, общее количество зарегистрированных адресов примерно равно 19 миллионам. Это составляет (19x10^6/2^160) x100, и равно примерно 1.3x10^-39., т.е. 0,000..00013 (всего 39 нулей после запятой) процента.
Для упрощения будем считать, что количество зарегистрированных адресов неизменно. Иначе совсем голову сломать можно будет.
Давайте теперь расчитаем вероятность случайно натолкнуться хотябы на один зарегистрированный адрес за адекватный период, возьмём например 10 лет непрерывной работы.
Количество дней в 10 годах: 10×365=3650 дней.
Общее количество адресов, которые можем проверить за 10 лет: (51×10^6)x3650
Вероятность того, что наш поиск не обнаружит ни одного зарегистрированного адреса равна ( 1 - (1.3×10^-39 / 2^160) ) ^ ((51x10^6)x3650).
Вычислив данное уравнение мы получим результат, стремящийся к единице, то есть к 100%.
Это означает, что практическая вероятность случайного подбора "правильного" ключа таким алгоритмом крайне мала. Что близко соответствует теоретическим изысканиям. Даже для относительно "слабой" 12-ти словной мнемонической фразы.
Вам нужно быть ну просто невероятно удачливым, чтоб подобрать таким образом правильную мнемоническую фразу для хоть одного реально существующего адреса.
Шанс того, что в вас в течении жизни попадёт молния пять раз подряд значительно больше.
Это первый завершенный учебник по математике за всю мою просветительскую деятельность! Шел я к этому без малого 8 лет! И я не собираюсь на этом останавливаться! Внутри поста интересная информация о том, как я пытаюсь создать лучший образовательный ресурс по математике!
Шел 2016 год. Мне надо было подтянуть знания по тригонометрии. Наткнулся на учебник от Гельфанда. Меня поразило то, насколько интересно и понятно он объясняет этот не самый легкий предмет. Я загорелся идеей создания собственных учебных материалов.
Так зародился проект TopMath — моя первая попытка создавать понятные и увлекательные учебники по математике. В рамках проекта я написал первую главу своего учебника по тригонометрии:
Моя самая первая попытка объяснять математику!
Из-за трудностей в вузе проект пришлось забросить. Но базовая идея — рассказывать про математику подробно, интересно и понятно, прочно засела в моей голове.
И началось... В течении 8 лет я регулярно к этой идее возвращался и с новыми знаниями пытался создать идеальный сайт-учебник. Всего таких попыток было 4. С каждым разом они становились все лучше-лучше, но по разным причинам я их забрасывал:
TopMath, MathIt, ByDef, OMath... тысячи их!
А вот пятая попытка выдалась самой удачной. Именно о ней дальше и пойдет речь.
В начале 2022 года я сел за пятую попытку создать учебник мечты. В этот раз я твердо решил "собрать все камни бесконечности" — создать проект, объединяющий все три необходимых для обучения компонента:
Подробную и понятную теорию с наглядными примерами из жизни
Краткие конспекты для запоминания самых важных моментов
Задачник с большим количеством задач для закрепления полученных знаний
На разработку я потратил чуть меньше года. В октябре 2023 года наконец официально увидел свет проект "Открытая математика" — квинтэссенция всех фишек, идей и опыта, накопленного предыдущими попытками.
Что есть уже сейчас?
Полноценное разделение на три части: теория, конспекты и задачник:
Удобная система ссылок между определениями, теоремами и другими блоками, которая позволяет не покидая текущую страницу посмотреть, куда конкретно ведет ссылка:
Полностью адаптивный дизайн, который хорошо смотрится на любых устройствах — от больших мониторов до небольших экранов смартфонов:
Светлая и темная темы, чтобы любители изучать математику в темноте не выжигали себе глаза:
Поддержка видеороликов, красивых и наглядных математических анимаций, схем и диаграмм:
Удобная система источников, которая позволяет понять, откуда я брал материал и по желанию изучить и первоисточник. Причем есть как общий список источников на титульной странице учебника, так и конкретный список "заимствований" в самих темах:
Задачи с автоматически генерирующимися условиями, чтобы можно было проверить себя на разных данных:
Часть фишек все еще не работает. Среди них: поиск, сортировка по типу тем, поддержка других языков и некоторые страницы. Ими я планирую заняться в ближайшее время.
Первый полноценный учебник на платформе. В процессе написания тем тестировались фишки платформы, выявлялись баги, а также появлялся новый функционал: те самые уже перечисленные ссылки на источники, видео, очень красивые математически анимации, аналогичные и генерирующиеся задачи и так далее!
Выбор пал именно на комбинаторику, потому что она имеет прикладной характер, в ней есть полезные и простые формулы, материала объяснять надо не очень много, а также у меня были хорошие источники, на основе которых можно было выстроить темы.
Всего в учебнике 10 тем, 12 определений и формул, 209 уникальных задач (без учета аналогов и генерирующихся задач)! Конечно, это не все, что можно было рассказать про комбинаторику.
В планах добавить темы про беспорядки, формулу включений-исключений и треугольник Паскаля. Но улучшать продукт можно бесконечно. В какой-то момент надо поставить точку, пускай и на время.
Последняя тема — "Формулы комбинаторики". В ней я собрал в красивые наглядные схемы все основные комбинаторные формулы. В практикуме привел задачи, которые задействуют сразу по нескольку формул.
Сейчас на очереди очередное техническое обновление — планирую написать единую систему, в которой можно одинаково быстро как добавлять новые статьи, так и вносить правки в уже опубликованные.
Кроме того, хочу еще раз обновить редактор, сделав его на основе блоков, что значительно расширит его функциональность.
И с новым функционалом уже приступать к написанию следующих учебников. Пока в планах теория множеств и теория пределов. Замахнусь на высшую математику! 😎
Буду держать вас в курсе!
Если есть желание, вы можете поддержать проект. Например есть возможность со своим фото и цитатой занять место на любой странице учебника!
Более подробная информация о спонсорстве и наградах есть на Boosty. Можете подписаться на меня здесь на Пикабу, а также на группы ВКонтакте или Telegram.
Присоединяйтесь!
Помогайте делать лучший математический контент! 🤝
Так же выражаю огромную благодарность Николаю Нагибину за то что открыл для меня мир математики. Без него этого сайта и учебника бы не было.
Добавил на сайт поддержку автоматически создающихся по тексту красивых диаграмм! Теперь не нужно долго возиться в графических редакторах, чтобы представить важную информацию в виде красивой схемы! Диаграммы есть практически в каждой теме учебника по комбинаторике, обязательно зацените!
Диаграммы в темах учебника
Помимо диаграмм, вернулся так сказать к истокам и обновил тему про "правило сложения", так как она была слабым звеном — ее я написал самой первой еще не имея знаний, которыми располагаю сейчас.
Сильно видоизменил теоретическую часть, добавил несколько новых задач и улучшил часть старых! Теперь она соответствует уровню остальных тем!
Так же обновил превью-картинки к обоим правилам: суммы и произведения:
Написал статью + конспект + задачник про одну из самых известных формул в алгебре — Бином Ньютона! Честно говоря, даже не мог подумать, что у одной формулы найдется настолько много замечательных применений внутри математики!
В прошлом посте я писал, что "Сочетания" будут последней крупной темой в моем учебнике по комбинаторике. Я ошибался) Сначала думал сделать небольшую тему, но в итоге получилась большая и полноценная тема! Часть материала даже пришлось вырезать и оформить как заготовку отдельной темы.
Специально для статьи создал красивую анимацию построения треугольника Паскаля. Потратил на нее полдня, но получилось хорошо:
Каждая новая анимация заставляет глубже разбираться в библиотеке Manim, про которую я тоже уже упоминал в посте про "Перестановки".
Учу составлять сочетания и считать их количество. Показываю вывод и использование одних из самых полезных формул в комбинаторике. С этими знаниями вы поймете, стоит ли участвовать в лотереях! Даже Инвокера из Доты 2 удалось задействовать :)
Это последняя крупная тема в моем учебнике по комбинаторике. Осталась только мелочевка: бином Ньютона, треугольник Паскаля и всякое такое.
Приятного изучения!
Если есть какие-то предложения, обязательно присылайте!
Если будет что-то толковое, добавлю в тему и вас упомяну)
Облазил весь интернет и кучу литературы, вытащил все самое интересное, пропустил через свою голову и оформил в виде темы "Перестановки" с теорией, конспектом и набором задач. Внутри красивые анимации и интересные детали про то, как я пытаюсь создать лучший образовательный ресурс по математике.
Видели когда-нибудь математические ролики YouTube с канала 3blue1brown или, может Wild Mathing? Оба этих канала в своих роликах используют очень красивые и наглядные математические анимации. Они создаются на языке Python с помощью библиотеки Manim. Эти анимации так хороши, что я тоже решил добавить их к себе на сайт.
Теперь и у меня в учебнике есть красивые и наглядные анимации! Вот, например, наглядная иллюстрация правила умножения для подсчета всех четырехзначных чисел с тройкой в разряде десяток:
Конкретно для одной задачи в практикуме перестановок я создал анимацию, помогающую понять, как именно возникают дубликаты при расстановке элементов по кругу:
Из-за небольшого опыта в работе с библиотекой на каждую такую анимацию пока уходит по полдня программирования пополам с изучением документации. Но это результат точно стоит потраченного времени. Исходный код всех анимаций храню в GitHub репозитории, чтобы можно было быстро вносить правки.
Другая фишка, которая появилась с выходом темы про перестановки — система источников. В поисках интересного материала и задач регулярно натыкаюсь на интересную литературу и сайты. Теперь они и места, откуда я взял материал отображаются как на главной странице учебника, так и в конце каждой темы. Не совсем по ГОСТу, но все равно удобно! Любой желающий может погрузиться в материал поглубже.
Из жизненных примеров использования перестановок удалось найти только использование анаграмм учеными с 17 по 19 века. Если вы знаете еще про какие-нибудь интересные и необычные примеры, буду рад про них узнать и добавить в тему.
Это шестая статья в учебнике по комбинаторике. Остались еще сочетания и одна-две дополнительные темы, такие как бином Ньютона, формула включений-исключений и прочее. Планирую к середине февраля завершить этот учебник и взяться за следующий.