Mathreshka

С новым учебным годом

В прошлом году я преподавал в RSM 5-му и 7-му классам олимпиадную математику. Или как у них говорят, competition mathematics. Очень был рад, что начало сезона у олимпиадников идёт со сдвигом в пару недель относительно стандартной программы. Ну а теперь уже привычка.

Итак, возвращаемся с летних каникул к любимой теме соавтора Матрёшки – клетке. Очевидная шахматная аналогия не всегда помогает в решении задач по примеру сегодняшней.

А если вам вдруг захотелось поупражняться в задачах на клетчатой бумаге, то вот наша коллекция:
– Клеточный отбор (#30)
– Столбец квадратов (#54)
– Баги (#56)
– Дно коробки (#62)
– Робот на шахматной доске (#71)

и другие…

• Прямоугольники на доске 10х10
• Решение

​​Задача Бернулли-Эйлера о перепутанных письмах

Классическая задача Бернулли-Эйлера формулируется следующим образом.

Формулировка (№141)
Некто написал шесть писем шести различным людям и заготовил шесть конвертов с их адресами. Сколькими способами можно вложить письма в конверты, чтобы ни одно письмо не попало тому лицу, которому оно адресовано?

В качестве реверанса к предыдущему посту проинтерпретируем эту задачу в шахматных терминах: ладья на i-й вертикали и j-й горизонтали будет соответствовать i-му письму, упакованному в j-й конверт. С учётом этого получаем

Эквивалентную формулировку
Сколькими способами на доске 6х6 можно расставить 6 ладей так, чтобы они не били друг друга и не стояли на главной диагонали?

Альтернативная формулировка создаёт новый контекст с сопуствующим инструментарием. Поэтому возможно кому-то будет удобнее решать эту задачу в шахматных терминах.

#олимпиада #классическаязадача

• Решение

​​Шахматные задачи

Кроме математики мы также любим шахматы. Сегодня открывается турнир претендентов (и претенденток), который пройдёт в Торонто с 3 по 23 апреля. Победитель турнира сыграет матч за титул с действующим чемпионом мира по шахматам Дин Лижэнем. По этому поводу предлагаем вам решить авторскую задачу. Попутно также отметим, что шахматные задачи можно разделить на два типа:

– собственно шахматные, использующие полный набор правил и тренирующие навыки игры (например, как сегодняшняя)
– математические / логические, использующие некоторую шахматную механику, но решения которых лежат вне плоскости игры (например, как эта)

#шахматы #авторская

Условие (№140)

Какое максимальное количество ферзей можно получить на шахматной доске, играя по правилам? Какое максимальное количество фигур может присутствовать на доске в этот момент?

• Решение

Игры на клетчатой бумаге

Клетка – неисчерпаемый источник задач, игр и головоломок. В дополнение к раз и два представляем ещё одну игру с симпатичным решением. Примечательно, что во всех упомянутых сейчас задачах применяются совершенно разные стратегии выигрыша.

#олимпиада #игра

• Игра в квадрат
• Решение

Родственные задачи

Пополняем коллекцию логистических задач. Вообще есть гипотеза, что сегодняшняя задача и задачи из наших предыдущих постов:

– Королева бензоколонки (про кольцевую автодорогу)
– 50 байкеров (про максимальное расстояние на фиксированном количестве топлива)
– Перевозка СПГ (про максимальное количество доставленного груза)

эквивалентны. А именно, что есть некая общая постановка, к которой можно подогнать все задачи этого цикла. Было бы интересно в этом разобраться.

• Кругосветка
• Решение

Целое и дробное

Целой частью числа x называется максимальное целое число, не превосходящее x. Обычно целую часть числа обозначают квадратными скобками, например, [-√2] = -2. Дробной частью числа x называется число x - [x], то есть то, что остаётся от числа x после вычитания из него целой части. Обозначается фигурными скобками {x} = x - [x].

Если длина стороны квадрата равна x, то длина диагонали равна x√2. Если длина стороны куба равна x, то длина диагонали равна x√3. Если же длина стороны d-мерного куба равна x, то длина его диагонали равна x√d. Такова увертюра к сегодняшней задаче.

• Про дробную часть диагонали
• Решение

С Новым годом 2024

Лучше всего, конечно, пять звёздочек!
Фильм «Карнавальная ночь»

Дорогие друзья! Внезапно оказалось, что это уже 7-й по счёту Новый год, который мы встречаем вместе с вами. Мы, два математика и два иллюстратора, делимся с вами красивыми задачами, всегда авторскими решениями и в классном оформлении. Вся эта кипучая деятельность держится в основном на одном – вашем интересе. Поэтому большое СПАСИБО за то, что вы с нами.

Пусть новый год принесёт вам очень много радости и счастья! А чтобы дополнить праздничный антураж – с нас задача!

• Разноцветное пространство
• Решение

Отраслевая адаптация

Исходная версия задачи формулируется для верблюдов и бананов. Суть в том, что верблюд может в качестве источника энергии использовать полезный груз, которые ему надо перенести. Понятно, чем больше расстояние, тем меньше он сможет доставить. Единственная (!) современная промышленная аналогия данному феномену – перевозка сжиженного природного газа (СПГ). Я не знаю другого энергоносителя, который использовался бы подобным образом. Нет ведь бензовоза, который бы сливал горючее из цистерны в топливный бак. Есть перспектива у морских перевозок аммиака и водорода, но пока всё ограничивается единичными экспериментами.

Оригинал – достаточно распространённая задача на #интервью, поэтому даже не буду перечислять компании. А в авторских обвесах брейнтизер подойдёт для нефтегазовой сферы.

У меня ещё одна задача припасена про перевалку СПГ, так что скоро вы опять пострадаете от моей профдеформации.

• Перевозка СПГ
• Решение

Сюрпост

Согласно учению древних мир состоит из четырёх стихий: земля, вода, воздух и огонь. В Китае же к числу четыре относятся с большим страхом, ведь оно созвучно со словом смерть. По представлениям древних египтян мир покоится на четырёх столбах. А четыре стороны света на четырех морях положены. Было у Макея четыре лакея, а ныне Макей сам лакей. Без четырех углов изба не рубится. Четыре кола вбито да небом покрыто. А мы сегодня пойдём…

#олимпиады

• На все четыре стороны
• Решение

Априори / Апостериори

В теории вероятности есть такие понятия как вероятность априорная и апострериорная. Первая (a priori) – это вероятность события в исходной постановке, а вторая (a posteriori) принимает в расчёт дополнительную информацию, которая поступает к нам в процессе наблюдения и которая, вообще говоря, может отличаться от исходной.

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

Похожая задачка может встретиться на #интервью в #Facebook (источник).

#тервер

• Монета с двумя орлами
• Решение

Теория информации в задачах на взвешивание

Одна из первых задач здесь после начала учёбы в ШАДе была вот эта классическая задача на взвешивание. Удивительным образом сегодня я её закольцую с учётом нового опыта.

В задачах подобного типа часто встаёт вопрос, а почему нельзя обойтись меньшим количеством операций? Иногда это очевидно, но формальное доказательство очень длинное и скучное. Так вот недавно узнал о технике, которая в некоторых случаях справляется с доказательством в несколько строчек.

Суть очень простая. Допустим, вы загадали целое число от 1 до 4, а ваш друг хочет его узнать. Друг может задавать вам вопросы типа «это число больше / меньше n?» и получать ответы «да / нет». Какое минимальное количество вопросов небходимо задать, чтобы гарантированно узнать число? (Необходимое количество вопросов не обязательно будет достаточным). Заметим, что ответ бинарен, поэтому в лучшем случае исходное множество вариантов при каждом ответе сокращается в 2 раза. Так как дважды два – четыре, то необходимо задать не менее двух вопросов. На языке теории информации говорят, что нужно передать вашему другу не менее 2 битов информации. Понятно, что в этом случае 2 битов достаточно.

В задачах на взвешивания ответ небинарен (, =). Однако подход всё равно работает, в чём мы сегодня убедимся.

Итак, во-первых, добавлено новое решение для задачи с 12 монетами на языке теории информации (спасибо проф. мехмата МГУ Николаю Константиновичу Верещагину за прекрасные лекции!). Во-вторых, добавлена новая задача с 13 монетами, которая очень наглядно иллюстрирует, где именно возникает потребность в дополнительном взвешивании.

#ШАД

• Новое решение для 12 монет
• Весы и 13 монет
• Решение для 13 монет

ШАД 2019-2023

У меня есть недостаток – я не умею бросать начатое. Этим летом успешно завершилась моя четырёхлетняя эпопея обучения в ШАДе Яндекса. Из-за огромного количества временных ресурсов, инвестированных в данное мероприятие, я не могу не порефлексировать здесь на эту тему.

Зачем мне это было нужно?

Цель: начать профессионально заниматься анализом данных, так как за свою карьеру я понял, что у меня есть образовательная база и интерес к этому. То есть я получаю удовольствие в этой функциональной области и хочу в ней расти.

Что по факту на выходе?

– новая работа в области анализа данных морской траспортировки
– свой параллельный проект с перспективой оформления в виде научной статьи
– значительное расширение хард-скиллового инструментария (этот пункт раскрою подробно отдельно, так как по сути это то, что мне было предложено в школе и за чем конкретно я пришёл, а первые два пункта являются следствием развития навыков в процессе учёбы)
– сообщество

Почему именно ШАД Яндекса?

На мой взгляд, ШАД в моменте это лучшее высшее образование в сфере прикладного анализа данных. Это не реклама. Вот три аргумента:

1. Серьёзные вступительные (3 этапа отбора + проверка мотивации). Это гаранития того, что вы будете учиться в компании очень замотивированных ребят с примерно одинаковым уровнем подготовки на старте.
2. Школа организована и финансируется компанией, бизнес которой построен на том, чему она учит. Как следствие, программа прикладная и актуальная. Зачастую преподают сотрудники Яндекса и дают почти SotA знания по теме.
3. Программа обучения рассчитана на два года. Как следствие, есть время полноценно охватить весь необходимый арсенал предметов по заявленному функционалу.

Для сравнения, классические университетские программы не удовлетворяют пункту 2, поэтому зачастую оторваны от реальности (либо неактуальны, либо слишком академичны).
Онлайн-курсы а-ля Coursera, GeekBrains, SkillFactory не удовлетворяют пунктам 1 и 3.

Обучение в ШАДе бесплатное. И эта благотворительность Яндекса имеет практичное объяснение – нанять к себе наиболее талантливых выпускников, у которых за время обучения возникает лояльность к компании. Яндекс же экономит на поиске (каламбур). Как следствие, приоритет ШАДа – это качество образовательного продукта (нет прямой коммерческой метрики).

У ШАДа были интересные альтернативы (в рамках указанной выше концепции из трёх пунктов): Made VK, Ozon Masters, School 21 Sber, появившиеся после 2019 года. Но, судя по их сайтам, по состоянию на 2023 год, к сожалению, они все канули в лету. ШАД набирает студентов с 2007 года по сегодняшний день.

Коротко о ШАДе, если вы не слышали. Программа обучения – 2 года (мой кейс был дольше из-за академов), четыре образовательных трека на выбор, в каждом семестре нужно закрывать по 3 курса.

В общем, горячо рекомендую Школу всем, чей кейс напоминает мой на входе. В качестве бонуса после выпуска вы остаётесь в коммьюнити, вам доступны любые курсы ШАДа, которые вы не смогли взять по какой-то причине. Lifelong learning.

P.S. Следующий набор стартует весной 2024 года. Если вы надумаете поступать, то по хэштэгу #ШАД можно посмотреть задачки со вступительных, которые мы разбирали в Матрёшке.

P.P.S. А что по нашим задачкам? Задачка будет на этой неделе. Обещаю очень интересный и полезный сюжет.

UPD: Школа 21 жива. Их новости лучше смотреть на VK, так как блог на сайте забросили.

❄️ Коха

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

В качестве исходной заготовки используем равносторонний треугольник. Далее рассмотрим любую сторону:

1. Поделим отрезок на три части:
_ _ _
2. На центральной части, как на стороне, возведём равносторонний треугольник, а основание сотрём:
_/\_
3. В итоге у нас получится четыре новых отрезка из исходной стороны, с каждым из которых мы проделаем операции 1-2 снова и снова.

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

Примечательно, что полученная фигура имеет бесконечный периметр, но конечную площадь. Граница снежинки настолько сложна, что имеет бесконечную длину между любыми двумя точками, как бы близко вы их не старались выбрать. Таким образом, получилось нечто более богатое, чем линейный объект (размерности 1), но беднее объектов плоских (размерности 2). Математики такие объекты характеризуют размерностью дробной, но об этом постараемся рассказать в новом году.

Нашу новогоднюю задачку я придумал сам, так как найти по теме что-то занятное не получилось. Сам придумал – сам решил. Показалось просто. Однако в процессе оформления осознал, что решил задачу неправильно. Более того, возникшая сложность мне кажется непреодолимой для аналитического решения. Буду благодарен сообществу за правильное решение, а пока, сможете ли вы найти изъян в моём? Как говорится в одном известном меме с Ди Каприо «we need to go deeper», поэтому сегодняшняя задача – это решение.

С наступающим Новым годом, добра и счастья вам и вашим близким 🎄

И огромное спасибо за то, что остаётесь с нами 💛

• Заяц на снежинке Коха
• Софизм

Большая математическая игра

Марабу запустили новую Большую математическую игру! Приглашаются дети 10-13 лет прокачать математику в игровой форме. Почему большая? Длится весь учебный год, но вступить можно в любой момент.

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

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

Из фишек: стратегии для одного игрока и для команд, квесты, HelpBot и чаты для общения.

• Игру можно проходить на русском или английском языке.
• Участие 4000 рублей в месяц, а дети из Украины — играют бесплатно.
• Первый пробный месяц игры — бесплатно для всех. Я бы обязательно сыграл, но мне «не скажу сколько» лет 🙃
• Главный приз — поездка в умный лагерь «Марабу»!

В игру! https://bit.ly/3SDAuPf

А пример реальной игровой задачи в сегодняшнем посте.

• Два бота и игрок
• Решение

В память о…

Сегодня проходит прощание с доктором физико-математических наук, профессором кафедры теории вероятностей механико-математического факультета Л.Г. Афанасьевой (14.09.1937 – 26.08.2022). Лариса Григорьевна изучала теорию очередей (queueing theory) или, как чаще говорят в русскоязычной литературе, теорию массового обслуживания и её применения в теории транспортных сетей. Под её руководством я защитил кандидатскую диссертацию по эргодичности (это такое хорошее свойство случайной системы) систем обслуживания одного специального типа. Стоит отметить, что теория очередей, как область теории вероятностей, не была популярна среди студентов в годы моего обучения (2000-е). Большинство студентов на кафедре среди прикладных направлений предпочитали финансовую и актуарную математику в общем-то по понятным причинам. К Ларисе Григорьевне меня привёл, с одной стороны, случай, а с другой, – вполне осознанный интерес и её авторитет на кафедре.

Уже будучи аспирантом восхищался её научной интуиции. Например, как-то раз во время обсуждения она заявила: «Я знаю, что эта система эргодична, но не знаю, как это доказать». Случалось и наоборот, когда какой-то результат удивлял Ларису Григорьевну, чему она искренне радовалась!

В общении со студентами и аспирантами Лариса Григорьевна подразумевала их хорошую осведомлённость и понимание предмета, что в моём отношении зачастую не соответствовало действительности. Примерно так читал академик А.Н. Колмогоров, полагая, что все его понимают, хотя понимали единицы или вообще никто. Это особый тип уважения – предполагать наличие у слушателя интеллекта, не уступающего своему.

Я расскажу сегодня о несложной, но занимательной задаче, которую Лариса Григорьевна задавала на одном из ранних студенческих семинаров. Для её решения потребуется начальное знание теории вероятностей на уровне функций распределения.

Светлая память 🤍

#тервер

• Случай на автобусной остановке
• Решение

Задачи на клетчатой доске

Что мы умеем делать с простой клетчатой доской:

— конечно же, играть во что-то, напоминающее шахматы
— мостить
— записывать числа, получая что-то типа магического квадрата
— раскрашивать
— прочий вздор…

#олимпиады

• Доска 5 х 5 (#127)
• Решение