Зачем мне эта математика

Часто математические задачи можно решить разными способами. Например, недавно у нас была задача про улицы Питера. Мы её решали с помощью треугольника Паскаля, а в комментариях многие писали другой способ решения — комбинаторный. Разберём его. В той задаче Макс хочет пройти 6 кварталов вниз и 2 вправо. Все направления «вниз» идентичны между собой, как идентичны и варианты «вправо». Всего Максу нужно пройти 6 + 2 = 8 кварталов. Закодируем направление «вниз» буквой Н, а варианты «вправо» — буквой П. С точки зрения комбинаторики каждый маршрут — это как бы слово из восьми букв, причём шесть из них — Н и две — П. И нам нужно найти количество таких слов. Это же…. число сочетаний! Значит, количество способов добраться из точки А в точку В можно записать как C⁶₈ или как C²₈. В любом случае имеем 8! / (2!*6!) = (8*7) / 2 = 28. Именно этот ответ мы и получили раньше. Обобщим! Любой элемент треугольника Паскаля можно вычислить с помощью формулы для количества сочетаний из n по k. Индекс n пишут внизу рядом с заглавной буквой С, а индекс k — наверху. Формула для подсчёта количества сочетаний равна: n! / ((n-k)!*k!), где - n — это номер ряда треугольника Паскаля; - k — это номер коэффициента в n-м ряду. Нумерация обоих индексов n и k начинается с нуля! Вот так легко можно вычислить любой элемент треугольника Паскаля, не вычисляя предыдущие. Например, второй элемент в четвёртом ряду равен C²₄ = 4! / ((4-2)!*2!) = 4*3 / 2 = 6. А значит, можно вычислить коэффициент при любом слагаемом в разложении (a+b)ⁿ, не выписывая весь треугольник Паскаля до этой строчки. Удобно!

По окончании курса вы получите диплом о профпереподготовке. Наши специалисты помогут с трудоустройством. Более 2/3 выпускников находят работу по специальности. Сколько стоит? Курс стоит 96 000 рублей. Есть варианты, которые комфортнее совмещать с работой или более интенсивные. Материалы остаются у вас навсегда. А теперь — обещанный сюрприз! Мы подготовили для вас промокод со скидкой 10% на оплату любого курса направления анализа данных. И этот промокод не простой, а математический! Чтобы получить скидку, нужно: 1. Решить задачу ниже и получить ответ в виде числа. 2. Это число нужно записать вместо X в коде “PrakticheskiX” (но без кавычек). Например, если получится 99, то код будет Prakticheski99. Это не сам промокод, а только пример, как его записать. 😉 3. Ввести промокод на странице оплаты выбранного курса до 13 августа этого года. А вот и сама задача для промокода. Аркадий Стеков откликается на вакансии на позицию «Аналитик данных». Несколько компаний уже назначили собеседования! Известно, что каждая компания даёт ответ сразу же после собеседования. Аркадий прекращает ходить по собеседованиям, как только получает первый оффер. Аркадий всегда волнуется на собеседованиях, поэтому знает, что вероятность успешно пройти собеседование в первой же компании — всего 0.35. Дальше он чувствует себя увереннее, поэтому на всех следующих собеседованиях вероятность получить работу будет уже 0.65. Результат каждого из собеседований не зависит от других. На какое количество собеседований должен сходить Аркадий, чтобы получить работу с вероятностью не менее 99%? Важно! На этот раз ответ к задаче не нужно писать в комментариях. В комментариях можете задать вопросы по курсам, или оставить отзыв, если вы уже прошли какой-то из них. 😇 А мы оставим там ссылки на курсы наравления анализа данных.

