Зная траты за неделю, можно приблизительно спрогнозировать траты по этим категориям на месяц. В месяце примерно 4.3 недели, значит, умножив траты на 4.3, можно получить какое-то представление о расходах в месяц. Это третья операция с векторами — умножение на скаляр, то есть умножение на число. Для получения результата нужно умножить скаляр на каждую координату по отдельности. Наш прогноз равен Month₁=4.3*Week₁=(4.3*2050, 4.3*3150, 4.3*3120)=(8815, 13545, 13416).
В геометрическом смысле умножение на скаляр будет либо растягивать, либо сжимать вектор, в зависимости от значения. При отрицательном скаляре вектор ещё и сменит направление.
При умножении вектора на скаляр получается новый вектор. А при умножении векторов получится, как ни странно, скаляр. Но об этом поговорим в следующий раз!
А в комментариях лежит бонусный пример, где векторы применяются к котику. :)))
В геометрическом смысле умножение на скаляр будет либо растягивать, либо сжимать вектор, в зависимости от значения. При отрицательном скаляре вектор ещё и сменит направление.
При умножении вектора на скаляр получается новый вектор. А при умножении векторов получится, как ни странно, скаляр. Но об этом поговорим в следующий раз!
А в комментариях лежит бонусный пример, где векторы применяются к котику. :)))
👍21🥰2🙈2❤1🤓1
Сегодня поговорим о том, как теория вероятностей может помочь в реальной жизни. Речь о так называемом парадоксе Монти Холла. Эта задача названа в честь ведущего шоу Let’s make a deal. Она похожа на парадокс двух конвертов, о котором мы писали ранее, только там всё было странно, а здесь всё нормально. 😄
Представьте: вы пришли на тв-игру, где нужно выбрать одну из трех дверей. За двумя находятся козы, а за третьей — ааавтомобиль. Вы не знаете, за какой дверью что, но ведущий знает точно. Вы выбираете одну дверь, но до её открытия ведущий открывает одну из дверей с козой. Затем он предлагает вам изменить свой выбор на другую закрытую дверь — если захотите, конечно. Как нужно действовать, чтобы с наибольшей вероятностью получить машину?
На первый взгляд, выбор двери не влияет на исход игры: как только одна дверь с козой открыта, вероятность победы становится равна 1/2, и тогда нет никакой стратегии! Как будто исходная дверь и оставшаяся дают равные шансы на победу. Но мы бы не писали пост, будь там всё так просто.
И действительно, когда ведущий открывает одну из дверей с козой, он даёт вам дополнительную информацию. То есть решение задачи не начинается с нуля, а продолжается — поэтому вероятности будут распределены иначе.
Объясним неформально.
Если вы сразу выбрали нужную дверь (вероятность этого всего 1/3), то Монти просто откроет вам любую из двух других. В этом случае менять дверь невыгодно, но вы об этом не знаете. :)
А вот если вы сначала не угадали (вероятность этого уже 2/3), то Монти откроет вам ту из двух, где машины нет. И тогда выгоднее поменять дверь. Но, опять же, вы об этом не знаете. Но видно, что второй вариант более вероятен в принципе, ведь не-угадать сразу — более вероятно, чем угадать.
Значит, именно стратегии для второго случая стоит придерживаться — и ваши шансы на выигрыш увеличатся.
Больше об этом парадоксе можно почитать на Википедии, там же есть отсылка к другой похожей задаче.
Но, на самом деле, это не парадокс в классическом понимании — просто ответ противоречит интуиции!
Представьте: вы пришли на тв-игру, где нужно выбрать одну из трех дверей. За двумя находятся козы, а за третьей — ааавтомобиль. Вы не знаете, за какой дверью что, но ведущий знает точно. Вы выбираете одну дверь, но до её открытия ведущий открывает одну из дверей с козой. Затем он предлагает вам изменить свой выбор на другую закрытую дверь — если захотите, конечно. Как нужно действовать, чтобы с наибольшей вероятностью получить машину?
На первый взгляд, выбор двери не влияет на исход игры: как только одна дверь с козой открыта, вероятность победы становится равна 1/2, и тогда нет никакой стратегии! Как будто исходная дверь и оставшаяся дают равные шансы на победу. Но мы бы не писали пост, будь там всё так просто.
И действительно, когда ведущий открывает одну из дверей с козой, он даёт вам дополнительную информацию. То есть решение задачи не начинается с нуля, а продолжается — поэтому вероятности будут распределены иначе.
Объясним неформально.
Если вы сразу выбрали нужную дверь (вероятность этого всего 1/3), то Монти просто откроет вам любую из двух других. В этом случае менять дверь невыгодно, но вы об этом не знаете. :)
А вот если вы сначала не угадали (вероятность этого уже 2/3), то Монти откроет вам ту из двух, где машины нет. И тогда выгоднее поменять дверь. Но, опять же, вы об этом не знаете. Но видно, что второй вариант более вероятен в принципе, ведь не-угадать сразу — более вероятно, чем угадать.
Значит, именно стратегии для второго случая стоит придерживаться — и ваши шансы на выигрыш увеличатся.
Больше об этом парадоксе можно почитать на Википедии, там же есть отсылка к другой похожей задаче.
Но, на самом деле, это не парадокс в классическом понимании — просто ответ противоречит интуиции!
❤14🤪6👍5🔥3👌2
Все про коронацию — и мы про коронацию. :)
Вот вы, возможно, не знали, но с точки зрения математики, и Кейт Миддлтон, и Меган Маркл — королевских кровей.
Да и вы кстати тоже! У всех нас есть общие предки — и в сегодняшнем видео объясняется алгоритм, с помощью которого можно найти самого близкого общего предка для любой группы ныне живущих людей. И там обязательно найдутся царские особы.
Желаем вам королевских выходных! 😎
Вот вы, возможно, не знали, но с точки зрения математики, и Кейт Миддлтон, и Меган Маркл — королевских кровей.
Да и вы кстати тоже! У всех нас есть общие предки — и в сегодняшнем видео объясняется алгоритм, с помощью которого можно найти самого близкого общего предка для любой группы ныне живущих людей. И там обязательно найдутся царские особы.
Желаем вам королевских выходных! 😎
👍17🤓7
Если мы посмотрим на историю человечества, то увидим, что в разные периоды люди по-разному записывали числа.
Все знают, что числа 12345 и 54321 разные: они состоят из одинакового набора цифр, но порядок записи этих цифр очень сильно влияет на то, каким будет число. Это кажется нам логичным и естественным, но так было далеко не всегда. А как ещё можно? Сегодня поговорим о системах счисления и выясним ответ на этот вопрос.
Разберемся с терминологией:
Система счисления — это набор правил, по которым цифры собираются в число. Системы счисления бывают позиционными и непозиционными (бывают и другие, но сегодня о них не будем).
В позиционных системах счисления порядок записи цифр (то есть их позиция) влияет на результат. Например, в привычной нам десятичной системе номер цифры означает степень числа 10, на которую эта цифра умножается. Нумеруем цифры мы справа налево, при этом начинаем с номера 0. То есть, число 12345 — это сокращенная запись суммы
5*10⁰ + 4*10¹ + 3*10² + 2*10³ + 1*10⁴ или
5*1 + 4*10 + 3*100 + 2*1000 + 1*10000.
В непозиционных системах порядок записи цифр не влияет на результат, значения цифр просто складываются. Самая простая непозиционная система счисления возникла очень давно, когда торговцам нужно было считать количество проданного. Во время продажи за каждый товар одного вида (корова, мешок яблок или что угодно еще) на специальной веревочке завязывался узелок — и количество узелков в итоге равнялось количеству единиц проданного товара. Такая система счисления, как можно догадаться, получила название «узелковая». Чтобы выразить ее математически, можно договориться, что числа могут состоять только из единиц (без десяток, сотен, дюжин и чего-то ещё). Тогда количество единиц и равняется самому числу.
В этой системе счисления 11 — это два, 111 — это три, 11 + 111 = 11111 (два плюс три равно пяти) и так далее. Можно заметить, что этот способ записи чисел не очень удобен: занимает много места и быстро отличить 1111111111 от 111111111111 «на глаз» уже непросто.
Поэтому для больших чисел стали придумывать отдельные символы и использовать принцип сложения. Например, в древнеегипетской системе символ | означал единичку, а символ ⋂ — десять. Число 13 можно было записать и как ⋂|||, и как |||⋂. Это сильно сокращает запись, ведь теперь для записи нам нужно всего 4 символа вместо 13 палочек. :) На этой идее построены все древние непозиционные системы счисления, отличаются лишь обозначения.
А вот римская система уже не является чисто непозиционной, ведь там XI и IX — это уже разные числа, зато это ещё экономнее, ведь запись IX короче, чем VIIII.
Но и тут возникают проблемы: мы можем придумать 5 новых цифр для больших чисел, можем придумать 10, но делать так бесконечно не выйдет, и, чтобы записать число «десять тысяч» нам опять придется писатьмногабукав много букв: MMMMMMMMMM.
Действительно, экономность и наглядность — не сильные стороны таких способов записи чисел. Но они были удобны для простейшего бытового счета, а их изучение заставляет ценить привычный нам способ обозначения чисел: позиционные системы счисления.
Все знают, что числа 12345 и 54321 разные: они состоят из одинакового набора цифр, но порядок записи этих цифр очень сильно влияет на то, каким будет число. Это кажется нам логичным и естественным, но так было далеко не всегда. А как ещё можно? Сегодня поговорим о системах счисления и выясним ответ на этот вопрос.
Разберемся с терминологией:
Система счисления — это набор правил, по которым цифры собираются в число. Системы счисления бывают позиционными и непозиционными (бывают и другие, но сегодня о них не будем).
В позиционных системах счисления порядок записи цифр (то есть их позиция) влияет на результат. Например, в привычной нам десятичной системе номер цифры означает степень числа 10, на которую эта цифра умножается. Нумеруем цифры мы справа налево, при этом начинаем с номера 0. То есть, число 12345 — это сокращенная запись суммы
5*10⁰ + 4*10¹ + 3*10² + 2*10³ + 1*10⁴ или
5*1 + 4*10 + 3*100 + 2*1000 + 1*10000.
В непозиционных системах порядок записи цифр не влияет на результат, значения цифр просто складываются. Самая простая непозиционная система счисления возникла очень давно, когда торговцам нужно было считать количество проданного. Во время продажи за каждый товар одного вида (корова, мешок яблок или что угодно еще) на специальной веревочке завязывался узелок — и количество узелков в итоге равнялось количеству единиц проданного товара. Такая система счисления, как можно догадаться, получила название «узелковая». Чтобы выразить ее математически, можно договориться, что числа могут состоять только из единиц (без десяток, сотен, дюжин и чего-то ещё). Тогда количество единиц и равняется самому числу.
В этой системе счисления 11 — это два, 111 — это три, 11 + 111 = 11111 (два плюс три равно пяти) и так далее. Можно заметить, что этот способ записи чисел не очень удобен: занимает много места и быстро отличить 1111111111 от 111111111111 «на глаз» уже непросто.
Поэтому для больших чисел стали придумывать отдельные символы и использовать принцип сложения. Например, в древнеегипетской системе символ | означал единичку, а символ ⋂ — десять. Число 13 можно было записать и как ⋂|||, и как |||⋂. Это сильно сокращает запись, ведь теперь для записи нам нужно всего 4 символа вместо 13 палочек. :) На этой идее построены все древние непозиционные системы счисления, отличаются лишь обозначения.
А вот римская система уже не является чисто непозиционной, ведь там XI и IX — это уже разные числа, зато это ещё экономнее, ведь запись IX короче, чем VIIII.
Но и тут возникают проблемы: мы можем придумать 5 новых цифр для больших чисел, можем придумать 10, но делать так бесконечно не выйдет, и, чтобы записать число «десять тысяч» нам опять придется писать
Действительно, экономность и наглядность — не сильные стороны таких способов записи чисел. Но они были удобны для простейшего бытового счета, а их изучение заставляет ценить привычный нам способ обозначения чисел: позиционные системы счисления.
👍20❤5👌2
Теорема Байеса
Жизнь не всегда непредсказуема. Сложно сказать, пойдет ли завтра дождь, вырастет ли стоимость портфеля на бирже, отведаете ли вкусный ужин в ресторане, в котором никогда не были. В таких случаях мы часто прикидываем шансы событий:
— кажется, завтра будет дождь, ведь он шёл всю последнюю неделю;
— акции дорожали последние три дня, я рассчитываю и сегодня увидеть рост;
— мои друзья остались довольны едой в том ресторане, поэтому мне там точно понравится.
А замечали, как мы адаптируем наши оценки на основе новых данных? За день до долгожданного похода в ресторан, вы прочитали о нём разгромную рецензию от ресторанного критика. Как это повлияет на вероятность вкусно покушать в этом месте?
Математик Томас Байес не просто подметил, как люди оценивают шансы событий и корректируют их, но и формализовал эти мысли в целое направление в статистике. Мы обсудим ключевую теорему этого направления, формулу Байеса, которая объясняет с точки зрения математики, как обновляются наши представления о вероятностях на основе новой информации. Это одна из важнейших теорем в терии вероятностей!
Спойлер: там фигурирует условная вероятность! Часто она дана в задаче, но если нет, то вычислить её можно по определению:
P(A|B) = P(A∩B) / P(B), эта формула есть на иллюстрации ниже.
Она обозначает вероятность события А, при условии, что произошло событие B.
Жизнь не всегда непредсказуема. Сложно сказать, пойдет ли завтра дождь, вырастет ли стоимость портфеля на бирже, отведаете ли вкусный ужин в ресторане, в котором никогда не были. В таких случаях мы часто прикидываем шансы событий:
— кажется, завтра будет дождь, ведь он шёл всю последнюю неделю;
— акции дорожали последние три дня, я рассчитываю и сегодня увидеть рост;
— мои друзья остались довольны едой в том ресторане, поэтому мне там точно понравится.
А замечали, как мы адаптируем наши оценки на основе новых данных? За день до долгожданного похода в ресторан, вы прочитали о нём разгромную рецензию от ресторанного критика. Как это повлияет на вероятность вкусно покушать в этом месте?
Математик Томас Байес не просто подметил, как люди оценивают шансы событий и корректируют их, но и формализовал эти мысли в целое направление в статистике. Мы обсудим ключевую теорему этого направления, формулу Байеса, которая объясняет с точки зрения математики, как обновляются наши представления о вероятностях на основе новой информации. Это одна из важнейших теорем в терии вероятностей!
Спойлер: там фигурирует условная вероятность! Часто она дана в задаче, но если нет, то вычислить её можно по определению:
P(A|B) = P(A∩B) / P(B), эта формула есть на иллюстрации ниже.
Она обозначает вероятность события А, при условии, что произошло событие B.
👍11✍5❤1
А теперь теорема Байеса:
P(A|B) = (P(B|A) / P(B)) * P(A).
Поясним её, обратившись к примеру с рестораном. Для наглядности заменим абстрактные события A и B на рассматриваемые:
P(будет вкусно|негативная рецензия) = (P(негативная рецензия|будет вкусно) / P(негативная рецензия)) * P(будет вкусно).
По формуле уже можно заметить, что изначальная вероятность P(будет вкусно) превращается в вероятность при условии негативной рецензии P(будет вкусно|негативная рецензия), и делает она это с помощью домножения на некоторый дробный коэффициент. Этот коэффициент и отражает обновление нашей исходной вероятности.
Предположим, на основании отзывов друзей у вас сложились некоторые убеждения насчёт качества кухни этого ресторана. Вы уверены в том, что еда понравится с вероятностью P(будет вкусно) = 80%.
И вот вы встречаете негативную рецензию ресторанного критика, к мнению которого прислушиваетесь, и уже не так уверены в кухне. Вы вспоминаете, что на 10% ресторанов, где вам нравится кухня, критик оставил негативную рецензию.
А в целом, у него 40% всех рецензий — негативные.
Это и есть искомые числитель и знаменатель в нашем коэффициенте! Когда мы получили информацию о том, что вышла негативная рецензия, коэффициент корректирует наши планы вкусно покушать: они изменятся в (10% / 40%) раз или попросту станут в 4 раза ниже. Сопоставим наши размышления с формулой Байеса:
P(будет вкусно|негативная рецензия) = (0.1 / 0.4)*0.8 = 0.2.
Вот так можно уточнять вероятность событий с помощью новых данных! Нужно только аккуратно определить, чему равен каждый элемент формулы.
А теперь задачка для вас!
Панк-группа записывает новый трек, и сегодня на очереди вокал. Обычно вокалист фальшивит на 26% всех дублей, но накануне вечером он громко спорил про анархию в шумном клубе. Это могло повлиять на его голос! Известно, что каждый третий вечер вокалист проводит за жаркими дискуссиями про анархию и что 70% всех случаев фальши — как раз из-за вечерних споров накануне.
Какова вероятность фальши сегодня, если вчера был как раз такой вечер?
P(A|B) = (P(B|A) / P(B)) * P(A).
Поясним её, обратившись к примеру с рестораном. Для наглядности заменим абстрактные события A и B на рассматриваемые:
P(будет вкусно|негативная рецензия) = (P(негативная рецензия|будет вкусно) / P(негативная рецензия)) * P(будет вкусно).
По формуле уже можно заметить, что изначальная вероятность P(будет вкусно) превращается в вероятность при условии негативной рецензии P(будет вкусно|негативная рецензия), и делает она это с помощью домножения на некоторый дробный коэффициент. Этот коэффициент и отражает обновление нашей исходной вероятности.
Предположим, на основании отзывов друзей у вас сложились некоторые убеждения насчёт качества кухни этого ресторана. Вы уверены в том, что еда понравится с вероятностью P(будет вкусно) = 80%.
И вот вы встречаете негативную рецензию ресторанного критика, к мнению которого прислушиваетесь, и уже не так уверены в кухне. Вы вспоминаете, что на 10% ресторанов, где вам нравится кухня, критик оставил негативную рецензию.
А в целом, у него 40% всех рецензий — негативные.
Это и есть искомые числитель и знаменатель в нашем коэффициенте! Когда мы получили информацию о том, что вышла негативная рецензия, коэффициент корректирует наши планы вкусно покушать: они изменятся в (10% / 40%) раз или попросту станут в 4 раза ниже. Сопоставим наши размышления с формулой Байеса:
P(будет вкусно|негативная рецензия) = (0.1 / 0.4)*0.8 = 0.2.
Вот так можно уточнять вероятность событий с помощью новых данных! Нужно только аккуратно определить, чему равен каждый элемент формулы.
А теперь задачка для вас!
Панк-группа записывает новый трек, и сегодня на очереди вокал. Обычно вокалист фальшивит на 26% всех дублей, но накануне вечером он громко спорил про анархию в шумном клубе. Это могло повлиять на его голос! Известно, что каждый третий вечер вокалист проводит за жаркими дискуссиями про анархию и что 70% всех случаев фальши — как раз из-за вечерних споров накануне.
Какова вероятность фальши сегодня, если вчера был как раз такой вечер?
👍19❤7😁1
Разберём вчерашнюю задачу про вокалиста панк-группы.
В ней применяется формула Байеса:
P(A|B) = (P(B|A) / P(B)) * P(A).
Определим наши события и их вероятности.
А — вокалист фальшивит при записи,
B — вечером накануне вокалист громко спорил про анархию.
Тогда найти нам нужно P(A|B) — вероятность фальши при условии, что вчера вечером он громко спорил.
Для этого нам потребуются три другие вероятности.
P(A) — вероятность того, что вокалист в принципе фальшивит, она по условию равна 26% или 0.26.
Для любого случайного дня зададим P(B) — вероятность того, что вокалист громко спорил накануне. Известно, что он проводит за этим занятием каждый третий вечер, значит, вероятность равна 1/3.
И самое тонкое: P(B|A) — вероятность споров накануне, при условии, что сейчас вокалист фальшивит. Она по условию равна 0.7, хотя формулировка там чуть другая: «Известно, что 70% всех случаев фальши — как раз из-за вечерних споров накануне». То есть дан факт фальши (она — уже произошедшее условие, поэтому пишется справа от вертикальной черты), и вероятность вчерашних споров при условии сегодняшней фальши — те самые 70% или 0.7.
Подставим всё в формулу:
P(A|B) = (P(B|A) / P(B)) * P(A) = (0.7 / (1/3)) * P(0.26) = 0.546 или 54.6%.
Что выше, чем обычная вероятность фальши этого вокалиста.
Ответ вполне закономерный: если громко спорить вечером, петь на следующий день будет тяжелее. 😆
Желаем вам хороших выходных без последствий для голоса!
В ней применяется формула Байеса:
P(A|B) = (P(B|A) / P(B)) * P(A).
Определим наши события и их вероятности.
А — вокалист фальшивит при записи,
B — вечером накануне вокалист громко спорил про анархию.
Тогда найти нам нужно P(A|B) — вероятность фальши при условии, что вчера вечером он громко спорил.
Для этого нам потребуются три другие вероятности.
P(A) — вероятность того, что вокалист в принципе фальшивит, она по условию равна 26% или 0.26.
Для любого случайного дня зададим P(B) — вероятность того, что вокалист громко спорил накануне. Известно, что он проводит за этим занятием каждый третий вечер, значит, вероятность равна 1/3.
И самое тонкое: P(B|A) — вероятность споров накануне, при условии, что сейчас вокалист фальшивит. Она по условию равна 0.7, хотя формулировка там чуть другая: «Известно, что 70% всех случаев фальши — как раз из-за вечерних споров накануне». То есть дан факт фальши (она — уже произошедшее условие, поэтому пишется справа от вертикальной черты), и вероятность вчерашних споров при условии сегодняшней фальши — те самые 70% или 0.7.
Подставим всё в формулу:
P(A|B) = (P(B|A) / P(B)) * P(A) = (0.7 / (1/3)) * P(0.26) = 0.546 или 54.6%.
Что выше, чем обычная вероятность фальши этого вокалиста.
Ответ вполне закономерный: если громко спорить вечером, петь на следующий день будет тяжелее. 😆
Желаем вам хороших выходных без последствий для голоса!
👍23👌2🎉1🤓1
Лето уже совсем близко, поэтому сегодняшнюю тему будем разбирать на примере с мороженным. У моря. Потому что ну очень хочется!
Вы наверняка слышали про математика Джона Нэша, а может даже смотрели фильм «Игры разума». Нэш — лауреат нобелевской премии по экономике и премии Абеля (её неофициально называют «Нобелевской премией по математике»). Результаты его работ широко используются в экономике, а основополагающим в его теории является понятие равновесия Нэша.
Вы наверняка слышали про математика Джона Нэша, а может даже смотрели фильм «Игры разума». Нэш — лауреат нобелевской премии по экономике и премии Абеля (её неофициально называют «Нобелевской премией по математике»). Результаты его работ широко используются в экономике, а основополагающим в его теории является понятие равновесия Нэша.
👍2😁1
Рассказать о равновесии Нэша можно довольно просто!
Представим, что на пляже есть два продавца мороженого: Алиса и Боря. Оба устанавливают цену мороженого в 50 рублей и не меняют её, но их ларьки находятся на приличном расстоянии. Ларек Алисы расположен на одном конце пляжа, ближе ко входу, а ларек Бори — на другом конце, ближе к воде.
Будем считать, что ларьки одинаково привлекательны с точки зрения сервиса. Тогда покупатели просто будут выбирать мороженое в ближайшем для них ларьке. Таким образом, люди, находящиеся ближе к входу пляжа, склонятся к покупке мороженого у Алисы, а те, кто находится ближе к воде, выберут мороженое у Бори.
Допустим, Боря переставит свой ларёк на середину пути от входа к воде. Теперь к нему будет ходить 3/4 посетителей пляжа (все, кто находится ближе к воде и половина тех, кто раньше бы покупал в киоске Алисы). Тогда Алисе останется лишь 1/4 посетителей пляжа, то есть она потеряет половину своей прибыли.
Чтобы исправить ситуацию, Алиса тоже перевезёт свой ларёк к середине пляжа, то есть, в два раза ближе к морю (в паре метров от места, где стоит Боря). Тогда справедливость восторжествует, к обоим продавцам вновь будет ходить одинаковое количество покупателей. Более того, в этой ситуации ни Боря, ни Алиса не могут подвинуть свой ларек куда-либо, чтобы увеличить свою прибыль при условии, что второй продавец останется на месте.
Это и есть наглядная демонстрация равновесия Нэша! В общем случае такое равновесие — это ситуация в теории игр, при которой ни один участник не может улучшить свое положение, изменив стратегию поведения, при условии, что все остальные игроки ничего не изменят. Нэш доказал существование такого равновесия в любой конечной игре. Помимо теории игр и экономики это понятие часто возникает в бизнесе, социологии, политологии и в повседневной жизни.
Предлагаем поднять за это вафельный стаканчик!
Представим, что на пляже есть два продавца мороженого: Алиса и Боря. Оба устанавливают цену мороженого в 50 рублей и не меняют её, но их ларьки находятся на приличном расстоянии. Ларек Алисы расположен на одном конце пляжа, ближе ко входу, а ларек Бори — на другом конце, ближе к воде.
Будем считать, что ларьки одинаково привлекательны с точки зрения сервиса. Тогда покупатели просто будут выбирать мороженое в ближайшем для них ларьке. Таким образом, люди, находящиеся ближе к входу пляжа, склонятся к покупке мороженого у Алисы, а те, кто находится ближе к воде, выберут мороженое у Бори.
Допустим, Боря переставит свой ларёк на середину пути от входа к воде. Теперь к нему будет ходить 3/4 посетителей пляжа (все, кто находится ближе к воде и половина тех, кто раньше бы покупал в киоске Алисы). Тогда Алисе останется лишь 1/4 посетителей пляжа, то есть она потеряет половину своей прибыли.
Чтобы исправить ситуацию, Алиса тоже перевезёт свой ларёк к середине пляжа, то есть, в два раза ближе к морю (в паре метров от места, где стоит Боря). Тогда справедливость восторжествует, к обоим продавцам вновь будет ходить одинаковое количество покупателей. Более того, в этой ситуации ни Боря, ни Алиса не могут подвинуть свой ларек куда-либо, чтобы увеличить свою прибыль при условии, что второй продавец останется на месте.
Это и есть наглядная демонстрация равновесия Нэша! В общем случае такое равновесие — это ситуация в теории игр, при которой ни один участник не может улучшить свое положение, изменив стратегию поведения, при условии, что все остальные игроки ничего не изменят. Нэш доказал существование такого равновесия в любой конечной игре. Помимо теории игр и экономики это понятие часто возникает в бизнесе, социологии, политологии и в повседневной жизни.
Предлагаем поднять за это вафельный стаканчик!
🎉29❤14😁10👍2
На прошлой неделе у нас был пост с задачей на формулу Байеса.
А сегодня — ещё одна важная формула из теории вероятностей, которая не раз пригодится при решении задач. Кстати, часто нужны обе формулы сразу!
Итак, встречайте: формула полной вероятности (звучит претенциозно, не правда ли?) 😄
Именно она изображена на иллюстрации выше, но пусть вас не пугает её вид. Суть тут довольно простая, разберём на примере.
Пусть у вас есть 3 пары летней обуви, и сегодня вы можете надеть любую из них. Обозначим каждое из трёх событий «надеть пару номер n» как H с соответствующим индексом. У каждого из этих событий — своя вероятность. Например, пусть
P(H₁) = 0.2, P(H₂) = 0.3, P(H₃) = 0.5. События эти несовместны, то есть нельзя надеть две пары сразу, только какую-то одну. А ещё сумма вероятностей равна 1, то есть объединение этих событий даёт всё вероятностное пространство.
У каждой пары — своя вероятность натереть вам ноги! Обозначим событие «натереть ноги» за А. Тогда, например, событие A|H₁ — это вероятность натереть ноги, надев первую пару. Пусть все эти вероятности тоже даны:
P(A|H₁) = 0.1, P(A|H₂) = 0.4, P(A|H₃) = 0.7. Обратите внимание, сумма этих вероятностей уженикому ничего не должна быть равна 1.
Чему же сегодня равна P(A)? Вероятность натереть ноги складывается из вероятностей натирания в каждой из пар, но вероятность надеть каждую из пар — неодинакова, это тоже надо учитывать.
Поэтому P(A) = P(A|H₁)*P(H₁) + P(A|H₂)*P(H₂) + P(A|H₃)*P(H₃).
Мы как бы собрали полную вероятность из отдельных кусочков, учитывая вес (то бишь вероятность) каждого из этих кусочков. Давайте вычислим сумму этих маленьких произведений:
P(A) = 0.1*0.2 + 0.4*0.3 + 0.7*0.5 =
= 0.02 + 0.12 + 0.35 = 0.49.
Вероятность получилась довольно высокая! Основной вклад в этот ответ дала третья пара: она часто натирает, но при этом она явно вам нравится, раз вы выбираете её в 50% случаев. Что ж, любовь зла, но мы такое не одобряем. 😅
А сегодня — ещё одна важная формула из теории вероятностей, которая не раз пригодится при решении задач. Кстати, часто нужны обе формулы сразу!
Итак, встречайте: формула полной вероятности (звучит претенциозно, не правда ли?) 😄
Именно она изображена на иллюстрации выше, но пусть вас не пугает её вид. Суть тут довольно простая, разберём на примере.
Пусть у вас есть 3 пары летней обуви, и сегодня вы можете надеть любую из них. Обозначим каждое из трёх событий «надеть пару номер n» как H с соответствующим индексом. У каждого из этих событий — своя вероятность. Например, пусть
P(H₁) = 0.2, P(H₂) = 0.3, P(H₃) = 0.5. События эти несовместны, то есть нельзя надеть две пары сразу, только какую-то одну. А ещё сумма вероятностей равна 1, то есть объединение этих событий даёт всё вероятностное пространство.
У каждой пары — своя вероятность натереть вам ноги! Обозначим событие «натереть ноги» за А. Тогда, например, событие A|H₁ — это вероятность натереть ноги, надев первую пару. Пусть все эти вероятности тоже даны:
P(A|H₁) = 0.1, P(A|H₂) = 0.4, P(A|H₃) = 0.7. Обратите внимание, сумма этих вероятностей уже
Чему же сегодня равна P(A)? Вероятность натереть ноги складывается из вероятностей натирания в каждой из пар, но вероятность надеть каждую из пар — неодинакова, это тоже надо учитывать.
Поэтому P(A) = P(A|H₁)*P(H₁) + P(A|H₂)*P(H₂) + P(A|H₃)*P(H₃).
Мы как бы собрали полную вероятность из отдельных кусочков, учитывая вес (то бишь вероятность) каждого из этих кусочков. Давайте вычислим сумму этих маленьких произведений:
P(A) = 0.1*0.2 + 0.4*0.3 + 0.7*0.5 =
= 0.02 + 0.12 + 0.35 = 0.49.
Вероятность получилась довольно высокая! Основной вклад в этот ответ дала третья пара: она часто натирает, но при этом она явно вам нравится, раз вы выбираете её в 50% случаев. Что ж, любовь зла, но мы такое не одобряем. 😅
❤12👍6😁2
А теперь задачка для вас! Подсказка: в ней надо использовать и формулу полной вероятности, и теорему Байеса P(A|B) = (P(B|A) / P(B)) * P(A) .
Решения прячьте подспойлер , а мы опубликуем ответ в пятницу.
В городе N можно вызвать такси с помощью приложений X и Y.
Каждое из них имеет в своей базе по 1000 водителей (и эти базы не пересекаются). В приложении X все водители имеют рейтинг 4.5 и выше, а в приложении В таковы только 400 водителей из 1000, остальные же имеют рейтинг от 3.5 до 4.5.
Володя случайно выбирает для заказа одно из двух приложений, и приехавший водитель имеет рейтинг 4.7.
Какова вероятность, что использовалось приложение X?Решения прячьте под
👍4❤1
Марафон по математике завершился! 🎉
Мы рады поделиться результатами нашего математического марафона. За две недели участники погрузились в темы множеств, комбинаторики и теории вероятностей, прошли интерактивные уроки и участвовали в закрытых эфирах с нашими преподавателями.
Свои силы в марафоне попробовали 296 участников, и мы гордимся каждым из них! Особое признание заслуживают 119 отважных участников, которые выполняли задания каждый день и прошли всю дистанцию до конца! 🙌
Все, кто успешно завершил марафон, получили промокод на скидку на наши курсы по математике и анализу данных. Это награда за их усердие и желание учиться. 🏆
Уверены, что их успехи и достижения вдохновят многих из вас на дальнейшее изучение математики. И, кто знает, возможно, в следующий раз именно вы станете одним из участников! ✨
Приглашаем участников марафона поделиться впечатлениями в комментариях!
Мы рады поделиться результатами нашего математического марафона. За две недели участники погрузились в темы множеств, комбинаторики и теории вероятностей, прошли интерактивные уроки и участвовали в закрытых эфирах с нашими преподавателями.
Свои силы в марафоне попробовали 296 участников, и мы гордимся каждым из них! Особое признание заслуживают 119 отважных участников, которые выполняли задания каждый день и прошли всю дистанцию до конца! 🙌
Все, кто успешно завершил марафон, получили промокод на скидку на наши курсы по математике и анализу данных. Это награда за их усердие и желание учиться. 🏆
Уверены, что их успехи и достижения вдохновят многих из вас на дальнейшее изучение математики. И, кто знает, возможно, в следующий раз именно вы станете одним из участников! ✨
Приглашаем участников марафона поделиться впечатлениями в комментариях!
🍾23❤7👍3🔥3👏3
Разберём задачу про такси, которую постили в среду.
Для решения понадобятся и теорема Байеса, и формула полной вероятности.
Введём обозначения для событий:
X — Володя использовал для вызова такси приложение X,
Y — Володя использовал для вызова такси приложение Y,
T — приехал водитель с рейтингом 4.5 или выше.
В общем виде теорема Байеса выглядит так:
P(A|B) = P(B|A)*P(A) / P(B).
Нам нужно найти вероятность того, что выбрано приложение X, при условии, что приехал водитель с высоким рейтингом. То есть найти
P(X|T) = P(T|X)*P(X) / P(T).
Распишем, чему равны вероятности из правой части.
Вероятность высокого рейтинга при условии выбора первого приложения — стопроцентная, ведь в первом приложении только такие водители и есть. :) Поэтому P(T|X) = 1.
По условию выбора приложения случаен, поэтому вероятность выбора каждого равна 0.5, то есть P(X) = 0.5.
А вот с P(T) ситуация чуть сложнее, она состоит из суммы вероятностей
высокого рейтинга в случае приложения А и в случае приложения В, при этом
вероятность использования каждого из них по 0.5.
Нужна формула полной вероятности:
P(T) = P(T|X)*P(X) + P(T|Y)*P(Y) = 1*0.5 + 0.4*0.5.
Множитель 0.4 появился, так как во втором приложении только 400 водителей из 1000 имеют высокий рейтинг, поэтому
P(T|Y) = 400 / 1000 = 0.4.
Итого:
P(X|T) = P(T|X)*P(X) / P(T) = 1*0.5 / (1*0.5 + 0.4*0.5)= 0.5/0.7 = 5/7.
Ответ: 5/7
Приятных вам поездок!
Для решения понадобятся и теорема Байеса, и формула полной вероятности.
Введём обозначения для событий:
X — Володя использовал для вызова такси приложение X,
Y — Володя использовал для вызова такси приложение Y,
T — приехал водитель с рейтингом 4.5 или выше.
В общем виде теорема Байеса выглядит так:
P(A|B) = P(B|A)*P(A) / P(B).
Нам нужно найти вероятность того, что выбрано приложение X, при условии, что приехал водитель с высоким рейтингом. То есть найти
P(X|T) = P(T|X)*P(X) / P(T).
Распишем, чему равны вероятности из правой части.
Вероятность высокого рейтинга при условии выбора первого приложения — стопроцентная, ведь в первом приложении только такие водители и есть. :) Поэтому P(T|X) = 1.
По условию выбора приложения случаен, поэтому вероятность выбора каждого равна 0.5, то есть P(X) = 0.5.
А вот с P(T) ситуация чуть сложнее, она состоит из суммы вероятностей
высокого рейтинга в случае приложения А и в случае приложения В, при этом
вероятность использования каждого из них по 0.5.
Нужна формула полной вероятности:
P(T) = P(T|X)*P(X) + P(T|Y)*P(Y) = 1*0.5 + 0.4*0.5.
Множитель 0.4 появился, так как во втором приложении только 400 водителей из 1000 имеют высокий рейтинг, поэтому
P(T|Y) = 400 / 1000 = 0.4.
Итого:
P(X|T) = P(T|X)*P(X) / P(T) = 1*0.5 / (1*0.5 + 0.4*0.5)= 0.5/0.7 = 5/7.
Ответ: 5/7
Приятных вам поездок!
👍10👌1
Число Шеннона
Сегодня мы принесли вам интересный факт про шахматы. А точнее — про число всевозможных шахматных партий. Спойлер: это число такое большое, что превосходит количество атомов во Вселенной! Но давайте по порядку.
В середине XX века американский математик Клод Шеннон разрабатывал компьютерные программы, которые могли бы играть в шахматы. И пришёл к тому, что количество всевозможных партий можно оценить числом 10¹²⁰. Дать компьютеру «просто просчитать» все эти партии не получится — у нас нет даже рядом лежащих мощностей, чтобы просчитать такое за адекватное (или даже не очень адекватное) время.
На самом деле эта оценка достаточно грубая и основана на среднем количестве возможных ходов в каждый момент времени и на средней длительности партии. Но зато число получилось впечатляющее. :)
Подробнее про то, как получить число Шеннона и другие оценки, можно посмотреть в этом видео. Нужны лишь знания базовых правил шахмат и правило произведения из комбинаторики.
А что насчёт количества атомов (или даже частиц) во вселенной? Их, конечно, тоже много, но оценка гораздо скромнее — около 10⁸⁰. Про то, как прикинуть это количество — есть отдельное видео. В нём ещё содержится бонусный кусочек информации: через сколько лет человечество истратит все частицы в обозримой Вселенной, если популяция продолжит расти с текущей скоростью. И это подозрительно скоро. 😅
Кажется, нам нужна новая Вселенная! И более мощные компьютеры.
Сегодня мы принесли вам интересный факт про шахматы. А точнее — про число всевозможных шахматных партий. Спойлер: это число такое большое, что превосходит количество атомов во Вселенной! Но давайте по порядку.
В середине XX века американский математик Клод Шеннон разрабатывал компьютерные программы, которые могли бы играть в шахматы. И пришёл к тому, что количество всевозможных партий можно оценить числом 10¹²⁰. Дать компьютеру «просто просчитать» все эти партии не получится — у нас нет даже рядом лежащих мощностей, чтобы просчитать такое за адекватное (или даже не очень адекватное) время.
На самом деле эта оценка достаточно грубая и основана на среднем количестве возможных ходов в каждый момент времени и на средней длительности партии. Но зато число получилось впечатляющее. :)
Подробнее про то, как получить число Шеннона и другие оценки, можно посмотреть в этом видео. Нужны лишь знания базовых правил шахмат и правило произведения из комбинаторики.
А что насчёт количества атомов (или даже частиц) во вселенной? Их, конечно, тоже много, но оценка гораздо скромнее — около 10⁸⁰. Про то, как прикинуть это количество — есть отдельное видео. В нём ещё содержится бонусный кусочек информации: через сколько лет человечество истратит все частицы в обозримой Вселенной, если популяция продолжит расти с текущей скоростью. И это подозрительно скоро. 😅
Кажется, нам нужна новая Вселенная! И более мощные компьютеры.
❤9👍4👏2🆒2🤣1
Сегодня мы принесли вам задачу не на математические знания, а на общую логику и смекалку. Надеемся, вам понравится. 🌈
В стране Облакандии живут волшебные бессмертные единорожки. Однажды в этой стране появился злой волшебник, который стал их ловить и заточать в темницу. Сейчас в ней 777 печальных единорожек.
Волшебник посадил каждого в отдельную пещеру и предложил им колдовскую сделку. Раз в день их будут в случайном порядке по одному приводить в пустую пещеру, где нет ничего, кроме одного маленького светильника-радуги на столе, который единорожке разрешается включить, выключить или ничего с ним не делать. Неизвестно, включена или выключена маленькая радуга изначально, но все знают, в какой день отвели в пещеру первого единорожка.
Так как выбор каждый день случаен, в какой-то может оказаться, что одни единорожки уже были в пещере с маленькой радугой несколько раз, а до других очередь ещё не дошла.
Но гарантируется, что рано или поздно каждый из них побывает в пещере сколько угодно раз.
В любой момент единорожек, приведённый в пещеру с радугой, может объявить, что все единорожки уже побывали в пещере хотя бы по одному разу; если он прав, то всех отпустят прыгать по Облакандии дальше, если нет — оставят в мрачном заключении навсегда. До распределения по одиночным пещерам у единорожек есть возможность договориться между собой, после этого никакой коммуникации между ними не будет. Помогите им разработать стратегию для выхода на свободу!
Пишите свои решения в комментариях подскрытым текстом , разбор опубликуем в пятницу.
В стране Облакандии живут волшебные бессмертные единорожки. Однажды в этой стране появился злой волшебник, который стал их ловить и заточать в темницу. Сейчас в ней 777 печальных единорожек.
Волшебник посадил каждого в отдельную пещеру и предложил им колдовскую сделку. Раз в день их будут в случайном порядке по одному приводить в пустую пещеру, где нет ничего, кроме одного маленького светильника-радуги на столе, который единорожке разрешается включить, выключить или ничего с ним не делать. Неизвестно, включена или выключена маленькая радуга изначально, но все знают, в какой день отвели в пещеру первого единорожка.
Так как выбор каждый день случаен, в какой-то может оказаться, что одни единорожки уже были в пещере с маленькой радугой несколько раз, а до других очередь ещё не дошла.
Но гарантируется, что рано или поздно каждый из них побывает в пещере сколько угодно раз.
В любой момент единорожек, приведённый в пещеру с радугой, может объявить, что все единорожки уже побывали в пещере хотя бы по одному разу; если он прав, то всех отпустят прыгать по Облакандии дальше, если нет — оставят в мрачном заключении навсегда. До распределения по одиночным пещерам у единорожек есть возможность договориться между собой, после этого никакой коммуникации между ними не будет. Помогите им разработать стратегию для выхода на свободу!
Пишите свои решения в комментариях под
👍12🦄6🤔2✍1
Сказ о том, почему 0.(9)=1
Математика — очень логичная наука, даже если иногда кажется, что это не так. Случай с 0.(9)=1 — один из примеров, когда поверить на слово очень тяжело. Но это правда! Здесь между числами действительно стоит равенство, а не «приближённо равно».
Как часто бывает, доказательств тут несколько. Надеемся, что хотя бы одно из них вас убедит. ☺️
Доказательство №1 — через алгоритм перевода
Для начала вспомним, что запись 0.(9) обозначает 0.9999... , то есть бесконечную периодическую дробь.
Мы рассказывали в отдельном посте, как перевести такую бесконечную десятичную дробь в обыкновенную. Воспользуемся этим алгоритмом:
x = 0.(9)
10x = 9.(9)
10x - x = 9.(9) - 0.(9)
9x = 9
x = 1 ⇒ 0.(9)=1
Доказательство №2 — через сумму
1/3 = 0.33333333… = 0.(3)
Тогда можно сказать, что
1 = 3*1/3 = 1/3 + 1/3 + 1/3 = 0.(3) + 0.(3) + 0.(3) = 0.(9).
Можно подставить и другие периодические дроби, дающие в сумме 1, например
1/11 = 0.0909090909… = 0.(09) и 10/11 = 0.9090909090… = 0.(90).
Тогда
1 = 11/11 = 1/11 + 10/11 = 0.(09) + 0.(90) = 0.(99) = 0.(9).
Доказательство №3 — через геометрическую прогрессию (самое сложное, но самое научное)
Что вообще такое 0.(9)? Это сумма бесконечного количества конечных десятичных дробей:
0.(9) = 0.9 + 0.09 + 0.009 + 0.0009 + 0.00009 + … .
Слагаемые образуют бесконечную геометрическую прогрессию, почитать про это можно, например, тут. Каждый следующий член прогрессии меньше предыдущего в 10 раз, то есть её коэффициент q равен 0.1.
По формуле суммы для x первых членов геометрической прогрессии
Sₓ = b₁ / (1-q), где b₁ — первый член прогрессии.
Подставим наши значения:
Sₓ = 0.9 / (1-0.1) = 0.9 / 0.9 = 1.
Аналогично можно доказать, что 9.(9) = 10, 99.(9) = 100, а 999.(9) = 1000.
В заключении скажем, что как 1/3 и 0.(3) — это просто два разных способа обозначить одно и то же число, так и 1 и 0.(9) — просто два разных имени для одной и той же математической сущности. И это нормально, ведь все числа — всего лишь придуманные людьми абстракции.
Математика — очень логичная наука, даже если иногда кажется, что это не так. Случай с 0.(9)=1 — один из примеров, когда поверить на слово очень тяжело. Но это правда! Здесь между числами действительно стоит равенство, а не «приближённо равно».
Как часто бывает, доказательств тут несколько. Надеемся, что хотя бы одно из них вас убедит. ☺️
Доказательство №1 — через алгоритм перевода
Для начала вспомним, что запись 0.(9) обозначает 0.9999... , то есть бесконечную периодическую дробь.
Мы рассказывали в отдельном посте, как перевести такую бесконечную десятичную дробь в обыкновенную. Воспользуемся этим алгоритмом:
x = 0.(9)
10x = 9.(9)
10x - x = 9.(9) - 0.(9)
9x = 9
x = 1 ⇒ 0.(9)=1
Доказательство №2 — через сумму
1/3 = 0.33333333… = 0.(3)
Тогда можно сказать, что
1 = 3*1/3 = 1/3 + 1/3 + 1/3 = 0.(3) + 0.(3) + 0.(3) = 0.(9).
Можно подставить и другие периодические дроби, дающие в сумме 1, например
1/11 = 0.0909090909… = 0.(09) и 10/11 = 0.9090909090… = 0.(90).
Тогда
1 = 11/11 = 1/11 + 10/11 = 0.(09) + 0.(90) = 0.(99) = 0.(9).
Доказательство №3 — через геометрическую прогрессию (самое сложное, но самое научное)
Что вообще такое 0.(9)? Это сумма бесконечного количества конечных десятичных дробей:
0.(9) = 0.9 + 0.09 + 0.009 + 0.0009 + 0.00009 + … .
Слагаемые образуют бесконечную геометрическую прогрессию, почитать про это можно, например, тут. Каждый следующий член прогрессии меньше предыдущего в 10 раз, то есть её коэффициент q равен 0.1.
По формуле суммы для x первых членов геометрической прогрессии
Sₓ = b₁ / (1-q), где b₁ — первый член прогрессии.
Подставим наши значения:
Sₓ = 0.9 / (1-0.1) = 0.9 / 0.9 = 1.
Аналогично можно доказать, что 9.(9) = 10, 99.(9) = 100, а 999.(9) = 1000.
В заключении скажем, что как 1/3 и 0.(3) — это просто два разных способа обозначить одно и то же число, так и 1 и 0.(9) — просто два разных имени для одной и той же математической сущности. И это нормально, ведь все числа — всего лишь придуманные людьми абстракции.
👍22😨14🔥8🤯2😱2🌚2❤1👎1👀1
Разберём задачу про радужных единорожек из этого поста. Задача — одна из версий известной задачи о 100 узниках и лампочке. Их довольно много, сложность зависит от исходных условий. Наши — весьма мягкие. 😃
Сначала кажется, что одна лампочка-радуга — это слишком маленький и простой носитель, чтобы хотя бы кто-то мог узнать информацию обо всех единорожках. Но на самом деле даже её будет достаточно, чтобы все единорожки спаслись. Им нужно придерживаться такого алгоритма:
1. Единорожку, которого привели в пещеру с радугой в первый день, будем называть «счётчиком». В своё первое посещение он должен выключить радугу (или не трогать, если она уже выключена), а в уме запомнить число 1.
2. Все остальные единорожки будут называться «наблюдатели». Они не могут выключать радугу. Когда наблюдатель заходит в пещеру, сначала он должен проверить, горит ли радуга. Если горит, то он ничего не делает. Если не горит, то он должен включить её, но только в том случае, если раньше не включал. То есть наблюдатель должен включить радугу лишь один раз, а при последующих заходах в пещеру — просто любоваться ею.
3. Каждый раз, когда счётчик заходит в пещеру, он должен посмотреть, горит ли радуга. Если радуга горит, то этот единорожка выключает её и прибавляет к числу, которое запомнил в прошлый раз, единицу.
4. Когда число, которое помнит счётчик, становится равно 777, он говорит, что все побывали в пещере, и злой волшебник, скрипя зубами, отпускает бедных единорожек на свободу.
А теперь давайте разберемся, как это работает!
Если каждый день выбирается случайный единорожек для похода в пещеру, то может случиться, что кто-то из них дооооолго туда не попадёт, а другие уже побывают несколько раз. Но единорожки бессмертны, а условие гарантировало нам, что все они в какой-то момент окажутся в пещере, так что нужно просто дождаться. Время — не проблема. 😊
Каждый раз после первого, когда «счётчик» заходит в комнату и видит горящую радугу, это значит, что ее кто-то зажёг — ведь когда он уходил в прошлый раз, радуга не горела! Но кто же мог зажечь радугу? Только один из тех, кто раньше этого не делал. Когда счетчик дойдет до числа 777, это будет означать, все остальные 776 единорожек точно побывали в пещере хотя бы по одному разу. А значит, условие злого волшебника выполнено. Да здравствуют единорожки!
Сначала кажется, что одна лампочка-радуга — это слишком маленький и простой носитель, чтобы хотя бы кто-то мог узнать информацию обо всех единорожках. Но на самом деле даже её будет достаточно, чтобы все единорожки спаслись. Им нужно придерживаться такого алгоритма:
1. Единорожку, которого привели в пещеру с радугой в первый день, будем называть «счётчиком». В своё первое посещение он должен выключить радугу (или не трогать, если она уже выключена), а в уме запомнить число 1.
2. Все остальные единорожки будут называться «наблюдатели». Они не могут выключать радугу. Когда наблюдатель заходит в пещеру, сначала он должен проверить, горит ли радуга. Если горит, то он ничего не делает. Если не горит, то он должен включить её, но только в том случае, если раньше не включал. То есть наблюдатель должен включить радугу лишь один раз, а при последующих заходах в пещеру — просто любоваться ею.
3. Каждый раз, когда счётчик заходит в пещеру, он должен посмотреть, горит ли радуга. Если радуга горит, то этот единорожка выключает её и прибавляет к числу, которое запомнил в прошлый раз, единицу.
4. Когда число, которое помнит счётчик, становится равно 777, он говорит, что все побывали в пещере, и злой волшебник, скрипя зубами, отпускает бедных единорожек на свободу.
А теперь давайте разберемся, как это работает!
Если каждый день выбирается случайный единорожек для похода в пещеру, то может случиться, что кто-то из них дооооолго туда не попадёт, а другие уже побывают несколько раз. Но единорожки бессмертны, а условие гарантировало нам, что все они в какой-то момент окажутся в пещере, так что нужно просто дождаться. Время — не проблема. 😊
Каждый раз после первого, когда «счётчик» заходит в комнату и видит горящую радугу, это значит, что ее кто-то зажёг — ведь когда он уходил в прошлый раз, радуга не горела! Но кто же мог зажечь радугу? Только один из тех, кто раньше этого не делал. Когда счетчик дойдет до числа 777, это будет означать, все остальные 776 единорожек точно побывали в пещере хотя бы по одному разу. А значит, условие злого волшебника выполнено. Да здравствуют единорожки!
🦄21👍7🥰3
Перевод из десятичной системы счисления в двоичную и обратно
Мы уже рассказывали о том, какими бывают системы счисления.
Сегодня поговорим о двух важных и часто используемых: двоичной и десятичной. Название позиционных систем счисления напрямую связано с количеством цифр в них. В двоичной их всего две, 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. Ответ как всегда оставляйте подскрытым тестом .
Мы уже рассказывали о том, какими бывают системы счисления.
Сегодня поговорим о двух важных и часто используемых: двоичной и десятичной. Название позиционных систем счисления напрямую связано с количеством цифр в них. В двоичной их всего две, 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. Ответ как всегда оставляйте под
👍15❤4🔥2🆒2👏1
Сегодня хотим рассказать вам про задачу о стабильных браках. Ещё её называют задачей о марьяже.
Несмотря на то, что её классическая формулировка описывает поиск наилучшего супруга/супруги, в реальности эта задача нашла широчайшее применение. Недаром в 2012 за её решение авторов удостоили Нобелевской премии по экономике (хотя решение было опубликовано аж в 1962 году).
С помощью описанного алгоритма ординаторы и интерны находят потенциальные больницы для работы, студенты выбирают школы/колледжи, команды нанимают спортсменов, фирмы — стажёров или работников, интернет-пользователям назначается сервер. А ещё адаптация этого алгоритма помогает находить попутчиков или соседей по квартире.
Итак, пусть есть N мужчин и N женщин, все гетеросексуальны (иначе нужен другой алгоритм). Пусть у всех есть свой список предпочтений, то есть они могут упорядочить особей противоположного пола в порядке убывания привлекательности вот лично для себя.
Требуется составить устойчивые пары, из которых никто не хочет сбежать с кем-то другим. То есть не должно быть ситуаций, когда вам нравится чужая жена больше, чем своя, и при этом чужая жена тоже предпочитает вас своему мужу.
И было доказано, что алгоритм нахождения устойчивых пар существует! Правда счастья он никому не обещает.
Но зато теорема утверждает, что решение есть для любого N, оно находится за конечное (хотя и довольно большое) количество шагов, и что оно подбирает наилучшую пару для «активной стороны» — то есть для того пола, который делает предложение.
Наглядно данный алгоритм описан в этом видео, а в дополнении к нему поясняют доказательство и рассказывают про применения алгоритма в реальности. Советуем посмотреть оба видео. 😊
И пусть любой выбор в вашей жизни будет не только оптимальным, но и счастливым! 🥂
Несмотря на то, что её классическая формулировка описывает поиск наилучшего супруга/супруги, в реальности эта задача нашла широчайшее применение. Недаром в 2012 за её решение авторов удостоили Нобелевской премии по экономике (хотя решение было опубликовано аж в 1962 году).
С помощью описанного алгоритма ординаторы и интерны находят потенциальные больницы для работы, студенты выбирают школы/колледжи, команды нанимают спортсменов, фирмы — стажёров или работников, интернет-пользователям назначается сервер. А ещё адаптация этого алгоритма помогает находить попутчиков или соседей по квартире.
Итак, пусть есть N мужчин и N женщин, все гетеросексуальны (иначе нужен другой алгоритм). Пусть у всех есть свой список предпочтений, то есть они могут упорядочить особей противоположного пола в порядке убывания привлекательности вот лично для себя.
Требуется составить устойчивые пары, из которых никто не хочет сбежать с кем-то другим. То есть не должно быть ситуаций, когда вам нравится чужая жена больше, чем своя, и при этом чужая жена тоже предпочитает вас своему мужу.
И было доказано, что алгоритм нахождения устойчивых пар существует! Правда счастья он никому не обещает.
Но зато теорема утверждает, что решение есть для любого N, оно находится за конечное (хотя и довольно большое) количество шагов, и что оно подбирает наилучшую пару для «активной стороны» — то есть для того пола, который делает предложение.
Наглядно данный алгоритм описан в этом видео, а в дополнении к нему поясняют доказательство и рассказывают про применения алгоритма в реальности. Советуем посмотреть оба видео. 😊
И пусть любой выбор в вашей жизни будет не только оптимальным, но и счастливым! 🥂
YouTube
Stable Marriage Problem - Numberphile
Discuss on Reddit: https://redd.it/2fgu97
More links & stuff in full description below ↓↓↓
Featuring Dr Emily Riehl. Continues with the more mathematical bit at: https://youtu.be/LtTV6rIxhdo
The Gale/Shapley paper: https://bit.ly/StableMarriage
Animation and…
More links & stuff in full description below ↓↓↓
Featuring Dr Emily Riehl. Continues with the more mathematical bit at: https://youtu.be/LtTV6rIxhdo
The Gale/Shapley paper: https://bit.ly/StableMarriage
Animation and…
👍12🍾4❤3
Модульная арифметика
Любому школьнику известно, что числа 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. Остатки совпали!
Кстати, оба эти числа сравнимы с 3 по модулю 11, то есть с тем самым остатком от деления на 11.
Ещё пример: верно, что 29 ≡ 13 (mod 8), то есть числа 29 и 13 равны по модулю 8, ведь (29-13)⋮8. Более того, 29 ≡ 13 ≡ 5 (mod 8), ведь 5 — это и есть остаток от деления каждого из этих чисел на 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?
В обоих случаях требуются наименьшие возможные ответы. Они должны быть меньше, чем то число, по чьему модулю мы работаем.
Любому школьнику известно, что числа 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. Остатки совпали!
Кстати, оба эти числа сравнимы с 3 по модулю 11, то есть с тем самым остатком от деления на 11.
Ещё пример: верно, что 29 ≡ 13 (mod 8), то есть числа 29 и 13 равны по модулю 8, ведь (29-13)⋮8. Более того, 29 ≡ 13 ≡ 5 (mod 8), ведь 5 — это и есть остаток от деления каждого из этих чисел на 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?
В обоих случаях требуются наименьшие возможные ответы. Они должны быть меньше, чем то число, по чьему модулю мы работаем.
👍8❤3👌1