Зарядка для мозга во время самоизоляции: шесть задач от школы анализа данных «Яндекса»
Привет, я куратор школы анализа данных «Яндекса». Самоизоляция — отличный повод немного прокачаться, поэтому я подобрал для вас задачи, которые помогут отвлечься от тревожных новостей с пользой для мозга.
Кстати, похожие задачи будут в этом году на вступительном экзамене в ШАД, где для людей с опытом в ИТ мы придумали новый трек, который поможет им улучшить свои знания математики.
В подобных задачах обычно не нужны глубокие познания — достаточно хорошо понимать, что такое размещения, перестановки и сочетания. Но все же требуется большая аккуратность при работе с элементарными событиями, то есть базовыми равновероятными исходами, из которых мы и будем конструировать события в задаче. В противном случае легко впасть в заблуждения в духе «вероятность 50%: либо произойдет, либо нет».
В этой задаче можно сэкономить время и нервы, если решать её «конструктивно»: представив, что составляете расстановку шаров, удовлетворяющую условиям.
Например, так: сначала расположим красные и зелёные шары (надо выбрать из десяти пять мест, в которых будут красные), после чего пять синих шаров надо положить не более, чем по одному, в одиннадцать промежутков между красными и зелёными шарами, а также слева и справа (то есть выбрать пять мест из одиннадцати).
Задачи по алгоритмам очень хороши тем, что они проверяют не только умение понятно описать некую процедуру, но и объяснить, почему она работает.
Если граф — дерево, то бракованное реле находится перед первой (от источника тока) не горящей лампочкой. Если есть циклы, то можно выключить все рёбра и запустить аналог поиска в глубину.
Задачи на графы, особенно если количество вершин небольшое, чаще всего стараются свести к разбору случаев. Важно, чтобы вы смогли внимательно разобрать их и при этом не запутаться.
Впрочем, эту классическую задачу можно решить и очень коротким элегантным способом (достаточно рассмотреть одного человека и троих его знакомых, а если таких меньше трёх, то «инвертируем» граф знакомств, заменив все рёбра их отсутствиями и наоборот — задача от этого не поменяется). Если его найдете, сэкономите много времени!
Еще одна задачка на тонкости логической связки «если — то». Тут важно разобраться, что под условие подходят карточки вида:
- четное число, гласная буква;
- нечетное число, что угодно.
И не подходят карточки вида:
- четное число, согласная буква.
Теперь становится ясно: что бы ни было написано на обороте карточек «А» и «5», это не влияет на ситуацию; а чтобы проверить условие, нам достаточно перевернуть карточки «Б» и «4» и проверить, нет ли на обороте четного числа и согласной буквы соответственно.
Задачка на геометрическую интуицию: надо понять, что ни один из меньших треугольников не может покрыть сразу две вершины. После этого становится ясно: чтобы покрыть все три вершины, нужно хотя бы три треугольника. А вообще тут зарыто непростое утверждение о диаметре треугольника, но его можно не доказывать.
Несмотря на то что это как будто бы задача на линейную алгебру, на самом деле ее суть в том, чтобы правильно разобраться со словами: «…такова, что для любой… такой, что». И не слишком-то важно, что речь идет о матрицах и следах. Если что-то верно для любой матрицы, удовлетворяющей некоторому условию, это верно и для каждой конкретной матрицы.
Таким образом, встретив подобную задачу, стоит сначала взять какие-нибудь конкретные (и желательно очень простые) матрицы X с нулевым следом и попробовать понять, что же нам дает условие tr(AX) = 0. В качестве таких матриц удобно взять матричные единицы (и матрицы, у которых на диагонали все нули, кроме двух элементов, равных 1 и (-1).
Собственно говоря, на этом задача и закончится: из условий tr(AX) = 0, которые вы распишете для таких матриц, сразу будет следовать ответ.
В задаче 5 какая-то ошибка
Роман, спасибо! Конечно, тут "двумя" выпало. Вот пример того, как стилистические правки могут исказить суть.
Комментарий недоступен
Всё корректно) В переводе с математического жаргона это как раз и значит "два синих шара никогда не лежат рядом"
Комментарий недоступен
Комментарий недоступен
А вы не могли бы перенести формулировки задач, например, во врезки? В заголовках они занимают слишком много места.
Готово :)
Здорово, спасибо большое!
А что за новый трек в ШАДе?
Мы создали его в этом году для тех, кто уже имеет опыт в IT и хочет развиваться дальше, но не так хорошо владеет высшей математикой, чтобы пройти через наш стандартный процесс отбора. При отборе мы будем учитывать умение программировать и знакомство с основами анализа данных, участие в проектах и наличие научных статей; математика же будет проверяться на гораздо более базовом уровне; собственно говоря, решать придётся задачи, похожие на задачи в этом посте. Поступивших ждёт адаптационный курс по высшей математике, который мы разработали специально для этого трека и который поможет им потом без проблем влиться в ШАДовский учебный процесс. Вот тут вы можете почитать подробнее про процесс поступления в ШАД: http://yandexdataschool.ru/enroll
Большое спасибо!
Ох и формулировки задач.
Математикам нравятся шарады, но подпускать их к программированию нельзя 😊
Задача 4: на обороте карточки "5" вполне может быть чётное число, что нарушит истинность утверждения. Так что её тоже надо перевернуть!
Тоже обратил на это внимание, подождем комментарий от автора)
В вашей ШАД много ошибок. Когда вы пишите: "В ряд выложены пять красных, пять синих и пять зеленых шаров.", то это означает что они выложены последовательно. Нужно либо добавлять в перемешку случайным образом.