Привет! На связи команда математики. Мы уже рассказывали про наш математический курс. А ещё в Практикуме можно получить новую профессию с нуля: например, аналитика данных или специалиста по Data Science. Сегодня мы расскажем о курсе «Аналитик данных», в конце поста — сюрприз! О чём этот курс? Курс поможет освоить профессию аналитика данных — с нуля за 6 месяцев. Вы научитесь: - выгружать, преобразовывать и очищать данные; - создавать дашборды; - рассчитывать ключевые метрики компаний; - проводить A/B-тесты; - помогать бизнесу принимать решения на основе данных. Вы освоите основные рабочие инструменты аналитика: SQL, Python, Tableau. Программа курса постоянно обновляется, последний раз — в апреле 2023. Кому подойдёт курс? Курс подойдёт тем, кто хочет получить новую профессию с нуля. Как проходит обучение? Вы изучаете теорию на платформе, а затем закрепляете навыки на практических задачах. 75% курса — это практика. Вас ждут типичные для аналитика кейсы из разных сфер бизнеса. Вы решите их и сможете добавить в своё портфолио более 13 проектов. Учёба занимает 6 месяцев. Что с обратной связью? Вас поддержат практикующие специалисты: - Преподаватели ответят на вопросы в чате в любой день недели. - Наставники проведут вебинары, разберут сложные кейсы и вопросы карьеры. - Ревьюеры проверят код и проекты. - Кураторы поддержат морально и помогут организовать учебный процесс.

Великая теорема Ферма Наверняка вы слышали о ней — возможно, больше о долгих попытках её доказать, а не о самой формулировке. Формулировка же до того проста, что её поймёт даже школьник: У уравнения aⁿ+bⁿ=cⁿ не существует целочисленных ненулевых решений при n>2. Пьер Ферма сформулировал теорему ещё в 17 веке, а про её доказательство написал, что оно «поистине чудесно», но «поля книги слишком узки для него». Доподлинно неизвестно, действительно ли Ферма нашёл доказательство или просто пошутил.😄 Или у него правда было короткое доказательство — просто неверное или неполное. Итак, более 300 лет математики пытались доказать эту теорему. Сначала этим занимались только учёные, а потом она стала настолько популярна, что к попыткам доказать её присоединились и просто любители математики. Они были настолько активны, что в 1972 году журнал «Квант» написал: «Редакция „Кванта“ со своей стороны считает необходимым известить читателей, что письма с проектами доказательств теоремы Ферма рассматриваться (и возвращаться) не будут». К решению этой проблемы привлекали и компьютеры. В 20 веке был период, когда самые мощные в мире компьютеры в фоновом режиме постоянно доказывали эту теорему для частных случаев: когда n равняется конкретному числу. Но общего доказательства всё ещё не было. Наконец в 1994 году английский математик Эндрю Уайлс с коллегами доказали теорему — и весь математический мир вздохнул с облегчением. Доказательство занимает более 100 страниц и пост в телеграме слишком узок для него 😉 Познакомиться с кратким пересказом можно тут, а при очень большом желании можно почитать книгу, в которой объясняется полное доказательство. Всё на английском, и математика там, конечно, ого-го! В этом и нюанс — доказательство использует современные инструменты (например, теорию Галуа и алгебраическую геометрию), которые никак не могли быть известны Ферма. И вот, несмотря на то, что факт уже доказан, до сих пор есть сообщество людей (их называют Ферматистами), которые пытаются найти то самое «поистине чудесное» доказательство, о котором говорил Ферма. Пока безуспешно. Теорема Ферма ещё не нашла конкретного применения, однако факты, которые доказывались, по сути, для неё — используются и в других областях математики. Но нам кажется, что её доказывали и продолжают доказывать потому, что формулировка так проста, а короткое решение так долго не находилось — это просто обидно! А напоследок давайте уйдём чуть в сторону от теоремы Ферма и рассмотрим то же уравнение aⁿ+bⁿ=cⁿ, но в том случае, который она не охватывает. А именно: натуральные n⩽2. Сколько целочисленных ненулевых решений у этого уравнения в таком случае?

Привет! Сегодня разберём решение двух задач из поста о малой теореме Ферма. Напомним формулировку теоремы: Если p — простое число и a — целое число, которое не делится на p, то aᵖ⁻¹ ≡ 1 (mod p). 1) Найти остаток от деления числа 3¹⁰ на 11. Здесь p=11. По нашей теореме любое число, которое не делится на 11 нацело, при возведении в 10 степень даст остаток 1 при делении на 11. И раз 3 взаимно просто с 11 — теорема применима, поэтому сразу получаем ответ. Ответ: 1 2) Найти остаток от деления числа 17⁸ на 7. В данном случае p=7, поэтому давайте представим число 17⁸ как 289*17⁶, чтобы показатель был равен p-1, как в теореме. И раз 17 не делится на 7 нацело, можно применить теорему для множителя 17⁶. Получим 17⁶ ≡ 1 (mod 7). Также надо найти, с чем сравнимо 289 по модулю 7. Число 287 делится на 7 нацело, поэтому: 289 ≡ 2 (mod 7). Значит, 289*17⁶ ≡ 2 (mod 7) * 1 (mod 7) = 2 (mod 7). Ответ: 2

Давненько у нас не было фактов про простые числа! Исправим это недоразумение и поговорим о малой теореме Ферма. Её формулировка звучит так: Если p — простое число и a — целое число, которое не делится на p, то aᵖ⁻¹ ≡ 1 (mod p). Если такая запись вам незнакома, советуем прочитать наш пост про арифметику остатков. Чуть более простая формулировка теоремы: если p — простое число и a — целое число, которое не делится на p, то aᵖ⁻¹-1 нацело делится на p. У данного факта существует довольно много доказательств: попроще и сильно посложнее. При желании можно посмотреть их тут и пообсуждать в комментариях к посту. Чем может быть полезна эта теорема? Она помогает находить простые делители чисел или проверять, является ли число простым. Конечно, при маленьких значениях это можно выяснить и вручную, но для достаточно больших чисел проще воспользоваться теоремой. Также малая теорема Ферма используется для доказательства корректности алгоритма шифрования RSA. Ну и, конечно же, с её помощью можно находить остатки от деления! Предлагаем вам почувствовать себя исследователями теории чисел и решить пару задач, используя малую теорему Ферма. 1) Найдите остаток от деления числа 3¹⁰ на 11. 2) Найдите остаток от деления числа 17⁸ на 7. Ваши решения и ответы ждём под скрытым текстом.

Сегодня рассмотрим экзистенциально-гастрономическую проблему. Допустим, у вас есть бутерброд из трёх слоёв, например: хлеб, колбаса и сыр. Вы хотите разрезать его пополам и разделить с другом. Казалось бы, в чём сложность? По справедливости в половинках должно быть поровну всех ингредиентов — и хлеба, и колбасы, и сыра. При этом никто не гарантирует, что колбаса и сыр лежали ровно посередине куска хлеба, да и каждый «слой» может иметь разную форму и размер. А разрез можно сделать всего один! Возможно ли честное разделение пополам при таких условиях? Теорема о бутерброде утверждает, что да! В трёхмерном пространстве всегда можно совершить один такой разрез, который разделит бутерброд из трёх слоёв как надо. Даже если части этого бутерброда расположить на разных концах планеты или галактики. :) Правда и ножик тогда потребуется интересный… Подробнее о том, как именно получить идеальные половинки бутерброда — в этом видео. В нём бутерброд чуть более скучный: два куска хлеба и ветчина, но принцип тот же самый. Кстати, если хотите смотреть иностранные видео на русском, то можно делать это через Яндекс Браузер, в нём есть отличная функция перевода. А подробнее о самой теореме можно почитать тут. Приятного вам аппетита! 🥪

Привет! В пятницу мы выкладывали задачку про котиков-курьеров, сегодня публикуем решение. По условию известно, что в контрольной группе в приложение зашли 50 000 пользователей, а оформили заказ лишь 2370 пользователей. Рассчитаем конверсию: (2370 / 50 000) * 100% ≈ 4.7%. В тестовой группе в приложение зашли 50 000 пользователей, а оформили заказ 2550. Снова рассчитаем конверсию: (2550 / 50 000) * 100% = 5.1%. Мы видим, что разница есть. Но является ли она статистически надёжной? На такие вопросы и отвечает статистика. Она позволяет рассчитать специальный критерий, который будет учитывать погрешность в данных. Если бы разницы между конверсиями не было, то значение критерия было бы очень близко к нулю. А p-value показывает вероятность получить такое (как мы получили) или более экстремальное значение критерия при условии, что наше предложение о равенстве конверсий верно. Если в этой задаче применить корректный статистический тест и воспользоваться калькулятором, то можно получить значение p-value ≈ 0.009, что ниже выбранного уровня значимости. Значит, это статистически значимый результат. То есть разница конверсий с учетом погрешности данных — существенна. Следовательно, можно утверждать, что коты-курьеры действительно влияют на результат! Чтобы узнать, как работают статистические тесты, как считаются результаты и что означает этот ваш p-value — проходите новый бесплатный курс «Основы статистики и AB тестирования».   Скрин с решением кошки Кнопы — в комментариях. ☺️

Привет! Сегодня мы принесли вам задачку про котиков. Для её решения потребуются знания некоторых специальных терминов. Повод такой: у нас вышел бесплатный курс «Основы статистики и A/B-тестирования», задача как раз оттуда. Предлагаем вам попробовать свои силы! ___ Кошка Кнопа управляет онлайн-магазином товаров для животных «Кнопа и партнёры». Сейчас магазин тестирует новый способ доставки: товары привозят не люди, а коты (когда коты нанимают котов, это не считается эксплуатацией). Ожидается, что новый способ доставки повысит конверсию* из захода в приложение в заказ. Магазин провёл А/В-тест, его результаты вы найдёте в комментариях к этому посту. Теперь надо определить, действительно ли способ доставки влияет на конверсию? Чтобы помочь Кнопе ответить на этот вопрос, рассчитайте значение конверсии из захода в приложение в оформление заказа для контрольной и тестовой групп, а затем определите статистическую значимость разницы конверсий. Для этого воспользуйтесь одним из онлайн-калькуляторов — например, этим. Кнопа уточняет, что она использует уровень значимости, равный 0.05. Ваши ответы она будет ждать в комментариях под скрытым текстом, а своё решение опубликует в понедельник. *Конверсия (англ. Conversion Rate, CR) — процент пользователей, совершивших целевое действие. ___ Кстати, сегодняшнее изображение котика-курьера мы сгенирировали с помощью нейросети. Делитесь своими вариантами (можно настоящими, можно цифровыми), устроим выставку!

Две верхние строчки соответствуют коэффициентам для (a+b)⁰ и (a+b)¹. Нумеруются строки в треугольнике с нулевой, чтобы номер совпадал со степенью, в которую возводили двучлен. Как же получить следующую строку? По краям пишем единички, а любое значение в середине равно сумме двух чисел над ним. Подвигать ползунок и посмотреть на этот процесс можно тут. У треугольника Паскаля целый вагон великолепных свойств, обязательно ещё вернёмся к нему. Итак, зная коэффициенты в седьмой строке, можно получить восьмую: 1 8 28 56 70 56 28 8 1. И именно в восьмой строке скрыт ответ на исходную задачу: попасть в нужную точку B можно с перекрёстков со значениями 7 и 21, складываем их и получаем 28. Конечно, получить 28 можно было и не выписывая весь треугольник. И даже не зная о его существовании. :) В каждой ситуации выбирайте свой способ решения. Наиболе оптимальным здесь является комбинаторный — о нём расскажем в другой раз! Однако если задача стоит в перемножении многочленов — треугольник Паскаля просто незаменим! Для тренировки предланаем вам с его помощью вычислить разложение (a+b)⁹ и (a+b)¹⁰. Ответы, как всегда, оставляйте под скрытым текстом.

Привет! Вчера у нас была задача про прогулки по улицам Питера. На самом деле она была лишь поводом рассказать вам о треугольнике Паскаля и его связи с возведением двучлена в степень. Но давайте обо всём по порядку. Зафиксируем на каждом перекрёстке количество возможных способов до него добраться. Тогда количество маршрутов до каждого следующего равно сумме способов добраться до двух предыдущих, ведущих к нему. В этой интерактивной объяснялке подробнее показываем, как получить число на каждом из перекрёстков. При чём же тут двучлены и возведение их в степень? Дело в том, что получившиеся числа на перекрёстках — это ни что иное, как биноминальные коэффициенты. Бином — это двучлен, например, (a+b). Если мы возводим его в степень, то есть умножаем на самого себя несколько раз, при раскрытии скобок перед каждым буквенным слагаемым будут возникать числа — коэффициенты. При раскрытии скобок степень переменной a постепенно убывает с n до 0, степень b — возрастает с 0 до n. А сумма показателей в каждом отдельном слагаемом равна n. Например, (a+b)² = 1a²+2ab+1b², (a+b)³ = 1a³+3a²b+3ab²+1b³, (a+b)⁴ = 1a⁴+4a³b+6a²b²+4ab³+1b⁴. Если выписать только коэффициенты из правой части, то получим такой треугольник ⬇️

Лето, белые ночи — самое время для задачки о прогулке по Питеру! Макс приехал в Санкт-Петербург и гуляет по Васильевскому острову. Фишка в том, что большая часть острова — это сетка из трёх параллельных проспектов и перпендикулярных им линий. Макс хочет дойти от причалов (точка А) до дома друга (точка В), не проходя по одной и той же улице дважды и не разворачиваясь назад. Ему нужно пройти шесть кварталов вперёд и два вправо. Можно сначала повернуть, потом идти вперёд. Можно сначала пройти вперёд, а потом уже поворачивать. А можно идти вперёд, потом повернуть, потом снова идти вперёд… в общем, вариантов много! Но сколько именно? Вычислите общее количество способов добраться из точки А в точку B. Ждём ваши ответы под скрытым текстом. А завтра мы опубликуем решение и расскажем про связь этой задачи с формулами сокращённого умножения. :)

Привет! Выкладываем решение задачи про бактерии из нашего пятничного поста. Пусть первая стадия эксперимента длится p минут, вторая — d минут. Составим уравнения: 4*10ᵖ = 2000 и 4*10ᵈ = 8000. Упростим их, поделив всё на 4, получим 10ᵖ = 500 и 10ᵈ = 2000. Числа p и q — не целые и даже не рациональные. По определению логарифма имеем: p = log₁₀500 и d = log₁₀2000. У логарифмов по основанию 10 есть сокращённое обозначение lg. Значит, p = lg500 и d = lg2000. По свойству суммы логарифмов lg500 + lg2000 = lg(500*2000) = lg1000000 = lg10⁶ = 6. Значит, весь эксперимент занимает 6 минут.

Давайте же применим эти знания к реальной задаче! В лаборатории выводят новые виды бактерий. Известно, что они размножаются по закону типа y = a*bⁿ, где y — итоговое количество бактерий, a — их стартовое количество, b — коэффициент размножения (во сколько раз их количество возрастает за одну минуту), n — количество прошедших минут. Эксперимент состоит из двух стадий: сначала наблюдают за одной группой бактерий, затем за другой. В обеих группах на момент начала наблюдений было по 4 бактерии, скорость размножения у них одинаковая. Сначала достают из холодильника чашку с первой группой, через минуту бактерий в ней становится больше в 10 раз. Как только их становится 2000, исследователи достают чашку со второй группой бактерий. Эксперимент заканчивается, когда во второй чашке насчитывается 8000 бактерий. Сколько минут длился весь эксперимент? Ваши ответы и решения как всегда ждём в комментариях под скрытым текстом.

Сегодня мы хотим предложить вам решить задачку про скорость размножения бактерий. Для описания многих биологических и экономических моделей нужны знания о показательных функциях. А где степени с показателями — там и логарифмы! И именно благодаря логарифмам и их свойствам мы сможем получить красивый ответ. Что такое этот ваш логарифм, мы уже обсуждали ранее, можно освежить определение в памяти в первом посте. А сегодня — о свойствах. Первое правило клуба любителей логарифмов: логарифм — это степень. Если держать в голове это утверждение и свойства степеней, то большая часть понимания уже будет с вами. Чем же так прекрасны логарифмы? 1) Сумма логарифмов равна логарифму произведения Эта формула есть на изображении выше. Чтобы её доказать — вспомним свойство степеней. При умножении степеней с одинаковым основанием их показатели складываются, то есть aᵏ × aᵗ = aᵏ⁺ᵗ. Так, например, 2³ × 2² = 2⁵ = 32. Логарифм — это степень, значит, показатели можно заменить логарифмами. Пусть aᵏ = m, aᵗ = n, тогда k = logₐm, t = logₐn. Получаем, что aᵏ⁺ᵗ = aᵏ × aᵗ = a^{logₐm} × a^{logₐn} = m × n = a^{logₐ(m*n)}. Значит, показатели равны: k + t = logₐ(m*n), то есть logₐm + logₐn = logₐ(m*n). С числами это свойство выглядит так: log₂8 + log₂4 = log₂(8*4) = log₂32 = 5. 2) Разность логарифмов равна логарифму частного Формула тоже есть на картинке выше. Это ещё одно свойство степени, переведённое на язык логарифмов. Как было у степеней: aᵏ / aᵐ = aᵏ⁻ᵐ. Снова обозначим aᵏ = m, aᵗ = n, тогда k = logₐm, t = logₐn. Как будет с логарифмами: aᵏ⁻ᵗ = aᵏ / aᵗ = a^{logₐm} / a^{logₐn} = m/n = a^{logₐ(m/n)}. Отсюда и показатели равны: k - t = logₐm - logₐn = logₐ(m/n). Числовая версия: log₂8 - log₂4 = log₂(8/4) = log₂2 = 1. Оба эти свойства работают и в обратную сторону, только там будут появляться модули: logₐ(m*n) = logₐ|m| + logₐ|n|. logₐ(m/n) = logₐ|m| - logₐ|n|.

Разберём вчерашнюю задачу про покупку авиабилета. Большинство из вас легко с ней справились! Стоимость билета в рублях с учётом кэшбека получается 17200*0.94 = 16168 рублей. Второй вариант с евро в теории дешевле, ведь 165*91.8 = 15147 рублей. Но по факту всё было несколько иначе. :) Во-первых, из-за комиссии сайта, стоимость в евро составит 165*1.01=166.65. Для этого потребуется 166.65*26.4 лир, а чтобы получить рубли, умножаем ещё на 3.7. Итого: 166.65*26.4*3.7 ≈ 16278.4. Это, конечно, меньше, чем 17200, но если учитывать кэшбек, то данный вариант становится менее выгодным, чем покупка на российском сайте. Как вам такие задачи из жизни?

Сегодня у нас злободневная задачка. :) Кристине нужно купить билет на самолёт из Стамбула в Берлин. На российском сайте подходящий билет стоит 17200 рублей, но при оплате её любимой банковской картой 6% вернутся в виде кэшбэка. Этот же билет можно купить на зарубежном сайте, там он стоит 165 евро. В момент, когда Кристина смотрит билеты, 1 евро = 91.8 рублей, то есть цена в евро — выгоднее! Однако для покупки на зарубежном сайте придётся использовать зарубежную карточку. У Кристины есть турецкая дебетовая, но на неё нужно перевести деньги. Сложность в том, что перевести их можно только на лировый счёт, а потом сконвертировать эти лиры в евро, и оплачивать билеты уже с еврового счёта. При пересылке рублей на лировый счёт курс будет такой: 1 лира = 3.7 рублей. А купить 1 евро турецкий банк предлагает за 26.4 лиры. А ещё зарубежный билетный сайт берёт 1% процент комиссии при оплате дебетовыми картами. Какой же вариант покупки билетов выгоднее для Кристины? Сколько она потратит в каждом из случаев (в рублях)? Пишите ответы в комментариях скрытм текстом, а позже мы опубликуем разбор.

Модульная арифметика Любому школьнику известно, что числа 37 и 23 не равны. Но, если в утверждение «числа 23 и 37 равны» добавить два слова и ещё одно число, то утверждение станет верным. Что же это за волшебные слова? Сегодня речь пойдёт про сравнение чисел по модулю другого числа. Если мы говорим, что число a сравнимо с числом b по модулю числа c, то это значит, что у чисел a и b одинаковые остатки при делении на c. Ещё говорят, что числа a и b равны по модулю c. Естественно, рассуждать об этом можно только в контексте целых чисел, иначе смысл определения теряется. Записывают сравнимость так: a ≡ b (mod c). Ещё можно понимать сравнение по модулю таким образом: если разность чисел a и b нацело делится на число c, то эти числа сравнимы (равны) по модулю с. То же самое символами: (a-b) ⋮ с <=> a ≡ b (mod c). То есть чтобы фраза «числа 23 и 37 равны» стала верной, надо добавить «по модулю 2». Также подойдут добавки «по модулю 7» и «по модулю 14». Разберём, например, такое утверждение: 36 ≡ 91 (mod 11). Здесь сказано, что числа 36 и 91 сравнимы по модулю 11, то есть имеют одинаковые остатки при делении на 11. Проверим: 36 = 11*3 + 3, а 91 = 11*8 + 3. Остатки совпали! Ещё пример: верно, что 29 ≡ 13 (mod 8), то есть числа 29 и 13 равны по модулю 8, ведь (29-13)⋮8. Сравнения по модулю имеют свойства, которые очень похожи на свойства обычных операций. Вот некоторые из них: 1) Если известно, два числа сравнимы по модулю третьего, то их натуральные степени также будут сравнимы. То есть если a ≡ b (mod c), то для любого натурального k верно, что aᵏ ≡ bᵏ (mod c). 2) Сравнения можно складывать/вычитать и перемножать друг с другом, но только в том случае, если они берутся по одному модулю — а вот сравнения по разным модулям нельзя соединять, это будет неверно. То есть если a ≡ b (mod c), n ≡ m (mod c), то a + n ≡ b + m (mod c), a*n ≡ b*m (mod c). Большинство стандартных операций со сравнениями очень просто и привычно проделывать из-за схожести с обычными вычислениями. Но одна из упомянутых операций обладает интересным свойством! Дело в том, что возвести число в степень по модулю несложно — надо просто возвести число в нужную степень и найти остаток от деления (или искать остаток от деления на каждом шаге, так делать обычно проще). Но вот выполнить обратную операцию, то есть найти «корень» нужной степени, гораздо труднее. Мало того, что этот процесс часто сводится к длинному перебору — иногда случается, что нужного нам корня вообще не существует. Из-за этих сложностей, принцип взятия остатка числа по какому-то модулю используется в криптографии: например, алгоритм (или, как его еще называют, протокол) Диффи-Хеллмана построен именно на том факте, что зашифровать одно число при помощи другого легко, а вот чтобы расшифровать не зная «код», понадобится много времени. А теперь задачи для вас! Решения, как всегда, ждём под скрытым текстом. 1) С чем сравнимо число 1000*1001*1002*1003 по модулю 999? 2) С чем сравнимо 4²⁰²³ по модулю 3?

Сегодня хотим рассказать вам про задачу о стабильных браках. Ещё её называют задачей о марьяже. Несмотря на то, что её классическая формулировка описывает поиск наилучшего супруга/супруги, в реальности эта задача нашла широчайшее применение. Недаром в 2012 за её решение авторов удостоили Нобелевской премии по экономике (хотя решение было опубликовано аж в 1962 году). С помощью алгоритма из этой задачи ординаторы и интерны находят потенциальные больницы для работы, студенты выбирают школы/колледжи, команды нанимают спортсменов, фирмы — стажёров или работников, интернет-пользователям назначается сервер. А ещё адаптация этого алгоритма помогает находить попутчиков или соседей по квартире. Итак, пусть есть N мужчин и N женщин, все гетеросексуальны (иначе нужен другой алгоритм). Пусть все у всех есть свой список предпочтений, то есть они могут упорядочить особей противоположного пола в порядке убывания привлекательности вот лично для себя. Требуется составить устойчивые пары, из которых никто не хочет сбежать с кем-то другим. То есть не должно быть ситуаций, когда вам нравится чужая жена больше, чем своя, и при этом чужая жена тоже предпочитает вас своему мужу. И было доказано, что алгоритм нахождения устойчивых пар существует! Правда счастья он никому не обещает. Но зато теорема утверждает, что решение есть для любого N, оно находится за конечное (хотя и довольно большое) количество шагов, и что оно подбирает наилучшую пару для «активной стороны» — то есть для того пола, который делает предложение. Наглядно данный алгоритм описан в этом видео, а в дополнении к нему поясняют доказательство и рассказывают про применения алгоритма в реальности. Советуем посмотреть оба видео. 😊 И пусть любой выбор в вашей жизни будет не только оптимальным, но и счастливым! 🥂

Перевод из десятичной системы счисления в двоичную и обратно Мы уже рассказывали о том, какими бывают системы счисления. Сегодня поговорим о двух важных и часто используемых: двоичной и десятичной. Название позиционных систем счисления напрямую связано с количеством цифр в них. В двоичной их всего две, 0 и 1. В десятичной — десять: от 0 до 9. Десятичной обычно пользуемся мы с вами, а вот двоичную предпочитают компьютеры и специалисты по математической логике. Цифрами двоичной системы легко описать состояния физических устройств: например, лампочка либо включена (1), либо выключена (0). Запись числа в десятичной системе счисления говорит о том, сколько в нём тех или иных степеней десятки. Например, 137 = 1*100 + 3*10 + 7*1 = 1*10² + 3*10¹ + 7*10⁰. Запись же числа в двоичной системе счисления показывает, какие степени двойки в нём есть, а каких нет. Отсчёт идёт с нулевой степени. Например, 11 в двоичной системе счисления — это 1*2¹ + 1*2⁰. Обсудим подробнее сам процесс перевода. Чтобы перевести число из десятичной системы в двоичную, нужно посмотреть на него как на сумму степеней двойки. Как это делается, наглядно показываем в этой динамической объяснялке. Самое главное — не забыть поставить нули на месте отсутствующих степеней. В числе 76, например, наибольшей степенью будет 64 = 2⁶, но дальше есть не все степени. 76 = 64 + 12 = 64 + 8 + 4 = 2⁶ + 2³ +2². На месте «присутствующих» шестой, третьей и второй степеней будут единицы, а на месте «отсутствующих» пятой, четвёртой, первой и нулевой степеней будут нули. 76 = 1*2⁶ + 0*2⁵ + 0*2⁴ + 1*2³ + 1*2² + 0*2¹ + 0*2⁰ = 1001100. Для перевода в обратном направлении снова понадобятся степени двойки. Рассмотрим для примера число 111101010 в двоичной системе. Оно девятизначное, значит, в нём могут содержаться степени от восьмой до нулевой. 111101010 = 1*2⁸ + 1*2⁷ + 1*2⁶ + 1*2⁵ + 0*2⁴ + 1*2³ + 0*2² + 1*2¹ + 0*2⁰ = = 256 + 128 + 64 + 32 + 8 + 2 = 490. Другой пример: в числе 10000100 восемь знаков, наибольшая степень — седьмая. Также единица стоит в разряде второй степени. 10000100 = 1*2⁷ + 1*2² = 128 + 4 = 132. Ваша очередь переводить! Переведите в двоичную систему числа 89 и 17, а в десятичную — числа 1001001 и 11101. Ответ как всегда оставляйте под скрытым тестом.